aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure
AgeCommit message (Collapse)Author
2003-02-01Delete nodes more efficientlyChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5463 91177308-0d34-0410-b5e6-96231b3b80d8
2003-02-01Remove dead nodes more efficientlyChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5462 91177308-0d34-0410-b5e6-96231b3b80d8
2003-02-01Improve efficiency of aliveness traversal codeChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5461 91177308-0d34-0410-b5e6-96231b3b80d8
2003-02-01Change DSGraph stuff to use hash_(set|map) instead of std::(set|map)Chris Lattner
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
2003-02-01Remove using declarationsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5456 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-31Remove globals on the bottom up pass which do not contain any informationChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5451 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-31Add functions to the ban listChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5450 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-29Use and implement API for graph traversalsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5431 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-28free instructions mark their operands as being heap nodes.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5425 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-23* Eliminate boolean arguments in favor of using enumsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5420 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-23* Eliminate boolean arguments in favor of using enumsChris Lattner
* T-D pass now eliminates unreachable globals git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5419 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-23Slight efficiency improvementChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5418 91177308-0d34-0410-b5e6-96231b3b80d8
2003-01-22Fix analysis of the Burg programChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5401 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-12'graph' is spelled without a 'c'.Misha Brukman
Also added Statistic counters for NoAlias and MayAlias. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4972 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-10This file implements a pass that automatically parallelizes a program,Vikram S. Adve
using the Cilk multi-threaded runtime system to execute parallel code. The current version inserts too many sync() operations in the program because it does not attempt to optimize their placement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4962 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-08Iterator that enumerates the ProgramDependenceGraph (PDG) for a function,Vikram S. Adve
i.e., enumerates all data and control dependences for the function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4958 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-08An explicit representation of dependence graphs, and a pass thatVikram S. Adve
computes a dependence graph for data dependences on memory locations using interprocedural Mod/Ref information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4957 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-06Two bug fixes:Vikram S. Adve
(1) Make entries for Constant values in the ScalarMap. (2) Set MOD bit for the node pointed to by the argument of a free instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4948 91177308-0d34-0410-b5e6-96231b3b80d8
2002-12-06Fix several related bugs in DSNode::mergeWith() caused by theVikram S. Adve
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
2002-12-05Cute bug fix: when moving links from N to this, some links could haveVikram S. Adve
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
2002-11-27Fix logical error in TD pass: we should clear Mod/Ref bits of each callerVikram S. Adve
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
2002-11-27(1) Bug fix that was causing nodes with dangling references to be freed.Vikram S. Adve
We run removeDeadNodes() on the TD graph up front before using it. (2) Major enhancement to printing of results: now we list the actual objects that are mod/ref instead of just printing the bit vectors. Also an important bug fix in TDDataStructures pass (no change here): clear Mod/Ref bits of callers before inlining into a function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4833 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-25Keep global nodes in each DS Graph (by forcing them to be marked live).Vikram S. Adve
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4831 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-18Add peak memory usage measurement stuffChris Lattner
Add structure padding optimizations git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4749 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-18Add peak memory usage supportChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4748 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-18Add statsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4747 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-17Add hack to only consider indirect calls indirect if they do more than castChris Lattner
their source function git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4723 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-17Add MaxSCC statisticsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4722 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-13Pass to compute various statisics related to DSGraphs.Vikram S. Adve
For now, this just computes the #indirect call sites and the avg. #callees per indirect call site (actually it prints both totals and the average is their ratio). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4705 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-12Inline graphs from outside the SCC into the SCC before SCC resolution startsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4701 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-12Fix two bugs:Chris Lattner
* The globals vector was getting broken and unsorted, this caused vortex to get badly pessimized * Node offset handling was being handled really poorly, and in particular we were not merging types with offsets right. This causes several graphs to be non-merged. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4699 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Fix bugChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4697 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Handle a mismatch between # function args and call site argsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4696 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Elimiante calls to a node with nothing in it.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4695 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Complete rewrite of BU code to use Tarjan's SCC finding algorithm to driveChris Lattner
the algorithm instead of hand coded depth first iteration git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4694 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Mark stuff reachable by _AUX_ calls as incomplete in the BU graphChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4690 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Fix infinite loop in the BU algorithm. Unfortunately this dies a seriousChris Lattner
death when handling moderately sized SCC's, but what can you do git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4689 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Print the right call set sizeChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4688 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-11Use call site mergeWith method to simplify codeChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4687 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-10Fix a bug that could trigger when varargs call sites had non-matching number ↵Chris Lattner
of arguments git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4683 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-10* Dramatically rework liveness evaluation.Chris Lattner
* Implement the first step of the Globals graph: Deleting nodes from function graphs. In practice, these nodes need to be moved to the globals graph, but this will be taken care of later. Note that the graphs computed right now are not strictly correct! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4681 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-10Honor the shouldPrintAuxCalls flagChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4678 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-10Initialize PrintAuxCalls memberChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4677 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-10* Bottom-Up graphs print the Aux call vectorChris Lattner
* Significantly improve DEBUG output * Aggressively fold calls together if we inlined a graph that provides call nodes. * Add a bailout if the current graph has over 200 call nodes in it, this is a really whacky case that should never happen. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4675 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09eliminate the ability to remove global nodes from deadNodeElminate... for now.Chris Lattner
This slows stuff down a bit, but it should get much better before it gets any worse. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4666 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09Remove obsolete codeChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4665 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09Fix logicChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4664 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09Add globals graphs to all three passesChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4663 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09Move maskNodeTypes to header fileChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4661 91177308-0d34-0410-b5e6-96231b3b80d8
2002-11-09Clean up DSGraph::removeDeadNodes interfaceChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4660 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-09 10:35:40 +0000