diff options
| -rw-r--r-- | docs/AliasAnalysis.html | 23 | ||||
| -rw-r--r-- | docs/Passes.html | 75 | ||||
| -rw-r--r-- | docs/ReleaseNotes.html | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/Passes.h | 7 | ||||
| -rw-r--r-- | include/llvm/LinkAllPasses.h | 1 | ||||
| -rw-r--r-- | lib/Analysis/IPA/Andersens.cpp | 2868 |
6 files changed, 2 insertions, 2974 deletions
diff --git a/docs/AliasAnalysis.html b/docs/AliasAnalysis.html index ebf6386..5b4eb93 100644 --- a/docs/AliasAnalysis.html +++ b/docs/AliasAnalysis.html @@ -403,7 +403,7 @@ implementing, you just override the interfaces you can improve.</p> href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a> passes) every alias analysis pass chains to another alias analysis implementation (for example, the user can specify "<tt>-basicaa -ds-aa --anders-aa -licm</tt>" to get the maximum benefit from the three alias +-licm</tt>" to get the maximum benefit from both alias analyses). The alias analysis class automatically takes care of most of this for methods that you don't override. For methods that you do override, in code paths that return a conservative MayAlias or Mod/Ref result, simply return @@ -705,25 +705,6 @@ non-address taken globals), but is very quick analysis.</p> <!-- _______________________________________________________________________ --> <div class="doc_subsubsection"> - <a name="anders-aa">The <tt>-anders-aa</tt> pass</a> -</div> - -<div class="doc_text"> - -<p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm" -for interprocedural alias analysis. This algorithm is a subset-based, -flow-insensitive, context-insensitive, and field-insensitive alias analysis that -is widely believed to be fairly precise. Unfortunately, this algorithm is also -O(N<sup>3</sup>). The LLVM implementation currently does not implement any of -the refinements (such as "online cycle elimination" or "offline variable -substitution") to improve its efficiency, so it can be quite slow in common -cases. -</p> - -</div> - -<!-- _______________________________________________________________________ --> -<div class="doc_subsubsection"> <a name="steens-aa">The <tt>-steens-aa</tt> pass</a> </div> @@ -855,7 +836,7 @@ pointer.</p> <div class="doc_text"> <p>These passes are useful for evaluating the various alias analysis -implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa +implementations. You can use them with commands like '<tt>opt -ds-aa -aa-eval foo.bc -disable-output -stats</tt>'.</p> </div> diff --git a/docs/Passes.html b/docs/Passes.html index bbf6b3d..a2bacf9 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -75,7 +75,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <tr><th colspan="2"><b>ANALYSIS PASSES</b></th></tr> <tr><th>Option</th><th>Name</th></tr> <tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr> -<tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr> <tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr> <tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr> <tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Optimize for code generation</td></tr> @@ -204,80 +203,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <!-------------------------------------------------------------------------- --> <div class="doc_subsection"> - <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a> -</div> -<div class="doc_text"> - <p> - This is an implementation of Andersen's interprocedural alias - analysis - </p> - - <p> - In pointer analysis terms, this is a subset-based, flow-insensitive, - field-sensitive, and context-insensitive algorithm pointer algorithm. - </p> - - <p> - This algorithm is implemented as three stages: - </p> - - <ol> - <li>Object identification.</li> - <li>Inclusion constraint identification.</li> - <li>Offline constraint graph optimization.</li> - <li>Inclusion constraint solving.</li> - </ol> - - <p> - The object identification stage identifies all of the memory objects in the - program, which includes globals, heap allocated objects, and stack allocated - objects. - </p> - - <p> - The inclusion constraint identification stage finds all inclusion constraints - in the program by scanning the program, looking for pointer assignments and - other statements that effect the points-to graph. For a statement like - <code><var>A</var> = <var>B</var></code>, this statement is processed to - indicate that <var>A</var> can point to anything that <var>B</var> can point - to. Constraints can handle copies, loads, and stores, and address taking. - </p> - - <p> - The offline constraint graph optimization portion includes offline variable - substitution algorithms intended to computer pointer and location - equivalences. Pointer equivalences are those pointers that will have the - same points-to sets, and location equivalences are those variables that - always appear together in points-to sets. - </p> - - <p> - The inclusion constraint solving phase iteratively propagates the inclusion - constraints until a fixed point is reached. This is an O(<var>n</var>³) - algorithm. - </p> - - <p> - Function constraints are handled as if they were structs with <var>X</var> - fields. Thus, an access to argument <var>X</var> of function <var>Y</var> is - an access to node index <code>getNode(<var>Y</var>) + <var>X</var></code>. - This representation allows handling of indirect calls without any issues. To - wit, an indirect call <code><var>Y</var>(<var>a</var>,<var>b</var>)</code> is - equivalent to <code>*(<var>Y</var> + 1) = <var>a</var>, *(<var>Y</var> + 2) = - <var>b</var></code>. The return node for a function <var>F</var> is always - located at <code>getNode(<var>F</var>) + CallReturnPos</code>. The arguments - start at <code>getNode(<var>F</var>) + CallArgPos</code>. - </p> - - <p> - Please keep in mind that the current andersen's pass has many known - problems and bugs. It should be considered "research quality". - </p> - -</div> - -<!-------------------------------------------------------------------------- --> -<div class="doc_subsection"> <a name="basicaa">Basic Alias Analysis (default AA impl)</a> </div> <div class="doc_text"> diff --git a/docs/ReleaseNotes.html b/docs/ReleaseNotes.html index 84200c3..3b96432 100644 --- a/docs/ReleaseNotes.html +++ b/docs/ReleaseNotes.html @@ -66,7 +66,6 @@ Almost dead code. llvm/Analysis/PointerTracking.h => Edwin wants this, consider for 2.8. ABCD, SCCVN, GEPSplitterPass MSIL backend? - AndersAA -> Unsupported, zap after branch. --> @@ -734,7 +733,6 @@ href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">LLVMdev list</a>.</p> experimental.</li> <li>The <tt>llc</tt> "<tt>-filetype=asm</tt>" (the default) is the only supported value for this option. The ELF writer is experimental.</li> -<li>The implementation of Andersen's Alias Analysis has many known bugs.</li> </ul> </div> diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 2f39c6a..1a5cbb2 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -81,13 +81,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createAndersensPass - This pass implements Andersen's interprocedural alias - // analysis. - // - ModulePass *createAndersensPass(); - - //===--------------------------------------------------------------------===// - // // createProfileLoaderPass - This pass loads information from a profile dump // file. // diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index a7e2e05..ae53851 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -46,7 +46,6 @@ namespace { (void) llvm::createAggressiveDCEPass(); (void) llvm::createAliasAnalysisCounterPass(); (void) llvm::createAliasDebugger(); - (void) llvm::createAndersensPass(); (void) llvm::createArgumentPromotionPass(); (void) llvm::createStructRetPromotionPass(); (void) llvm::createBasicAliasAnalysisPass(); diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp deleted file mode 100644 index 2e35a56..0000000 --- a/lib/Analysis/IPA/Andersens.cpp +++ /dev/null @@ -1,2868 +0,0 @@ -//===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines an implementation of Andersen's interprocedural alias -// analysis -// -// In pointer analysis terms, this is a subset-based, flow-insensitive, -// field-sensitive, and context-insensitive algorithm pointer algorithm. -// -// This algorithm is implemented as three stages: -// 1. Object identification. -// 2. Inclusion constraint identification. -// 3. Offline constraint graph optimization -// 4. Inclusion constraint solving. -// -// The object identification stage identifies all of the memory objects in the -// program, which includes globals, heap allocated objects, and stack allocated -// objects. -// -// The inclusion constraint identification stage finds all inclusion constraints -// in the program by scanning the program, looking for pointer assignments and -// other statements that effect the points-to graph. For a statement like "A = -// B", this statement is processed to indicate that A can point to anything that -// B can point to. Constraints can handle copies, loads, and stores, and -// address taking. -// -// The offline constraint graph optimization portion includes offline variable -// substitution algorithms intended to compute pointer and location -// equivalences. Pointer equivalences are those pointers that will have the -// same points-to sets, and location equivalences are those variables that -// always appear together in points-to sets. It also includes an offline -// cycle detection algorithm that allows cycles to be collapsed sooner -// during solving. -// -// The inclusion constraint solving phase iteratively propagates the inclusion -// constraints until a fixed point is reached. This is an O(N^3) algorithm. -// -// Function constraints are handled as if they were structs with X fields. -// Thus, an access to argument X of function Y is an access to node index -// getNode(Y) + X. This representation allows handling of indirect calls -// without any issues. To wit, an indirect call Y(a,b) is equivalent to -// *(Y + 1) = a, *(Y + 2) = b. -// The return node for a function is always located at getNode(F) + -// CallReturnPos. The arguments start at getNode(F) + CallArgPos. -// -// Future Improvements: -// Use of BDD's. -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "anders-aa" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/Support/InstVisitor.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Support/Debug.h" -#include "llvm/System/Atomic.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/SparseBitVector.h" -#include "llvm/ADT/DenseSet.h" -#include <algorithm> -#include <set> -#include <list> -#include <map> -#include <stack> -#include <vector> -#include <queue> - -// Determining the actual set of nodes the universal set can consist of is very -// expensive because it means propagating around very large sets. We rely on -// other analysis being able to determine which nodes can never be pointed to in -// order to disambiguate further than "points-to anything". -#define FULL_UNIVERSAL 0 - -using namespace llvm; -#ifndef NDEBUG -STATISTIC(NumIters , "Number of iterations to reach convergence"); -#endif -STATISTIC(NumConstraints, "Number of constraints"); -STATISTIC(NumNodes , "Number of nodes"); -STATISTIC(NumUnified , "Number of variables unified"); -STATISTIC(NumErased , "Number of redundant constraints erased"); - -static const unsigned SelfRep = (unsigned)-1; -static const unsigned Unvisited = (unsigned)-1; -// Position of the function return node relative to the function node. -static const unsigned CallReturnPos = 1; -// Position of the function call node relative to the function node. -static const unsigned CallFirstArgPos = 2; - -namespace { - struct BitmapKeyInfo { - static inline SparseBitVector<> *getEmptyKey() { - return reinterpret_cast<SparseBitVector<> *>(-1); - } - static inline SparseBitVector<> *getTombstoneKey() { - return reinterpret_cast<SparseBitVector<> *>(-2); - } - static unsigned getHashValue(const SparseBitVector<> *bitmap) { - return bitmap->getHashValue(); - } - static bool isEqual(const SparseBitVector<> *LHS, - const SparseBitVector<> *RHS) { - if (LHS == RHS) - return true; - else if (LHS == getEmptyKey() || RHS == getEmptyKey() - || LHS == getTombstoneKey() || RHS == getTombstoneKey()) - return false; - - return *LHS == *RHS; - } - }; - - class Andersens : public ModulePass, public AliasAnalysis, - private InstVisitor<Andersens> { - struct Node; - - /// Constraint - Objects of this structure are used to represent the various - /// constraints identified by the algorithm. The constraints are 'copy', - /// for statements like "A = B", 'load' for statements like "A = *B", - /// 'store' for statements like "*A = B", and AddressOf for statements like - /// A = alloca; The Offset is applied as *(A + K) = B for stores, - /// A = *(B + K) for loads, and A = B + K for copies. It is - /// illegal on addressof constraints (because it is statically - /// resolvable to A = &C where C = B + K) - - struct Constraint { - enum ConstraintType { Copy, Load, Store, AddressOf } Type; - unsigned Dest; - unsigned Src; - unsigned Offset; - - Constraint(ConstraintType Ty, unsigned D, unsigned S, unsigned O = 0) - : Type(Ty), Dest(D), Src(S), Offset(O) { - assert((Offset == 0 || Ty != AddressOf) && - "Offset is illegal on addressof constraints"); - } - - bool operator==(const Constraint &RHS) const { - return RHS.Type == Type - && RHS.Dest == Dest - && RHS.Src == Src - && RHS.Offset == Offset; - } - - bool operator!=(const Constraint &RHS) const { - return !(*this == RHS); - } - - bool operator<(const Constraint &RHS) const { - if (RHS.Type != Type) - return RHS.Type < Type; - else if (RHS.Dest != Dest) - return RHS.Dest < Dest; - else if (RHS.Src != Src) - return RHS.Src < Src; - return RHS.Offset < Offset; - } - }; - - // Information DenseSet requires implemented in order to be able to do - // it's thing - struct PairKeyInfo { - static inline std::pair<unsigned, unsigned> getEmptyKey() { - return std::make_pair(~0U, ~0U); - } - static inline std::pair<unsigned, unsigned> getTombstoneKey() { - return std::make_pair(~0U - 1, ~0U - 1); - } - static unsigned getHashValue(const std::pair<unsigned, unsigned> &P) { - return P.first ^ P.second; - } - static unsigned isEqual(const std::pair<unsigned, unsigned> &LHS, - const std::pair<unsigned, unsigned> &RHS) { - return LHS == RHS; - } - }; - - struct ConstraintKeyInfo { - static inline Constraint getEmptyKey() { - return Constraint(Constraint::Copy, ~0U, ~0U, ~0U); - } - static inline Constraint getTombstoneKey() { - return Constraint(Constraint::Copy, ~0U - 1, ~0U - 1, ~0U - 1); - } - static unsigned getHashValue(const Constraint &C) { - return C.Src ^ C.Dest ^ C.Type ^ C.Offset; - } - static bool isEqual(const Constraint &LHS, - const Constraint &RHS) { - return LHS.Type == RHS.Type && LHS.Dest == RHS.Dest - && LHS.Src == RHS.Src && LHS.Offset == RHS.Offset; - } - }; - - // Node class - This class is used to represent a node in the constraint - // graph. Due to various optimizations, it is not always the case that - // there is a mapping from a Node to a Value. In particular, we add - // artificial Node's that represent the set of pointed-to variables shared - // for each location equivalent Node. - struct Node { - private: - static volatile sys::cas_flag Counter; - - public: - Value *Val; - SparseBitVector<> *Edges; - SparseBitVector<> *PointsTo; - SparseBitVector<> *OldPointsTo; - std::list<Constraint> Constraints; - - // Pointer and location equivalence labels - unsigned PointerEquivLabel; - unsigned LocationEquivLabel; - // Predecessor edges, both real and implicit - SparseBitVector<> *PredEdges; - SparseBitVector<> *ImplicitPredEdges; - // Set of nodes that point to us, only use for location equivalence. - SparseBitVector<> *PointedToBy; - // Number of incoming edges, used during variable substitution to early - // free the points-to sets - unsigned NumInEdges; - // True if our points-to set is in the Set2PEClass map - bool StoredInHash; - // True if our node has no indirect constraints (complex or otherwise) - bool Direct; - // True if the node is address taken, *or* it is part of a group of nodes - // that must be kept together. This is set to true for functions and - // their arg nodes, which must be kept at the same position relative to - // their base function node. - bool AddressTaken; - - // Nodes in cycles (or in equivalence classes) are united together using a - // standard union-find representation with path compression. NodeRep - // gives the index into GraphNodes for the representative Node. - unsigned NodeRep; - - // Modification timestamp. Assigned from Counter. - // Used for work list prioritization. - unsigned Timestamp; - - explicit Node(bool direct = true) : - Val(0), Edges(0), PointsTo(0), OldPointsTo(0), - PointerEquivLabel(0), LocationEquivLabel(0), PredEdges(0), - ImplicitPredEdges(0), PointedToBy(0), NumInEdges(0), - StoredInHash(false), Direct(direct), AddressTaken(false), - NodeRep(SelfRep), Timestamp(0) { } - - Node *setValue(Value *V) { - assert(Val == 0 && "Value already set for this node!"); - Val = V; - return this; - } - - /// getValue - Return the LLVM value corresponding to this node. - /// - Value *getValue() const { return Val; } - - /// addPointerTo - Add a pointer to the list of pointees of this node, - /// returning true if this caused a new pointer to be added, or false if - /// we already knew about the points-to relation. - bool addPointerTo(unsigned Node) { - return PointsTo->test_and_set(Node); - } - - /// intersects - Return true if the points-to set of this node intersects - /// with the points-to set of the specified node. - bool intersects(Node *N) const; - - /// intersectsIgnoring - Return true if the points-to set of this node - /// intersects with the points-to set of the specified node on any nodes - /// except for the specified node to ignore. - bool intersectsIgnoring(Node *N, unsigned) const; - - // Timestamp a node (used for work list prioritization) - void Stamp() { - Timestamp = sys::AtomicIncrement(&Counter); - --Timestamp; - } - - bool isRep() const { - return( (int) NodeRep < 0 ); - } - }; - - struct WorkListElement { - Node* node; - unsigned Timestamp; - WorkListElement(Node* n, unsigned t) : node(n), Timestamp(t) {} - - // Note that we reverse the sense of the comparison because we - // actually want to give low timestamps the priority over high, - // whereas priority is typically interpreted as a greater value is - // given high priority. - bool operator<(const WorkListElement& that) const { - return( this->Timestamp > that.Timestamp ); - } - }; - - // Priority-queue based work list specialized for Nodes. - class WorkList { - std::priority_queue<WorkListElement> Q; - - public: - void insert(Node* n) { - Q.push( WorkListElement(n, n->Timestamp) ); - } - - // We automatically discard non-representative nodes and nodes - // that were in the work list twice (we keep a copy of the - // timestamp in the work list so we can detect this situation by - // comparing against the node's current timestamp). - Node* pop() { - while( !Q.empty() ) { - WorkListElement x = Q.top(); Q.pop(); - Node* INode = x.node; - - if( INode->isRep() && - INode->Timestamp == x.Timestamp ) { - return(x.node); - } - } - return(0); - } - - bool empty() { - return Q.empty(); - } - }; - - /// GraphNodes - This vector is populated as part of the object - /// identification stage of the analysis, which populates this vector with a - /// node for each memory object and fills in the ValueNodes map. - std::vector<Node> GraphNodes; - - /// ValueNodes - This map indicates the Node that a particular Value* is - /// represented by. This contains entries for all pointers. - DenseMap<Value*, unsigned> ValueNodes; - - /// ObjectNodes - This map contains entries for each memory object in the - /// program: globals, alloca's and mallocs. - DenseMap<Value*, unsigned> ObjectNodes; - - /// ReturnNodes - This map contains an entry for each function in the - /// program that returns a value. - DenseMap<Function*, unsigned> ReturnNodes; - - /// VarargNodes - This map contains the entry used to represent all pointers - /// passed through the varargs portion of a function call for a particular - /// function. An entry is not present in this map for functions that do not - /// take variable arguments. - DenseMap<Function*, unsigned> VarargNodes; - - - /// Constraints - This vector contains a list of all of the constraints - /// identified by the program. - std::vector<Constraint> Constraints; - - // Map from graph node to maximum K value that is allowed (for functions, - // this is equivalent to the number of arguments + CallFirstArgPos) - std::map<unsigned, unsigned> MaxK; - - /// This enum defines the GraphNodes indices that correspond to important - /// fixed sets. - enum { - UniversalSet = 0, - NullPtr = 1, - NullObject = 2, - NumberSpecialNodes - }; - // Stack for Tarjan's - std::stack<unsigned> SCCStack; - // Map from Graph Node to DFS number - std::vector<unsigned> Node2DFS; - // Map from Graph Node to Deleted from graph. - std::vector<bool> Node2Deleted; - // Same as Node Maps, but implemented as std::map because it is faster to - // clear - std::map<unsigned, unsigned> Tarjan2DFS; - std::map<unsigned, bool> Tarjan2Deleted; - // Current DFS number - unsigned DFSNumber; - - // Work lists. - WorkList w1, w2; - WorkList *CurrWL, *NextWL; // "current" and "next" work lists - - // Offline variable substitution related things - - // Temporary rep storage, used because we can't collapse SCC's in the - // predecessor graph by uniting the variables permanently, we can only do so - // for the successor graph. - std::vector<unsigned> VSSCCRep; - // Mapping from node to whether we have visited it during SCC finding yet. - std::vector<bool> Node2Visited; - // During variable substitution, we create unknowns to represent the unknown - // value that is a dereference of a variable. These nodes are known as - // "ref" nodes (since they represent the value of dereferences). - unsigned FirstRefNode; - // During HVN, we create represent address taken nodes as if they were - // unknown (since HVN, unlike HU, does not evaluate unions). - unsigned FirstAdrNode; - // Current pointer equivalence class number - unsigned PEClass; - // Mapping from points-to sets to equivalence classes - typedef DenseMap<SparseBitVector<> *, unsigned, BitmapKeyInfo> BitVectorMap; - BitVectorMap Set2PEClass; - // Mapping from pointer equivalences to the representative node. -1 if we - // have no representative node for this pointer equivalence class yet. - std::vector<int> PEClass2Node; - // Mapping from pointer equivalences to representative node. This includes - // pointer equivalent but not location equivalent variables. -1 if we have - // no representative node for this pointer equivalence class yet. - std::vector<int> PENLEClass2Node; - // Union/Find for HCD - std::vector<unsigned> HCDSCCRep; - // HCD's offline-detected cycles; "Statically DeTected" - // -1 if not part of such a cycle, otherwise a representative node. - std::vector<int> SDT; - // Whether to use SDT (UniteNodes can use it during solving, but not before) - bool SDTActive; - - public: - static char ID; - Andersens() : ModulePass(&ID) {} - - bool runOnModule(Module &M) { - InitializeAliasAnalysis(this); - IdentifyObjects(M); - CollectConstraints(M); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa-constraints" - DEBUG(PrintConstraints()); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa" - SolveConstraints(); - DEBUG(PrintPointsToGraph()); - - // Free the constraints list, as we don't need it to respond to alias - // requests. - std::vector<Constraint>().swap(Constraints); - //These are needed for Print() (-analyze in opt) - //ObjectNodes.clear(); - //ReturnNodes.clear(); - //VarargNodes.clear(); - return false; - } - - void releaseMemory() { - // FIXME: Until we have transitively required passes working correctly, - // this cannot be enabled! Otherwise, using -count-aa with the pass - // causes memory to be freed too early. :( -#if 0 - // The memory objects and ValueNodes data structures at the only ones that - // are still live after construction. - std::vector<Node>().swap(GraphNodes); - ValueNodes.clear(); -#endif - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.setPreservesAll(); // Does not transform code - } - - /// getAdjustedAnalysisPointer - This method is used when a pass implements - /// an analysis interface through multiple inheritance. If needed, it - /// should override this to adjust the this pointer as needed for the - /// specified pass info. - virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { - if (PI->isPassID(&AliasAnalysis::ID)) - return (AliasAnalysis*)this; - return this; - } - - //------------------------------------------------ - // Implement the AliasAnalysis API - // - AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); - virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); - virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); - bool pointsToConstantMemory(const Value *P); - - virtual void deleteValue(Value *V) { - ValueNodes.erase(V); - getAnalysis<AliasAnalysis>().deleteValue(V); - } - - virtual void copyValue(Value *From, Value *To) { - ValueNodes[To] = ValueNodes[From]; - getAnalysis<AliasAnalysis>().copyValue(From, To); - } - - private: - /// getNode - Return the node corresponding to the specified pointer scalar. - /// - unsigned getNode(Value *V) { - if (Constant *C = dyn_cast<Constant>(V)) - if (!isa<GlobalValue>(C)) - return getNodeForConstantPointer(C); - - DenseMap<Value*, unsigned>::iterator I = ValueNodes.find(V); - if (I == ValueNodes.end()) { -#ifndef NDEBUG - V->dump(); -#endif - llvm_unreachable("Value does not have a node in the points-to graph!"); - } - return I->second; - } - - /// getObject - Return the node corresponding to the memory object for the - /// specified global or allocation instruction. - unsigned getObject(Value *V) const { - DenseMap<Value*, unsigned>::const_iterator I = ObjectNodes.find(V); - assert(I != ObjectNodes.end() && - "Value does not have an object in the points-to graph!"); - return I->second; - } - - /// getReturnNode - Return the node representing the return value for the - /// specified function. - unsigned getReturnNode(Function *F) const { - DenseMap<Function*, unsigned>::const_iterator I = ReturnNodes.find(F); - assert(I != ReturnNodes.end() && "Function does not return a value!"); - return I->second; - } - - /// getVarargNode - Return the node representing the variable arguments - /// formal for the specified function. - unsigned getVarargNode(Function *F) const { - DenseMap<Function*, unsigned>::const_iterator I = VarargNodes.find(F); - assert(I != VarargNodes.end() && "Function does not take var args!"); - return I->second; - } - - /// getNodeValue - Get the node for the specified LLVM value and set the - /// value for it to be the specified value. - unsigned getNodeValue(Value &V) { - unsigned Index = getNode(&V); - GraphNodes[Index].setValue(&V); - return Index; - } - - unsigned UniteNodes(unsigned First, unsigned Second, - bool UnionByRank = true); - unsigned FindNode(unsigned Node); - unsigned FindNode(unsigned Node) const; - - void IdentifyObjects(Module &M); - void CollectConstraints(Module &M); - bool AnalyzeUsesOfFunction(Value *); - void CreateConstraintGraph(); - void OptimizeConstraints(); - unsigned FindEquivalentNode(unsigned, unsigned); - void ClumpAddressTaken(); - void RewriteConstraints(); - void HU(); - void HVN(); - void HCD(); - void Search(unsigned Node); - void UnitePointerEquivalences(); - void SolveConstraints(); - bool QueryNode(unsigned Node); - void Condense(unsigned Node); - void HUValNum(unsigned Node); - void HVNValNum(unsigned Node); - unsigned getNodeForConstantPointer(Constant *C); - unsigned getNodeForConstantPointerTarget(Constant *C); - void AddGlobalInitializerConstraints(unsigned, Constant *C); - - void AddConstraintsForNonInternalLinkage(Function *F); - void AddConstraintsForCall(CallSite CS, Function *F); - bool AddConstraintsForExternalCall(CallSite CS, Function *F); - - - void PrintNode(const Node *N) const; - void PrintConstraints() const ; - void PrintConstraint(const Constraint &) const; - void PrintLabels() const; - void PrintPointsToGraph() const; - - //===------------------------------------------------------------------===// - // Instruction visitation methods for adding constraints - // - friend class InstVisitor<Andersens>; - void visitReturnInst(ReturnInst &RI); - void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); } - void visitCallInst(CallInst &CI) { - if (isMalloc(&CI)) visitAlloc(CI); - else visitCallSite(CallSite(&CI)); - } - void visitCallSite(CallSite CS); - void visitAllocaInst(AllocaInst &I); - void visitAlloc(Instruction &I); - void visitLoadInst(LoadInst &LI); - void visitStoreInst(StoreInst &SI); - void visitGetElementPtrInst(GetElementPtrInst &GEP); - void visitPHINode(PHINode &PN); - void visitCastInst(CastInst &CI); - void visitICmpInst(ICmpInst &ICI) {} // NOOP! - void visitFCmpInst(FCmpInst &ICI) {} // NOOP! - void visitSelectInst(SelectInst &SI); - void visitVAArg(VAArgInst &I); - void visitInstruction(Instruction &I); - - //===------------------------------------------------------------------===// - // Implement Analyize interface - // - void print(raw_ostream &O, const Module*) const { - PrintPointsToGraph(); - } - }; -} - -char Andersens::ID = 0; -static RegisterPass<Andersens> -X("anders-aa", "Andersen's Interprocedural Alias Analysis (experimental)", - false, true); -static RegisterAnalysisGroup<AliasAnalysis> Y(X); - -// Initialize Timestamp Counter (static). -volatile llvm::sys::cas_flag Andersens::Node::Counter = 0; - -ModulePass *llvm::createAndersensPass() { return new Andersens(); } - -//===----------------------------------------------------------------------===// -// AliasAnalysis Interface Implementation -//===----------------------------------------------------------------------===// - -AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - Node *N1 = &GraphNodes[FindNode(getNode(const_cast<Value*>(V1)))]; - Node *N2 = &GraphNodes[FindNode(getNode(const_cast<Value*>(V2)))]; - - // Check to see if the two pointers are known to not alias. They don't alias - // if their points-to sets do not intersect. - if (!N1->intersectsIgnoring(N2, NullObject)) - return NoAlias; - - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); -} - -AliasAnalysis::ModRefResult -Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) { - // The only thing useful that we can contribute for mod/ref information is - // when calling external function calls: if we know that memory never escapes - // from the program, it cannot be modified by an external call. - // - // NOTE: This is not really safe, at least not when the entire program is not - // available. The deal is that the external function could call back into the - // program and modify stuff. We ignore this technical niggle for now. This - // is, after all, a "research quality" implementation of Andersen's analysis. - if (Function *F = CS.getCalledFunction()) - if (F->isDeclaration()) { - Node *N1 = &GraphNodes[FindNode(getNode(P))]; - - if (N1->PointsTo->empty()) - return NoModRef; -#if FULL_UNIVERSAL - if (!UniversalSet->PointsTo->test(FindNode(getNode(P)))) - return NoModRef; // Universal set does not contain P -#else - if (!N1->PointsTo->test(UniversalSet)) - return NoModRef; // P doesn't point to the universal set. -#endif - } - - return AliasAnalysis::getModRefInfo(CS, P, Size); -} - -AliasAnalysis::ModRefResult -Andersens::getModRefInfo(CallSite CS1, CallSite CS2) { - return AliasAnalysis::getModRefInfo(CS1,CS2); -} - -/// pointsToConstantMemory - If we can determine that this pointer only points -/// to constant memory, return true. In practice, this means that if the -/// pointer can only point to constant globals, functions, or the null pointer, -/// return true. -/// -bool Andersens::pointsToConstantMemory(const Value *P) { - Node *N = &GraphNodes[FindNode(getNode(const_cast<Value*>(P)))]; - unsigned i; - - for (SparseBitVector<>::iterator bi = N->PointsTo->begin(); - bi != N->PointsTo->end(); - ++bi) { - i = *bi; - Node *Pointee = &GraphNodes[i]; - if (Value *V = Pointee->getValue()) { - if (!isa<GlobalValue>(V) || (isa<GlobalVariable>(V) && - !cast<GlobalVariable>(V)->isConstant())) - return AliasAnalysis::pointsToConstantMemory(P); - } else { - if (i != NullObject) - return AliasAnalysis::pointsToConstantMemory(P); - } - } - - return true; -} - -//===----------------------------------------------------------------------===// -// Object Identification Phase -//===----------------------------------------------------------------------===// - -/// IdentifyObjects - This stage scans the program, adding an entry to the -/// GraphNodes list for each memory object in the program (global stack or -/// heap), and populates the ValueNodes and ObjectNodes maps for these objects. -/// -void Andersens::IdentifyObjects(Module &M) { - unsigned NumObjects = 0; - - // Object #0 is always the universal set: the object that we don't know - // anything about. - assert(NumObjects == UniversalSet && "Something changed!"); - ++NumObjects; - - // Object #1 always represents the null pointer. - assert(NumObjects == NullPtr && "Something changed!"); - ++NumObjects; - - // Object #2 always represents the null object (the object pointed to by null) - assert(NumObjects == NullObject && "Something changed!"); - ++NumObjects; - - // Add all the globals first. - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) { - ObjectNodes[I] = NumObjects++; - ValueNodes[I] = NumObjects++; - } - - // Add nodes for all of the functions and the instructions inside of them. - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - // The function itself is a memory object. - unsigned First = NumObjects; - ValueNodes[F] = NumObjects++; - if (F->getFunctionType()->getReturnType()->isPointerTy()) - ReturnNodes[F] = NumObjects++; - if (F->getFunctionType()->isVarArg()) - VarargNodes[F] = NumObjects++; - - - // Add nodes for all of the incoming pointer arguments. - for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); - I != E; ++I) - { - if (I->getType()->isPointerTy()) - ValueNodes[I] = NumObjects++; - } - MaxK[First] = NumObjects - First; - - // Scan the function body, creating a memory object for each heap/stack - // allocation in the body of the function and a node to represent all - // pointer values defined by instructions and used as operands. - for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { - // If this is an heap or stack allocation, create a node for the memory - // object. - if (II->getType()->isPointerTy()) { - ValueNodes[&*II] = NumObjects++; - if (AllocaInst *AI = dyn_cast<AllocaInst>(&*II)) - ObjectNodes[AI] = NumObjects++; - else if (isMalloc(&*II)) - ObjectNodes[&*II] = NumObjects++; - } - - // Calls to inline asm need to be added as well because the callee isn't - // referenced anywhere else. - if (CallInst *CI = dyn_cast<CallInst>(&*II)) { - Value *Callee = CI->getCalledValue(); - if (isa<InlineAsm>(Callee)) - ValueNodes[Callee] = NumObjects++; - } - } - } - - // Now that we know how many objects to create, make them all now! - GraphNodes.resize(NumObjects); - NumNodes += NumObjects; -} - -//===----------------------------------------------------------------------===// -// Constraint Identification Phase -//===----------------------------------------------------------------------===// - -/// getNodeForConstantPointer - Return the node corresponding to the constant -/// pointer itself. -unsigned Andersens::getNodeForConstantPointer(Constant *C) { - assert(C->getType()->isPointerTy() && "Not a constant pointer!"); - - if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C)) - return NullPtr; - else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) - return getNode(GV); - else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { - switch (CE->getOpcode()) { - case Instruction::GetElementPtr: - return getNodeForConstantPointer(CE->getOperand(0)); - case Instruction::IntToPtr: - return UniversalSet; - case Instruction::BitCast: - return getNodeForConstantPointer(CE->getOperand(0)); - default: - errs() << "Constant Expr not yet handled: " << *CE << "\n"; - llvm_unreachable(0); - } - } else { - llvm_unreachable("Unknown constant pointer!"); - } - return 0; -} - -/// getNodeForConstantPointerTarget - Return the node POINTED TO by the -/// specified constant pointer. -unsigned Andersens::getNodeForConstantPointerTarget(Constant *C) { - assert(C->getType()->isPointerTy() && "Not a constant pointer!"); - - if (isa<ConstantPointerNull>(C)) - return NullObject; - else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) - return getObject(GV); - else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { - switch (CE->getOpcode()) { - case Instruction::GetElementPtr: - return getNodeForConstantPointerTarget(CE->getOperand(0)); - case Instruction::IntToPtr: - return UniversalSet; - case Instruction::BitCast: - return getNodeForConstantPointerTarget(CE->getOperand(0)); - default: - errs() << "Constant Expr not yet handled: " << *CE << "\n"; - llvm_unreachable(0); - } - } else { - llvm_unreachable("Unknown constant pointer!"); - } - return 0; -} - -/// AddGlobalInitializerConstraints - Add inclusion constraints for the memory -/// object N, which contains values indicated by C. -void Andersens::AddGlobalInitializerConstraints(unsigned NodeIndex, - Constant *C) { - if (C->getType()->isSingleValueType()) { - if (C->getType()->isPointerTy()) - Constraints.push_back(Constraint(Constraint::Copy, NodeIndex, - getNodeForConstantPointer(C))); - } else if (C->isNullValue()) { - Constraints.push_back(Constraint(Constraint::Copy, NodeIndex, - NullObject)); - return; - } else if (!isa<UndefValue>(C)) { - // If this is an array or struct, include constraints for each element. - assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C)); - for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) - AddGlobalInitializerConstraints(NodeIndex, - cast<Constant>(C->getOperand(i))); - } -} - -/// AddConstraintsForNonInternalLinkage - If this function does not have -/// internal linkage, realize that we can't trust anything passed into or -/// returned by this function. -void Andersens::AddConstraintsForNonInternalLinkage(Function *F) { - for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) - if (I->getType()->isPointerTy()) - // If this is an argument of an externally accessible function, the - // incoming pointer might point to anything. - Constraints.push_back(Constraint(Constraint::Copy, getNode(I), - UniversalSet)); -} - -/// AddConstraintsForCall - If this is a call to a "known" function, add the -/// constraints and return true. If this is a call to an unknown function, -/// return false. -bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) { - assert(F->isDeclaration() && "Not an external function!"); - - // These functions don't induce any points-to constraints. - if (F->getName() == "atoi" || F->getName() == "atof" || - F->getName() == "atol" || F->getName() == "atoll" || - F->getName() == "remove" || F->getName() == "unlink" || - F->getName() == "rename" || F->getName() == "memcmp" || - F->getName() == "llvm.memset" || - F->getName() == "strcmp" || F->getName() == "strncmp" || - F->getName() == "execl" || F->getName() == "execlp" || - F->getName() == "execle" || F->getName() == "execv" || - F->getName() == "execvp" || F->getName() == "chmod" || - F->getName() == "puts" || F->getName() == "write" || - F->getName() == "open" || F->getName() == "create" || - F->getName() == "truncate" || F->getName() == "chdir" || - F->getName() == "mkdir" || F->getName() == "rmdir" || - F->getName() == "read" || F->getName() == "pipe" || - F->getName() == "wait" || F->getName() == "time" || - F->getName() == "stat" || F->getName() == "fstat" || - F->getName() == "lstat" || F->getName() == "strtod" || - F->getName() == "strtof" || F->getName() == "strtold" || - F->getName() == "fopen" || F->getName() == "fdopen" || - F->getName() == "freopen" || - F->getName() == "fflush" || F->getName() == "feof" || - F->getName() == "fileno" || F->getName() == "clearerr" || - F->getName() == "rewind" || F->getName() == "ftell" || - F->getName() == "ferror" || F->getName() == "fgetc" || - F->getName() == "fgetc" || F->getName() == "_IO_getc" || - F->getName() == "fwrite" || F->getName() == "fread" || - F->getName() == "fgets" || F->getName() == "ungetc" || - F->getName() == "fputc" || - F->getName() == "fputs" || F->getName() == "putc" || - F->getName() == "ftell" || F->getName() == "rewind" || - F->getName() == "_IO_putc" || F->getName() == "fseek" || - F->getName() == "fgetpos" || F->getName() == "fsetpos" || - F->getName() == "printf" || F->getName() == "fprintf" || - F->getName() == "sprintf" || F->getName() == "vprintf" || - F->getName() == "vfprintf" || F->getName() == "vsprintf" || - F->getName() == "scanf" || F->getName() == "fscanf" || - F->getName() == "sscanf" || F->getName() == "__assert_fail" || - F->getName() == "modf") - return true; - - - // These functions do induce points-to edges. - if (F->getName() == "llvm.memcpy" || - F->getName() == "llvm.memmove" || - F->getName() == "memmove") { - - const FunctionType *FTy = F->getFunctionType(); - if (FTy->getNumParams() > 1 && - FTy->getParamType(0)->isPointerTy() && - FTy->getParamType(1)->isPointerTy()) { - - // *Dest = *Src, which requires an artificial graph node to represent the - // constraint. It is broken up into *Dest = temp, temp = *Src - unsigned FirstArg = getNode(CS.getArgument(0)); - unsigned SecondArg = getNode(CS.getArgument(1)); - unsigned TempArg = GraphNodes.size(); - GraphNodes.push_back(Node()); - Constraints.push_back(Constraint(Constraint::Store, - FirstArg, TempArg)); - Constraints.push_back(Constraint(Constraint::Load, - TempArg, SecondArg)); - // In addition, Dest = Src - Constraints.push_back(Constraint(Constraint::Copy, - FirstArg, SecondArg)); - return true; - } - } - - // Result = Arg0 - if (F->getName() == "realloc" || F->getName() == "strchr" || - F->getName() == "strrchr" || F->getName() == "strstr" || - F->getName() == "strtok") { - const FunctionType *FTy = F->getFunctionType(); - if (FTy->getNumParams() > 0 && - FTy->getParamType(0)->isPointerTy()) { - Constraints.push_back(Constraint(Constraint::Copy, - getNode(CS.getInstruction()), - getNode(CS.getArgument(0)))); - return true; - } - } - - return false; -} - - - -/// AnalyzeUsesOfFunction - Look at all of the users of the specified function. -/// If this is used by anything complex (i.e., the address escapes), return -/// true. -bool Andersens::AnalyzeUsesOfFunction(Value *V) { - - if (!V->getType()->isPointerTy()) return true; - - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (isa<LoadInst>(*UI)) { - return false; - } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { - if (V == SI->getOperand(1)) { - return false; - } else if (SI->getOperand(1)) { - return true; // Storing the pointer - } - } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { - if (AnalyzeUsesOfFunction(GEP)) return true; - } else if (isFreeCall(*UI)) { - return false; - } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { - // Make sure that this is just the function being called, not that it is - // passing into the function. - for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) - if (CI->getOperand(i) == V) return true; - } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { - // Make sure that this is just the function being called, not that it is - // passing into the function. - for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i) - if (II->getOperand(i) == V) return true; - } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { - if (CE->getOpcode() == Instruction::GetElementPtr || - CE->getOpcode() == Instruction::BitCast) { - if (AnalyzeUsesOfFunction(CE)) - return true; - } else { - return true; - } - } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) { - if (!isa<ConstantPointerNull>(ICI->getOperand(1))) - return true; // Allow comparison against null. - } else { - return true; - } - return false; -} - -/// CollectConstraints - This stage scans the program, adding a constraint to -/// the Constraints list for each instruction in the program that induces a -/// constraint, and setting up the initial points-to graph. -/// -void Andersens::CollectConstraints(Module &M) { - // First, the universal set points to itself. - Constraints.push_back(Constraint(Constraint::AddressOf, UniversalSet, - UniversalSet)); - Constraints.push_back(Constraint(Constraint::Store, UniversalSet, - UniversalSet)); - - // Next, the null pointer points to the null object. - Constraints.push_back(Constraint(Constraint::AddressOf, NullPtr, NullObject)); - - // Next, add any constraints on global variables and their initializers. - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) { - // Associate the address of the global object as pointing to the memory for - // the global: &G = <G memory> - unsigned ObjectIndex = getObject(I); - Node *Object = &GraphNodes[ObjectIndex]; - Object->setValue(I); - Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(*I), - ObjectIndex)); - - if (I->hasDefinitiveInitializer()) { - AddGlobalInitializerConstraints(ObjectIndex, I->getInitializer()); - } else { - // If it doesn't have an initializer (i.e. it's defined in another - // translation unit), it points to the universal set. - Constraints.push_back(Constraint(Constraint::Copy, ObjectIndex, - UniversalSet)); - } - } - - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - // Set up the return value node. - if (F->getFunctionType()->getReturnType()->isPointerTy()) - GraphNodes[getReturnNode(F)].setValue(F); - if (F->getFunctionType()->isVarArg()) - GraphNodes[getVarargNode(F)].setValue(F); - - // Set up incoming argument nodes. - for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); - I != E; ++I) - if (I->getType()->isPointerTy()) - getNodeValue(*I); - - // At some point we should just add constraints for the escaping functions - // at solve time, but this slows down solving. For now, we simply mark - // address taken functions as escaping and treat them as external. - if (!F->hasLocalLinkage() || AnalyzeUsesOfFunction(F)) - AddConstraintsForNonInternalLinkage(F); - - if (!F->isDeclaration()) { - // Scan the function body, creating a memory object for each heap/stack - // allocation in the body of the function and a node to represent all - // pointer values defined by instructions and used as operands. - visit(F); - } else { - // External functions that return pointers return the universal set. - if (F->getFunctionType()->getReturnType()->isPointerTy()) - Constraints.push_back(Constraint(Constraint::Copy, - getReturnNode(F), - UniversalSet)); - - // Any pointers that are passed into the function have the universal set - // stored into them. - for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); - I != E; ++I) - if (I->getType()->isPointerTy()) { - // Pointers passed into external functions could have anything stored - // through them. - Constraints.push_back(Constraint(Constraint::Store, getNode(I), - UniversalSet)); - // Memory objects passed into external function calls can have the - // universal set point to them. -#if FULL_UNIVERSAL - Constraints.push_back(Constraint(Constraint::Copy, - UniversalSet, - getNode(I))); -#else - Constraints.push_back(Constraint(Constraint::Copy, - getNode(I), - UniversalSet)); -#endif - } - - // If this is an external varargs function, it can also store pointers - // into any pointers passed through the varargs section. - if (F->getFunctionType()->isVarArg()) - Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F), - UniversalSet)); - } - } - NumConstraints += Constraints.size(); -} - - -void Andersens::visitInstruction(Instruction &I) { -#ifdef NDEBUG - return; // This function is just a big assert. -#endif - if (isa<BinaryOperator>(I)) - return; - // Most instructions don't have any effect on pointer values. - switch (I.getOpcode()) { - case Instruction::Br: - case Instruction::Switch: - case Instruction::Unwind: - case Instruction::Unreachable: - case Instruction::ICmp: - case Instruction::FCmp: - return; - default: - // Is this something we aren't handling yet? - errs() << "Unknown instruction: " << I; - llvm_unreachable(0); - } -} - -void Andersens::visitAllocaInst(AllocaInst &I) { - visitAlloc(I); -} - -void Andersens::visitAlloc(Instruction &I) { - unsigned ObjectIndex = getObject(&I); - GraphNodes[ObjectIndex].setValue(&I); - Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(I), - ObjectIndex)); -} - -void Andersens::visitReturnInst(ReturnInst &RI) { - if (RI.getNumOperands() && RI.getOperand(0)->getType()->isPointerTy()) - // return V --> <Copy/retval{F}/v> - Constraints.push_back(Constraint(Constraint::Copy, - getReturnNode(RI.getParent()->getParent()), - getNode(RI.getOperand(0)))); -} - -void Andersens::visitLoadInst(LoadInst &LI) { - if (LI.getType()->isPointerTy()) - // P1 = load P2 --> <Load/P1/P2> - Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI), - getNode(LI.getOperand(0)))); -} - -void Andersens::visitStoreInst(StoreInst &SI) { - if (SI.getOperand(0)->getType()->isPointerTy()) - // store P1, P2 --> <Store/P2/P1> - Constraints.push_back(Constraint(Constraint::Store, - getNode(SI.getOperand(1)), - getNode(SI.getOperand(0)))); -} - -void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) { - // P1 = getelementptr P2, ... --> <Copy/P1/P2> - Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP), - getNode(GEP.getOperand(0)))); -} - -void Andersens::visitPHINode(PHINode &PN) { - if (PN.getType()->isPointerTy()) { - unsigned PNN = getNodeValue(PN); - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - // P1 = phi P2, P3 --> <Copy/P1/P2>, <Copy/P1/P3>, ... - Constraints.push_back(Constraint(Constraint::Copy, PNN, - getNode(PN.getIncomingValue(i)))); - } -} - -void Andersens::visitCastInst(CastInst &CI) { - Value *Op = CI.getOperand(0); - if (CI.getType()->isPointerTy()) { - if (Op->getType()->isPointerTy()) { - // P1 = cast P2 --> <Copy/P1/P2> - Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), - getNode(CI.getOperand(0)))); - } else { - // P1 = cast int --> <Copy/P1/Univ> -#if 0 - Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), - UniversalSet)); -#else - getNodeValue(CI); -#endif - } - } else if (Op->getType()->isPointerTy()) { - // int = cast P1 --> <Copy/Univ/P1> -#if 0 - Constraints.push_back(Constraint(Constraint::Copy, - UniversalSet, - getNode(CI.getOperand(0)))); -#else - getNode(CI.getOperand(0)); -#endif - } -} - -void Andersens::visitSelectInst(SelectInst &SI) { - if (SI.getType()->isPointerTy()) { - unsigned SIN = getNodeValue(SI); - // P1 = select C, P2, P3 ---> <Copy/P1/P2>, <Copy/P1/P3> - Constraints.push_back(Constraint(Constraint::Copy, SIN, - getNode(SI.getOperand(1)))); - Constraints.push_back(Constraint(Constraint::Copy, SIN, - getNode(SI.getOperand(2)))); - } -} - -void Andersens::visitVAArg(VAArgInst &I) { - llvm_unreachable("vaarg not handled yet!"); -} - -/// AddConstraintsForCall - Add constraints for a call with actual arguments -/// specified by CS to the function specified by F. Note that the types of -/// arguments might not match up in the case where this is an indirect call and -/// the function pointer has been casted. If this is the case, do something -/// reasonable. -void Andersens::AddConstraintsForCall(CallSite CS, Function *F) { - Value *CallValue = CS.getCalledValue(); - bool IsDeref = F == NULL; - - // If this is a call to an external function, try to handle it directly to get - // some taste of context sensitivity. - if (F && F->isDeclaration() && AddConstraintsForExternalCall(CS, F)) - return; - - if (CS.getType()->isPointerTy()) { - unsigned CSN = getNode(CS.getInstruction()); - if (!F || F->getFunctionType()->getReturnType()->isPointerTy()) { - if (IsDeref) - Constraints.push_back(Constraint(Constraint::Load, CSN, - getNode(CallValue), CallReturnPos)); - else - Constraints.push_back(Constraint(Constraint::Copy, CSN, - getNode(CallValue) + CallReturnPos)); - } else { - // If the function returns a non-pointer value, handle this just like we - // treat a nonpointer cast to pointer. - Constraints.push_back(Constraint(Constraint::Copy, CSN, - UniversalSet)); - } - } else if (F && F->getFunctionType()->getReturnType()->isPointerTy()) { -#if FULL_UNIVERSAL - Constraints.push_back(Constraint(Constraint::Copy, - UniversalSet, - getNode(CallValue) + CallReturnPos)); -#else - Constraints.push_back(Constraint(Constraint::Copy, - getNode(CallValue) + CallReturnPos, - UniversalSet)); -#endif - - - } - - CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end(); - bool external = !F || F->isDeclaration(); - if (F) { - // Direct Call - Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); - for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) - { -#if !FULL_UNIVERSAL - if (external && (*ArgI)->getType()->isPointerTy()) - { - // Add constraint that ArgI can now point to anything due to - // escaping, as can everything it points to. The second portion of - // this should be taken care of by universal = *universal - Constraints.push_back(Constraint(Constraint::Copy, - getNode(*ArgI), - UniversalSet)); - } -#endif - if (AI->getType()->isPointerTy()) { - if ((*ArgI)->getType()->isPointerTy()) { - // Copy the actual argument into the formal argument. - Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), - getNode(*ArgI))); - } else { - Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), - UniversalSet)); - } - } else if ((*ArgI)->getType()->isPointerTy()) { -#if FULL_UNIVERSAL - Constraints.push_back(Constraint(Constraint::Copy, - UniversalSet, - getNode(*ArgI))); -#else - Constraints.push_back(Constraint(Constraint::Copy, - getNode(*ArgI), - UniversalSet)); -#endif - } - } - } else { - //Indirect Call - unsigned ArgPos = CallFirstArgPos; - for (; ArgI != ArgE; ++ArgI) { - if ((*ArgI)->getType()->isPointerTy()) { - // Copy the actual argument into the formal argument. - Constraints.push_back(Constraint(Constraint::Store, - getNode(CallValue), - getNode(*ArgI), ArgPos++)); - } else { - Constraints.push_back(Constraint(Constraint::Store, - getNode (CallValue), - UniversalSet, ArgPos++)); - } - } - } - // Copy all pointers passed through the varargs section to the varargs node. - if (F && F->getFunctionType()->isVarArg()) - for (; ArgI != ArgE; ++ArgI) - if ((*ArgI)->getType()->isPointerTy()) - Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F), - getNode(*ArgI))); - // If more arguments are passed in than we track, just drop them on the floor. -} - -void Andersens::visitCallSite(CallSite CS) { - if (CS.getType()->isPointerTy()) - getNodeValue(*CS.getInstruction()); - - if (Function *F = CS.getCalledFunction()) { - AddConstraintsForCall(CS, F); - } else { - AddConstraintsForCall(CS, NULL); - } -} - -//===----------------------------------------------------------------------===// -// Constraint Solving Phase -//===----------------------------------------------------------------------===// - -/// intersects - Return true if the points-to set of this node intersects -/// with the points-to set of the specified node. -bool Andersens::Node::intersects(Node *N) const { - return PointsTo->intersects(N->PointsTo); -} - -/// intersectsIgnoring - Return true if the points-to set of this node -/// intersects with the points-to set of the specified node on any nodes -/// except for the specified node to ignore. -bool Andersens::Node::intersectsIgnoring(Node *N, unsigned Ignoring) const { - // TODO: If we are only going to call this with the same value for Ignoring, - // we should move the special values out of the points-to bitmap. - bool WeHadIt = PointsTo->test(Ignoring); - bool NHadIt = N->PointsTo->test(Ignoring); - bool Result = false; - if (WeHadIt) - PointsTo->reset(Ignoring); - if (NHadIt) - N->PointsTo->reset(Ignoring); - Result = PointsTo->intersects(N->PointsTo); - if (WeHadIt) - PointsTo->set(Ignoring); - if (NHadIt) - N->PointsTo->set(Ignoring); - return Result; -} - - -/// Clump together address taken variables so that the points-to sets use up -/// less space and can be operated on faster. - -void Andersens::ClumpAddressTaken() { -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa-renumber" - std::vector<unsigned> Translate; - std::vector<Node> NewGraphNodes; - - Translate.resize(GraphNodes.size()); - unsigned NewPos = 0; - - for (unsigned i = 0; i < Constraints.size(); ++i) { - Constraint &C = Constraints[i]; - if (C.Type == Constraint::AddressOf) { - GraphNodes[C.Src].AddressTaken = true; - } - } - for (unsigned i = 0; i < NumberSpecialNodes; ++i) { - unsigned Pos = NewPos++; - Translate[i] = Pos; - NewGraphNodes.push_back(GraphNodes[i]); - DEBUG(dbgs() << "Renumbering node " << i << " to node " << Pos << "\n"); - } - - // I believe this ends up being faster than making two vectors and splicing - // them. - for (unsigned i = NumberSpecialNodes; i < GraphNodes.size(); ++i) { - if (GraphNodes[i].AddressTaken) { - unsigned Pos = NewPos++; - Translate[i] = Pos; - NewGraphNodes.push_back(GraphNodes[i]); - DEBUG(dbgs() << "Renumbering node " << i << " to node " << Pos << "\n"); - } - } - - for (unsigned i = NumberSpecialNodes; i < GraphNodes.size(); ++i) { - if (!GraphNodes[i].AddressTaken) { - unsigned Pos = NewPos++; - Translate[i] = Pos; - NewGraphNodes.push_back(GraphNodes[i]); - DEBUG(dbgs() << "Renumbering node " << i << " to node " << Pos << "\n"); - } - } - - for (DenseMap<Value*, unsigned>::iterator Iter = ValueNodes.begin(); - Iter != ValueNodes.end(); - ++Iter) - Iter->second = Translate[Iter->second]; - - for (DenseMap<Value*, unsigned>::iterator Iter = ObjectNodes.begin(); - Iter != ObjectNodes.end(); - ++Iter) - Iter->second = Translate[Iter->second]; - - for (DenseMap<Function*, unsigned>::iterator Iter = ReturnNodes.begin(); - Iter != ReturnNodes.end(); - ++Iter) - Iter->second = Translate[Iter->second]; - - for (DenseMap<Function*, unsigned>::iterator Iter = VarargNodes.begin(); - Iter != VarargNodes.end(); - ++Iter) - Iter->second = Translate[Iter->second]; - - for (unsigned i = 0; i < Constraints.size(); ++i) { - Constraint &C = Constraints[i]; - C.Src = Translate[C.Src]; - C.Dest = Translate[C.Dest]; - } - - GraphNodes.swap(NewGraphNodes); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa" -} - -/// The technique used here is described in "Exploiting Pointer and Location -/// Equivalence to Optimize Pointer Analysis. In the 14th International Static -/// Analysis Symposium (SAS), August 2007." It is known as the "HVN" algorithm, -/// and is equivalent to value numbering the collapsed constraint graph without -/// evaluating unions. This is used as a pre-pass to HU in order to resolve -/// first order pointer dereferences and speed up/reduce memory usage of HU. -/// Running both is equivalent to HRU without the iteration -/// HVN in more detail: -/// Imagine the set of constraints was simply straight line code with no loops -/// (we eliminate cycles, so there are no loops), such as: -/// E = &D -/// E = &C -/// E = F -/// F = G -/// G = F -/// Applying value numbering to this code tells us: -/// G == F == E -/// -/// For HVN, this is as far as it goes. We assign new value numbers to every -/// "address node", and every "reference node". -/// To get the optimal result for this, we use a DFS + SCC (since all nodes in a -/// cycle must have the same value number since the = operation is really -/// inclusion, not overwrite), and value number nodes we receive points-to sets -/// before we value our own node. -/// The advantage of HU over HVN is that HU considers the inclusion property, so -/// that if you have -/// E = &D -/// E = &C -/// E = F -/// F = G -/// F = &D -/// G = F -/// HU will determine that G == F == E. HVN will not, because it cannot prove -/// that the points to information ends up being the same because they all -/// receive &D from E anyway. - -void Andersens::HVN() { - DEBUG(dbgs() << "Beginning HVN\n"); - // Build a predecessor graph. This is like our constraint graph with the - // edges going in the opposite direction, and there are edges for all the - // constraints, instead of just copy constraints. We also build implicit - // edges for constraints are implied but not explicit. I.E for the constraint - // a = &b, we add implicit edges *a = b. This helps us capture more cycles - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - if (C.Type == Constraint::AddressOf) { - GraphNodes[C.Src].AddressTaken = true; - GraphNodes[C.Src].Direct = false; - - // Dest = &src edge - unsigned AdrNode = C.Src + FirstAdrNode; - if (!GraphNodes[C.Dest].PredEdges) - GraphNodes[C.Dest].PredEdges = new SparseBitVector<>; - GraphNodes[C.Dest].PredEdges->set(AdrNode); - - // *Dest = src edge - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].ImplicitPredEdges) - GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>; - GraphNodes[RefNode].ImplicitPredEdges->set(C.Src); - } else if (C.Type == Constraint::Load) { - if (C.Offset == 0) { - // dest = *src edge - if (!GraphNodes[C.Dest].PredEdges) - GraphNodes[C.Dest].PredEdges = new SparseBitVector<>; - GraphNodes[C.Dest].PredEdges->set(C.Src + FirstRefNode); - } else { - GraphNodes[C.Dest].Direct = false; - } - } else if (C.Type == Constraint::Store) { - if (C.Offset == 0) { - // *dest = src edge - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].PredEdges) - GraphNodes[RefNode].PredEdges = new SparseBitVector<>; - GraphNodes[RefNode].PredEdges->set(C.Src); - } - } else { - // Dest = Src edge and *Dest = *Src edge - if (!GraphNodes[C.Dest].PredEdges) - GraphNodes[C.Dest].PredEdges = new SparseBitVector<>; - GraphNodes[C.Dest].PredEdges->set(C.Src); - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].ImplicitPredEdges) - GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>; - GraphNodes[RefNode].ImplicitPredEdges->set(C.Src + FirstRefNode); - } - } - PEClass = 1; - // Do SCC finding first to condense our predecessor graph - DFSNumber = 0; - Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0); - Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false); - Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false); - - for (unsigned i = 0; i < FirstRefNode; ++i) { - unsigned Node = VSSCCRep[i]; - if (!Node2Visited[Node]) - HVNValNum(Node); - } - for (BitVectorMap::iterator Iter = Set2PEClass.begin(); - Iter != Set2PEClass.end(); - ++Iter) - delete Iter->first; - Set2PEClass.clear(); - Node2DFS.clear(); - Node2Deleted.clear(); - Node2Visited.clear(); - DEBUG(dbgs() << "Finished HVN\n"); - -} - -/// This is the workhorse of HVN value numbering. We combine SCC finding at the -/// same time because it's easy. -void Andersens::HVNValNum(unsigned NodeIndex) { - unsigned MyDFS = DFSNumber++; - Node *N = &GraphNodes[NodeIndex]; - Node2Visited[NodeIndex] = true; - Node2DFS[NodeIndex] = MyDFS; - - // First process all our explicit edges - if (N->PredEdges) - for (SparseBitVector<>::iterator Iter = N->PredEdges->begin(); - Iter != N->PredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - if (!Node2Deleted[j]) { - if (!Node2Visited[j]) - HVNValNum(j); - if (Node2DFS[NodeIndex] > Node2DFS[j]) - Node2DFS[NodeIndex] = Node2DFS[j]; - } - } - - // Now process all the implicit edges - if (N->ImplicitPredEdges) - for (SparseBitVector<>::iterator Iter = N->ImplicitPredEdges->begin(); - Iter != N->ImplicitPredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - if (!Node2Deleted[j]) { - if (!Node2Visited[j]) - HVNValNum(j); - if (Node2DFS[NodeIndex] > Node2DFS[j]) - Node2DFS[NodeIndex] = Node2DFS[j]; - } - } - - // See if we found any cycles - if (MyDFS == Node2DFS[NodeIndex]) { - while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) { - unsigned CycleNodeIndex = SCCStack.top(); - Node *CycleNode = &GraphNodes[CycleNodeIndex]; - VSSCCRep[CycleNodeIndex] = NodeIndex; - // Unify the nodes - N->Direct &= CycleNode->Direct; - - if (CycleNode->PredEdges) { - if (!N->PredEdges) - N->PredEdges = new SparseBitVector<>; - *(N->PredEdges) |= CycleNode->PredEdges; - delete CycleNode->PredEdges; - CycleNode->PredEdges = NULL; - } - if (CycleNode->ImplicitPredEdges) { - if (!N->ImplicitPredEdges) - N->ImplicitPredEdges = new SparseBitVector<>; - *(N->ImplicitPredEdges) |= CycleNode->ImplicitPredEdges; - delete CycleNode->ImplicitPredEdges; - CycleNode->ImplicitPredEdges = NULL; - } - - SCCStack.pop(); - } - - Node2Deleted[NodeIndex] = true; - - if (!N->Direct) { - GraphNodes[NodeIndex].PointerEquivLabel = PEClass++; - return; - } - - // Collect labels of successor nodes - bool AllSame = true; - unsigned First = ~0; - SparseBitVector<> *Labels = new SparseBitVector<>; - bool Used = false; - - if (N->PredEdges) - for (SparseBitVector<>::iterator Iter = N->PredEdges->begin(); - Iter != N->PredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - unsigned Label = GraphNodes[j].PointerEquivLabel; - // Ignore labels that are equal to us or non-pointers - if (j == NodeIndex || Label == 0) - continue; - if (First == (unsigned)~0) - First = Label; - else if (First != Label) - AllSame = false; - Labels->set(Label); - } - - // We either have a non-pointer, a copy of an existing node, or a new node. - // Assign the appropriate pointer equivalence label. - if (Labels->empty()) { - GraphNodes[NodeIndex].PointerEquivLabel = 0; - } else if (AllSame) { - GraphNodes[NodeIndex].PointerEquivLabel = First; - } else { - GraphNodes[NodeIndex].PointerEquivLabel = Set2PEClass[Labels]; - if (GraphNodes[NodeIndex].PointerEquivLabel == 0) { - unsigned EquivClass = PEClass++; - Set2PEClass[Labels] = EquivClass; - GraphNodes[NodeIndex].PointerEquivLabel = EquivClass; - Used = true; - } - } - if (!Used) - delete Labels; - } else { - SCCStack.push(NodeIndex); - } -} - -/// The technique used here is described in "Exploiting Pointer and Location -/// Equivalence to Optimize Pointer Analysis. In the 14th International Static -/// Analysis Symposium (SAS), August 2007." It is known as the "HU" algorithm, -/// and is equivalent to value numbering the collapsed constraint graph -/// including evaluating unions. -void Andersens::HU() { - DEBUG(dbgs() << "Beginning HU\n"); - // Build a predecessor graph. This is like our constraint graph with the - // edges going in the opposite direction, and there are edges for all the - // constraints, instead of just copy constraints. We also build implicit - // edges for constraints are implied but not explicit. I.E for the constraint - // a = &b, we add implicit edges *a = b. This helps us capture more cycles - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - if (C.Type == Constraint::AddressOf) { - GraphNodes[C.Src].AddressTaken = true; - GraphNodes[C.Src].Direct = false; - - GraphNodes[C.Dest].PointsTo->set(C.Src); - // *Dest = src edge - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].ImplicitPredEdges) - GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>; - GraphNodes[RefNode].ImplicitPredEdges->set(C.Src); - GraphNodes[C.Src].PointedToBy->set(C.Dest); - } else if (C.Type == Constraint::Load) { - if (C.Offset == 0) { - // dest = *src edge - if (!GraphNodes[C.Dest].PredEdges) - GraphNodes[C.Dest].PredEdges = new SparseBitVector<>; - GraphNodes[C.Dest].PredEdges->set(C.Src + FirstRefNode); - } else { - GraphNodes[C.Dest].Direct = false; - } - } else if (C.Type == Constraint::Store) { - if (C.Offset == 0) { - // *dest = src edge - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].PredEdges) - GraphNodes[RefNode].PredEdges = new SparseBitVector<>; - GraphNodes[RefNode].PredEdges->set(C.Src); - } - } else { - // Dest = Src edge and *Dest = *Src edg - if (!GraphNodes[C.Dest].PredEdges) - GraphNodes[C.Dest].PredEdges = new SparseBitVector<>; - GraphNodes[C.Dest].PredEdges->set(C.Src); - unsigned RefNode = C.Dest + FirstRefNode; - if (!GraphNodes[RefNode].ImplicitPredEdges) - GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>; - GraphNodes[RefNode].ImplicitPredEdges->set(C.Src + FirstRefNode); - } - } - PEClass = 1; - // Do SCC finding first to condense our predecessor graph - DFSNumber = 0; - Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0); - Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false); - Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false); - - for (unsigned i = 0; i < FirstRefNode; ++i) { - if (FindNode(i) == i) { - unsigned Node = VSSCCRep[i]; - if (!Node2Visited[Node]) - Condense(Node); - } - } - - // Reset tables for actual labeling - Node2DFS.clear(); - Node2Visited.clear(); - Node2Deleted.clear(); - // Pre-grow our densemap so that we don't get really bad behavior - Set2PEClass.resize(GraphNodes.size()); - - // Visit the condensed graph and generate pointer equivalence labels. - Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false); - for (unsigned i = 0; i < FirstRefNode; ++i) { - if (FindNode(i) == i) { - unsigned Node = VSSCCRep[i]; - if (!Node2Visited[Node]) - HUValNum(Node); - } - } - // PEClass nodes will be deleted by the deleting of N->PointsTo in our caller. - Set2PEClass.clear(); - DEBUG(dbgs() << "Finished HU\n"); -} - - -/// Implementation of standard Tarjan SCC algorithm as modified by Nuutilla. -void Andersens::Condense(unsigned NodeIndex) { - unsigned MyDFS = DFSNumber++; - Node *N = &GraphNodes[NodeIndex]; - Node2Visited[NodeIndex] = true; - Node2DFS[NodeIndex] = MyDFS; - - // First process all our explicit edges - if (N->PredEdges) - for (SparseBitVector<>::iterator Iter = N->PredEdges->begin(); - Iter != N->PredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - if (!Node2Deleted[j]) { - if (!Node2Visited[j]) - Condense(j); - if (Node2DFS[NodeIndex] > Node2DFS[j]) - Node2DFS[NodeIndex] = Node2DFS[j]; - } - } - - // Now process all the implicit edges - if (N->ImplicitPredEdges) - for (SparseBitVector<>::iterator Iter = N->ImplicitPredEdges->begin(); - Iter != N->ImplicitPredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - if (!Node2Deleted[j]) { - if (!Node2Visited[j]) - Condense(j); - if (Node2DFS[NodeIndex] > Node2DFS[j]) - Node2DFS[NodeIndex] = Node2DFS[j]; - } - } - - // See if we found any cycles - if (MyDFS == Node2DFS[NodeIndex]) { - while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) { - unsigned CycleNodeIndex = SCCStack.top(); - Node *CycleNode = &GraphNodes[CycleNodeIndex]; - VSSCCRep[CycleNodeIndex] = NodeIndex; - // Unify the nodes - N->Direct &= CycleNode->Direct; - - *(N->PointsTo) |= CycleNode->PointsTo; - delete CycleNode->PointsTo; - CycleNode->PointsTo = NULL; - if (CycleNode->PredEdges) { - if (!N->PredEdges) - N->PredEdges = new SparseBitVector<>; - *(N->PredEdges) |= CycleNode->PredEdges; - delete CycleNode->PredEdges; - CycleNode->PredEdges = NULL; - } - if (CycleNode->ImplicitPredEdges) { - if (!N->ImplicitPredEdges) - N->ImplicitPredEdges = new SparseBitVector<>; - *(N->ImplicitPredEdges) |= CycleNode->ImplicitPredEdges; - delete CycleNode->ImplicitPredEdges; - CycleNode->ImplicitPredEdges = NULL; - } - SCCStack.pop(); - } - - Node2Deleted[NodeIndex] = true; - - // Set up number of incoming edges for other nodes - if (N->PredEdges) - for (SparseBitVector<>::iterator Iter = N->PredEdges->begin(); - Iter != N->PredEdges->end(); - ++Iter) - ++GraphNodes[VSSCCRep[*Iter]].NumInEdges; - } else { - SCCStack.push(NodeIndex); - } -} - -void Andersens::HUValNum(unsigned NodeIndex) { - Node *N = &GraphNodes[NodeIndex]; - Node2Visited[NodeIndex] = true; - - // Eliminate dereferences of non-pointers for those non-pointers we have - // already identified. These are ref nodes whose non-ref node: - // 1. Has already been visited determined to point to nothing (and thus, a - // dereference of it must point to nothing) - // 2. Any direct node with no predecessor edges in our graph and with no - // points-to set (since it can't point to anything either, being that it - // receives no points-to sets and has none). - if (NodeIndex >= FirstRefNode) { - unsigned j = VSSCCRep[FindNode(NodeIndex - FirstRefNode)]; - if ((Node2Visited[j] && !GraphNodes[j].PointerEquivLabel) - || (GraphNodes[j].Direct && !GraphNodes[j].PredEdges - && GraphNodes[j].PointsTo->empty())){ - return; - } - } - // Process all our explicit edges - if (N->PredEdges) - for (SparseBitVector<>::iterator Iter = N->PredEdges->begin(); - Iter != N->PredEdges->end(); - ++Iter) { - unsigned j = VSSCCRep[*Iter]; - if (!Node2Visited[j]) - HUValNum(j); - - // If this edge turned out to be the same as us, or got no pointer - // equivalence label (and thus points to nothing) , just decrement our - // incoming edges and continue. - if (j == NodeIndex || GraphNodes[j].PointerEquivLabel == 0) { - --GraphNodes[j].NumInEdges; - continue; - } - - *(N->PointsTo) |= GraphNodes[j].PointsTo; - - // If we didn't end up storing this in the hash, and we're done with all - // the edges, we don't need the points-to set anymore. - --GraphNodes[j].NumInEdges; - if (!GraphNodes[j].NumInEdges && !GraphNodes[j].StoredInHash) { - delete GraphNodes[j].PointsTo; - GraphNodes[j].PointsTo = NULL; - } - } - // If this isn't a direct node, generate a fresh variable. - if (!N->Direct) { - N->PointsTo->set(FirstRefNode + NodeIndex); - } - - // See If we have something equivalent to us, if not, generate a new - // equivalence class. - if (N->PointsTo->empty()) { - delete N->PointsTo; - N->PointsTo = NULL; - } else { - if (N->Direct) { - N->PointerEquivLabel = Set2PEClass[N->PointsTo]; - if (N->PointerEquivLabel == 0) { - unsigned EquivClass = PEClass++; - N->StoredInHash = true; - Set2PEClass[N->PointsTo] = EquivClass; - N->PointerEquivLabel = EquivClass; - } - } else { - N->PointerEquivLabel = PEClass++; - } - } -} - -/// Rewrite our list of constraints so that pointer equivalent nodes are -/// replaced by their the pointer equivalence class representative. -void Andersens::RewriteConstraints() { - std::vector<Constraint> NewConstraints; - DenseSet<Constraint, ConstraintKeyInfo> Seen; - - PEClass2Node.clear(); - PENLEClass2Node.clear(); - - // We may have from 1 to Graphnodes + 1 equivalence classes. - PEClass2Node.insert(PEClass2Node.begin(), GraphNodes.size() + 1, -1); - PENLEClass2Node.insert(PENLEClass2Node.begin(), GraphNodes.size() + 1, -1); - - // Rewrite constraints, ignoring non-pointer constraints, uniting equivalent - // nodes, and rewriting constraints to use the representative nodes. - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - unsigned RHSNode = FindNode(C.Src); - unsigned LHSNode = FindNode(C.Dest); - unsigned RHSLabel = GraphNodes[VSSCCRep[RHSNode]].PointerEquivLabel; - unsigned LHSLabel = GraphNodes[VSSCCRep[LHSNode]].PointerEquivLabel; - - // First we try to eliminate constraints for things we can prove don't point - // to anything. - if (LHSLabel == 0) { - DEBUG(PrintNode(&GraphNodes[LHSNode])); - DEBUG(dbgs() << " is a non-pointer, ignoring constraint.\n"); - continue; - } - if (RHSLabel == 0) { - DEBUG(PrintNode(&GraphNodes[RHSNode])); - DEBUG(dbgs() << " is a non-pointer, ignoring constraint.\n"); - continue; - } - // This constraint may be useless, and it may become useless as we translate - // it. - if (C.Src == C.Dest && C.Type == Constraint::Copy) - continue; - - C.Src = FindEquivalentNode(RHSNode, RHSLabel); - C.Dest = FindEquivalentNode(FindNode(LHSNode), LHSLabel); - if ((C.Src == C.Dest && C.Type == Constraint::Copy) - || Seen.count(C)) - continue; - - Seen.insert(C); - NewConstraints.push_back(C); - } - Constraints.swap(NewConstraints); - PEClass2Node.clear(); -} - -/// See if we have a node that is pointer equivalent to the one being asked -/// about, and if so, unite them and return the equivalent node. Otherwise, -/// return the original node. -unsigned Andersens::FindEquivalentNode(unsigned NodeIndex, - unsigned NodeLabel) { - if (!GraphNodes[NodeIndex].AddressTaken) { - if (PEClass2Node[NodeLabel] != -1) { - // We found an existing node with the same pointer label, so unify them. - // We specifically request that Union-By-Rank not be used so that - // PEClass2Node[NodeLabel] U= NodeIndex and not the other way around. - return UniteNodes(PEClass2Node[NodeLabel], NodeIndex, false); - } else { - PEClass2Node[NodeLabel] = NodeIndex; - PENLEClass2Node[NodeLabel] = NodeIndex; - } - } else if (PENLEClass2Node[NodeLabel] == -1) { - PENLEClass2Node[NodeLabel] = NodeIndex; - } - - return NodeIndex; -} - -void Andersens::PrintLabels() const { - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - if (i < FirstRefNode) { - PrintNode(&GraphNodes[i]); - } else if (i < FirstAdrNode) { - DEBUG(dbgs() << "REF("); - PrintNode(&GraphNodes[i-FirstRefNode]); - DEBUG(dbgs() <<")"); - } else { - DEBUG(dbgs() << "ADR("); - PrintNode(&GraphNodes[i-FirstAdrNode]); - DEBUG(dbgs() <<")"); - } - - DEBUG(dbgs() << " has pointer label " << GraphNodes[i].PointerEquivLabel - << " and SCC rep " << VSSCCRep[i] - << " and is " << (GraphNodes[i].Direct ? "Direct" : "Not direct") - << "\n"); - } -} - -/// The technique used here is described in "The Ant and the -/// Grasshopper: Fast and Accurate Pointer Analysis for Millions of -/// Lines of Code. In Programming Language Design and Implementation -/// (PLDI), June 2007." It is known as the "HCD" (Hybrid Cycle -/// Detection) algorithm. It is called a hybrid because it performs an -/// offline analysis and uses its results during the solving (online) -/// phase. This is just the offline portion; the results of this -/// operation are stored in SDT and are later used in SolveContraints() -/// and UniteNodes(). -void Andersens::HCD() { - DEBUG(dbgs() << "Starting HCD.\n"); - HCDSCCRep.resize(GraphNodes.size()); - - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - GraphNodes[i].Edges = new SparseBitVector<>; - HCDSCCRep[i] = i; - } - - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - assert (C.Src < GraphNodes.size() && C.Dest < GraphNodes.size()); - if (C.Type == Constraint::AddressOf) { - continue; - } else if (C.Type == Constraint::Load) { - if( C.Offset == 0 ) - GraphNodes[C.Dest].Edges->set(C.Src + FirstRefNode); - } else if (C.Type == Constraint::Store) { - if( C.Offset == 0 ) - GraphNodes[C.Dest + FirstRefNode].Edges->set(C.Src); - } else { - GraphNodes[C.Dest].Edges->set(C.Src); - } - } - - Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0); - Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false); - Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false); - SDT.insert(SDT.begin(), GraphNodes.size() / 2, -1); - - DFSNumber = 0; - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - unsigned Node = HCDSCCRep[i]; - if (!Node2Deleted[Node]) - Search(Node); - } - - for (unsigned i = 0; i < GraphNodes.size(); ++i) - if (GraphNodes[i].Edges != NULL) { - delete GraphNodes[i].Edges; - GraphNodes[i].Edges = NULL; - } - - while( !SCCStack.empty() ) - SCCStack.pop(); - - Node2DFS.clear(); - Node2Visited.clear(); - Node2Deleted.clear(); - HCDSCCRep.clear(); - DEBUG(dbgs() << "HCD complete.\n"); -} - -// Component of HCD: -// Use Nuutila's variant of Tarjan's algorithm to detect -// Strongly-Connected Components (SCCs). For non-trivial SCCs -// containing ref nodes, insert the appropriate information in SDT. -void Andersens::Search(unsigned Node) { - unsigned MyDFS = DFSNumber++; - - Node2Visited[Node] = true; - Node2DFS[Node] = MyDFS; - - for (SparseBitVector<>::iterator Iter = GraphNodes[Node].Edges->begin(), - End = GraphNodes[Node].Edges->end(); - Iter != End; - ++Iter) { - unsigned J = HCDSCCRep[*Iter]; - assert(GraphNodes[J].isRep() && "Debug check; must be representative"); - if (!Node2Deleted[J]) { - if (!Node2Visited[J]) - Search(J); - if (Node2DFS[Node] > Node2DFS[J]) - Node2DFS[Node] = Node2DFS[J]; - } - } - - if( MyDFS != Node2DFS[Node] ) { - SCCStack.push(Node); - return; - } - - // This node is the root of a SCC, so process it. - // - // If the SCC is "non-trivial" (not a singleton) and contains a reference - // node, we place this SCC into SDT. We unite the nodes in any case. - if (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) { - SparseBitVector<> SCC; - - SCC.set(Node); - - bool Ref = (Node >= FirstRefNode); - - Node2Deleted[Node] = true; - - do { - unsigned P = SCCStack.top(); SCCStack.pop(); - Ref |= (P >= FirstRefNode); - SCC.set(P); - HCDSCCRep[P] = Node; - } while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS); - - if (Ref) { - unsigned Rep = SCC.find_first(); - assert(Rep < FirstRefNode && "The SCC didn't have a non-Ref node!"); - - SparseBitVector<>::iterator i = SCC.begin(); - - // Skip over the non-ref nodes - while( *i < FirstRefNode ) - ++i; - - while( i != SCC.end() ) - SDT[ (*i++) - FirstRefNode ] = Rep; - } - } -} - - -/// Optimize the constraints by performing offline variable substitution and -/// other optimizations. -void Andersens::OptimizeConstraints() { - DEBUG(dbgs() << "Beginning constraint optimization\n"); - - SDTActive = false; - - // Function related nodes need to stay in the same relative position and can't - // be location equivalent. - for (std::map<unsigned, unsigned>::iterator Iter = MaxK.begin(); - Iter != MaxK.end(); - ++Iter) { - for (unsigned i = Iter->first; - i != Iter->first + Iter->second; - ++i) { - GraphNodes[i].AddressTaken = true; - GraphNodes[i].Direct = false; - } - } - - ClumpAddressTaken(); - FirstRefNode = GraphNodes.size(); - FirstAdrNode = FirstRefNode + GraphNodes.size(); - GraphNodes.insert(GraphNodes.end(), 2 * GraphNodes.size(), - Node(false)); - VSSCCRep.resize(GraphNodes.size()); - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - VSSCCRep[i] = i; - } - HVN(); - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - Node *N = &GraphNodes[i]; - delete N->PredEdges; - N->PredEdges = NULL; - delete N->ImplicitPredEdges; - N->ImplicitPredEdges = NULL; - } -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa-labels" - DEBUG(PrintLabels()); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa" - RewriteConstraints(); - // Delete the adr nodes. - GraphNodes.resize(FirstRefNode * 2); - - // Now perform HU - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - Node *N = &GraphNodes[i]; - if (FindNode(i) == i) { - N->PointsTo = new SparseBitVector<>; - N->PointedToBy = new SparseBitVector<>; - // Reset our labels - } - VSSCCRep[i] = i; - N->PointerEquivLabel = 0; - } - HU(); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa-labels" - DEBUG(PrintLabels()); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa" - RewriteConstraints(); - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - if (FindNode(i) == i) { - Node *N = &GraphNodes[i]; - delete N->PointsTo; - N->PointsTo = NULL; - delete N->PredEdges; - N->PredEdges = NULL; - delete N->ImplicitPredEdges; - N->ImplicitPredEdges = NULL; - delete N->PointedToBy; - N->PointedToBy = NULL; - } - } - - // perform Hybrid Cycle Detection (HCD) - HCD(); - SDTActive = true; - - // No longer any need for the upper half of GraphNodes (for ref nodes). - GraphNodes.erase(GraphNodes.begin() + FirstRefNode, GraphNodes.end()); - - // HCD complete. - - DEBUG(dbgs() << "Finished constraint optimization\n"); - FirstRefNode = 0; - FirstAdrNode = 0; -} - -/// Unite pointer but not location equivalent variables, now that the constraint -/// graph is built. -void Andersens::UnitePointerEquivalences() { - DEBUG(dbgs() << "Uniting remaining pointer equivalences\n"); - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - if (GraphNodes[i].AddressTaken && GraphNodes[i].isRep()) { - unsigned Label = GraphNodes[i].PointerEquivLabel; - - if (Label && PENLEClass2Node[Label] != -1) - UniteNodes(i, PENLEClass2Node[Label]); - } - } - DEBUG(dbgs() << "Finished remaining pointer equivalences\n"); - PENLEClass2Node.clear(); -} - -/// Create the constraint graph used for solving points-to analysis. -/// -void Andersens::CreateConstraintGraph() { - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - assert (C.Src < GraphNodes.size() && C.Dest < GraphNodes.size()); - if (C.Type == Constraint::AddressOf) - GraphNodes[C.Dest].PointsTo->set(C.Src); - else if (C.Type == Constraint::Load) - GraphNodes[C.Src].Constraints.push_back(C); - else if (C.Type == Constraint::Store) - GraphNodes[C.Dest].Constraints.push_back(C); - else if (C.Offset != 0) - GraphNodes[C.Src].Constraints.push_back(C); - else - GraphNodes[C.Src].Edges->set(C.Dest); - } -} - -// Perform DFS and cycle detection. -bool Andersens::QueryNode(unsigned Node) { - assert(GraphNodes[Node].isRep() && "Querying a non-rep node"); - unsigned OurDFS = ++DFSNumber; - SparseBitVector<> ToErase; - SparseBitVector<> NewEdges; - Tarjan2DFS[Node] = OurDFS; - - // Changed denotes a change from a recursive call that we will bubble up. - // Merged is set if we actually merge a node ourselves. - bool Changed = false, Merged = false; - - for (SparseBitVector<>::iterator bi = GraphNodes[Node].Edges->begin(); - bi != GraphNodes[Node].Edges->end(); - ++bi) { - unsigned RepNode = FindNode(*bi); - // If this edge points to a non-representative node but we are - // already planning to add an edge to its representative, we have no - // need for this edge anymore. - if (RepNode != *bi && NewEdges.test(RepNode)){ - ToErase.set(*bi); - continue; - } - - // Continue about our DFS. - if (!Tarjan2Deleted[RepNode]){ - if (Tarjan2DFS[RepNode] == 0) { - Changed |= QueryNode(RepNode); - // May have been changed by QueryNode - RepNode = FindNode(RepNode); - } - if (Tarjan2DFS[RepNode] < Tarjan2DFS[Node]) - Tarjan2DFS[Node] = Tarjan2DFS[RepNode]; - } - - // We may have just discovered that this node is part of a cycle, in - // which case we can also erase it. - if (RepNode != *bi) { - ToErase.set(*bi); - NewEdges.set(RepNode); - } - } - - GraphNodes[Node].Edges->intersectWithComplement(ToErase); - GraphNodes[Node].Edges |= NewEdges; - - // If this node is a root of a non-trivial SCC, place it on our - // worklist to be processed. - if (OurDFS == Tarjan2DFS[Node]) { - while (!SCCStack.empty() && Tarjan2DFS[SCCStack.top()] >= OurDFS) { - Node = UniteNodes(Node, SCCStack.top()); - - SCCStack.pop(); - Merged = true; - } - Tarjan2Deleted[Node] = true; - - if (Merged) - NextWL->insert(&GraphNodes[Node]); - } else { - SCCStack.push(Node); - } - - return(Changed | Merged); -} - -/// SolveConstraints - This stage iteratively processes the constraints list -/// propagating constraints (adding edges to the Nodes in the points-to graph) -/// until a fixed point is reached. -/// -/// We use a variant of the technique called "Lazy Cycle Detection", which is -/// described in "The Ant and the Grasshopper: Fast and Accurate Pointer -/// Analysis for Millions of Lines of Code. In Programming Language Design and -/// Implementation (PLDI), June 2007." -/// The paper describes performing cycle detection one node at a time, which can -/// be expensive if there are no cycles, but there are long chains of nodes that -/// it heuristically believes are cycles (because it will DFS from each node -/// without state from previous nodes). -/// Instead, we use the heuristic to build a worklist of nodes to check, then -/// cycle detect them all at the same time to do this more cheaply. This -/// catches cycles slightly later than the original technique did, but does it -/// make significantly cheaper. - -void Andersens::SolveConstraints() { - CurrWL = &w1; - NextWL = &w2; - - OptimizeConstraints(); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa-constraints" - DEBUG(PrintConstraints()); -#undef DEBUG_TYPE -#define DEBUG_TYPE "anders-aa" - - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - Node *N = &GraphNodes[i]; - N->PointsTo = new SparseBitVector<>; - N->OldPointsTo = new SparseBitVector<>; - N->Edges = new SparseBitVector<>; - } - CreateConstraintGraph(); - UnitePointerEquivalences(); - assert(SCCStack.empty() && "SCC Stack should be empty by now!"); - Node2DFS.clear(); - Node2Deleted.clear(); - Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0); - Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false); - DFSNumber = 0; - DenseSet<Constraint, ConstraintKeyInfo> Seen; - DenseSet<std::pair<unsigned,unsigned>, PairKeyInfo> EdgesChecked; - - // Order graph and add initial nodes to work list. - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - Node *INode = &GraphNodes[i]; - - // Add to work list if it's a representative and can contribute to the - // calculation right now. - if (INode->isRep() && !INode->PointsTo->empty() - && (!INode->Edges->empty() || !INode->Constraints.empty())) { - INode->Stamp(); - CurrWL->insert(INode); - } - } - std::queue<unsigned int> TarjanWL; -#if !FULL_UNIVERSAL - // "Rep and special variables" - in order for HCD to maintain conservative - // results when !FULL_UNIVERSAL, we need to treat the special variables in - // the same way that the !FULL_UNIVERSAL tweak does throughout the rest of - // the analysis - it's ok to add edges from the special nodes, but never - // *to* the special nodes. - std::vector<unsigned int> RSV; -#endif - while( !CurrWL->empty() ) { - DEBUG(dbgs() << "Starting iteration #" << ++NumIters << "\n"); - - Node* CurrNode; - unsigned CurrNodeIndex; - - // Actual cycle checking code. We cycle check all of the lazy cycle - // candidates from the last iteration in one go. - if (!TarjanWL.empty()) { - DFSNumber = 0; - - Tarjan2DFS.clear(); - Tarjan2Deleted.clear(); - while (!TarjanWL.empty()) { - unsigned int ToTarjan = TarjanWL.front(); - TarjanWL.pop(); - if (!Tarjan2Deleted[ToTarjan] - && GraphNodes[ToTarjan].isRep() - && Tarjan2DFS[ToTarjan] == 0) - QueryNode(ToTarjan); - } - } - - // Add to work list if it's a representative and can contribute to the - // calculation right now. - while( (CurrNode = CurrWL->pop()) != NULL ) { - CurrNodeIndex = CurrNode - &GraphNodes[0]; - CurrNode->Stamp(); - - - // Figure out the changed points to bits - SparseBitVector<> CurrPointsTo; - CurrPointsTo.intersectWithComplement(CurrNode->PointsTo, - CurrNode->OldPointsTo); - if (CurrPointsTo.empty()) - continue; - - *(CurrNode->OldPointsTo) |= CurrPointsTo; - - // Check the offline-computed equivalencies from HCD. - bool SCC = false; - unsigned Rep; - - if (SDT[CurrNodeIndex] >= 0) { - SCC = true; - Rep = FindNode(SDT[CurrNodeIndex]); - -#if !FULL_UNIVERSAL - RSV.clear(); -#endif - for (SparseBitVector<>::iterator bi = CurrPointsTo.begin(); - bi != CurrPointsTo.end(); ++bi) { - unsigned Node = FindNode(*bi); -#if !FULL_UNIVERSAL - if (Node < NumberSpecialNodes) { - RSV.push_back(Node); - continue; - } -#endif - Rep = UniteNodes(Rep,Node); - } -#if !FULL_UNIVERSAL - RSV.push_back(Rep); -#endif - - NextWL->insert(&GraphNodes[Rep]); - - if ( ! CurrNode->isRep() ) - continue; - } - - Seen.clear(); - - /* Now process the constraints for this node. */ - for (std::list<Constraint>::iterator li = CurrNode->Constraints.begin(); - li != CurrNode->Constraints.end(); ) { - li->Src = FindNode(li->Src); - li->Dest = FindNode(li->Dest); - - // Delete redundant constraints - if( Seen.count(*li) ) { - std::list<Constraint>::iterator lk = li; li++; - - CurrNode->Constraints.erase(lk); - ++NumErased; - continue; - } - Seen.insert(*li); - - // Src and Dest will be the vars we are going to process. - // This may look a bit ugly, but what it does is allow us to process - // both store and load constraints with the same code. - // Load constraints say that every member of our RHS solution has K - // added to it, and that variable gets an edge to LHS. We also union - // RHS+K's solution into the LHS solution. - // Store constraints say that every member of our LHS solution has K - // added to it, and that variable gets an edge from RHS. We also union - // RHS's solution into the LHS+K solution. - unsigned *Src; - unsigned *Dest; - unsigned K = li->Offset; - unsigned CurrMember; - if (li->Type == Constraint::Load) { - Src = &CurrMember; - Dest = &li->Dest; - } else if (li->Type == Constraint::Store) { - Src = &li->Src; - Dest = &CurrMember; - } else { - // TODO Handle offseted copy constraint - li++; - continue; - } - - // See if we can use Hybrid Cycle Detection (that is, check - // if it was a statically detected offline equivalence that - // involves pointers; if so, remove the redundant constraints). - if( SCC && K == 0 ) { -#if FULL_UNIVERSAL - CurrMember = Rep; - - if (GraphNodes[*Src].Edges->test_and_set(*Dest)) - if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo)) - NextWL->insert(&GraphNodes[*Dest]); -#else - for (unsigned i=0; i < RSV.size(); ++i) { - CurrMember = RSV[i]; - - if (*Dest < NumberSpecialNodes) - continue; - if (GraphNodes[*Src].Edges->test_and_set(*Dest)) - if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo)) - NextWL->insert(&GraphNodes[*Dest]); - } -#endif - // since all future elements of the points-to set will be - // equivalent to the current ones, the complex constraints - // become redundant. - // - std::list<Constraint>::iterator lk = li; li++; -#if !FULL_UNIVERSAL - // In this case, we can still erase the constraints when the - // elements of the points-to sets are referenced by *Dest, - // but not when they are referenced by *Src (i.e. for a Load - // constraint). This is because if another special variable is - // put into the points-to set later, we still need to add the - // new edge from that special variable. - if( lk->Type != Constraint::Load) -#endif - GraphNodes[CurrNodeIndex].Constraints.erase(lk); - } else { - const SparseBitVector<> &Solution = CurrPointsTo; - - for (SparseBitVector<>::iterator bi = Solution.begin(); - bi != Solution.end(); - ++bi) { - CurrMember = *bi; - - // Need to increment the member by K since that is where we are - // supposed to copy to/from. Note that in positive weight cycles, - // which occur in address taking of fields, K can go past - // MaxK[CurrMember] elements, even though that is all it could point - // to. - if (K > 0 && K > MaxK[CurrMember]) - continue; - else - CurrMember = FindNode(CurrMember + K); - - // Add an edge to the graph, so we can just do regular - // bitmap ior next time. It may also let us notice a cycle. -#if !FULL_UNIVERSAL - if (*Dest < NumberSpecialNodes) - continue; -#endif - if (GraphNodes[*Src].Edges->test_and_set(*Dest)) - if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo)) - NextWL->insert(&GraphNodes[*Dest]); - - } - li++; - } - } - SparseBitVector<> NewEdges; - SparseBitVector<> ToErase; - - // Now all we have left to do is propagate points-to info along the - // edges, erasing the redundant edges. - for (SparseBitVector<>::iterator bi = CurrNode->Edges->begin(); - bi != CurrNode->Edges->end(); - ++bi) { - - unsigned DestVar = *bi; - unsigned Rep = FindNode(DestVar); - - // If we ended up with this node as our destination, or we've already - // got an edge for the representative, delete the current edge. - if (Rep == CurrNodeIndex || - (Rep != DestVar && NewEdges.test(Rep))) { - ToErase.set(DestVar); - continue; - } - - std::pair<unsigned,unsigned> edge(CurrNodeIndex,Rep); - - // This is where we do lazy cycle detection. - // If this is a cycle candidate (equal points-to sets and this - // particular edge has not been cycle-checked previously), add to the - // list to check for cycles on the next iteration. - if (!EdgesChecked.count(edge) && - *(GraphNodes[Rep].PointsTo) == *(CurrNode->PointsTo)) { - EdgesChecked.insert(edge); - TarjanWL.push(Rep); - } - // Union the points-to sets into the dest -#if !FULL_UNIVERSAL - if (Rep >= NumberSpecialNodes) -#endif - if (GraphNodes[Rep].PointsTo |= CurrPointsTo) { - NextWL->insert(&GraphNodes[Rep]); - } - // If this edge's destination was collapsed, rewrite the edge. - if (Rep != DestVar) { - ToErase.set(DestVar); - NewEdges.set(Rep); - } - } - CurrNode->Edges->intersectWithComplement(ToErase); - CurrNode->Edges |= NewEdges; - } - - // Switch to other work list. - WorkList* t = CurrWL; CurrWL = NextWL; NextWL = t; - } - - - Node2DFS.clear(); - Node2Deleted.clear(); - for (unsigned i = 0; i < GraphNodes.size(); ++i) { - Node *N = &GraphNodes[i]; - delete N->OldPointsTo; - delete N->Edges; - } - SDTActive = false; - SDT.clear(); -} - -//===----------------------------------------------------------------------===// -// Union-Find -//===----------------------------------------------------------------------===// - -// Unite nodes First and Second, returning the one which is now the -// representative node. First and Second are indexes into GraphNodes -unsigned Andersens::UniteNodes(unsigned First, unsigned Second, - bool UnionByRank) { - assert (First < GraphNodes.size() && Second < GraphNodes.size() && - "Attempting to merge nodes that don't exist"); - - Node *FirstNode = &GraphNodes[First]; - Node *SecondNode = &GraphNodes[Second]; - - assert (SecondNode->isRep() && FirstNode->isRep() && - "Trying to unite two non-representative nodes!"); - if (First == Second) - return First; - - if (UnionByRank) { - int RankFirst = (int) FirstNode ->NodeRep; - int RankSecond = (int) SecondNode->NodeRep; - - // Rank starts at -1 and gets decremented as it increases. - // Translation: higher rank, lower NodeRep value, which is always negative. - if (RankFirst > RankSecond) { - unsigned t = First; First = Second; Second = t; - Node* tp = FirstNode; FirstNode = SecondNode; SecondNode = tp; - } else if (RankFirst == RankSecond) { - FirstNode->NodeRep = (unsigned) (RankFirst - 1); - } - } - - SecondNode->NodeRep = First; -#if !FULL_UNIVERSAL - if (First >= NumberSpecialNodes) -#endif - if (FirstNode->PointsTo && SecondNode->PointsTo) - FirstNode->PointsTo |= *(SecondNode->PointsTo); - if (FirstNode->Edges && SecondNode->Edges) - FirstNode->Edges |= *(SecondNode->Edges); - if (!SecondNode->Constraints.empty()) - FirstNode->Constraints.splice(FirstNode->Constraints.begin(), - SecondNode->Constraints); - if (FirstNode->OldPointsTo) { - delete FirstNode->OldPointsTo; - FirstNode->OldPointsTo = new SparseBitVector<>; - } - - // Destroy interesting parts of the merged-from node. - delete SecondNode->OldPointsTo; - delete SecondNode->Edges; - delete SecondNode->PointsTo; - SecondNode->Edges = NULL; - SecondNode->PointsTo = NULL; - SecondNode->OldPointsTo = NULL; - - NumUnified++; - DEBUG(dbgs() << "Unified Node "); - DEBUG(PrintNode(FirstNode)); - DEBUG(dbgs() << " and Node "); - DEBUG(PrintNode(SecondNode)); - DEBUG(dbgs() << "\n"); - - if (SDTActive) - if (SDT[Second] >= 0) { - if (SDT[First] < 0) - SDT[First] = SDT[Second]; - else { - UniteNodes( FindNode(SDT[First]), FindNode(SDT[Second]) ); - First = FindNode(First); - } - } - - return First; -} - -// Find the index into GraphNodes of the node representing Node, performing -// path compression along the way -unsigned Andersens::FindNode(unsigned NodeIndex) { - assert (NodeIndex < GraphNodes.size() - && "Attempting to find a node that can't exist"); - Node *N = &GraphNodes[NodeIndex]; - if (N->isRep()) - return NodeIndex; - else - return (N->NodeRep = FindNode(N->NodeRep)); -} - -// Find the index into GraphNodes of the node representing Node, -// don't perform path compression along the way (for Print) -unsigned Andersens::FindNode(unsigned NodeIndex) const { - assert (NodeIndex < GraphNodes.size() - && "Attempting to find a node that can't exist"); - const Node *N = &GraphNodes[NodeIndex]; - if (N->isRep()) - return NodeIndex; - else - return FindNode(N->NodeRep); -} - -//===----------------------------------------------------------------------===// -// Debugging Output -//===----------------------------------------------------------------------===// - -void Andersens::PrintNode(const Node *N) const { - if (N == &GraphNodes[UniversalSet]) { - dbgs() << "<universal>"; - return; - } else if (N == &GraphNodes[NullPtr]) { - dbgs() << "<nullptr>"; - return; - } else if (N == &GraphNodes[NullObject]) { - dbgs() << "<null>"; - return; - } - if (!N->getValue()) { - dbgs() << "artificial" << (intptr_t) N; - return; - } - - assert(N->getValue() != 0 && "Never set node label!"); - Value *V = N->getValue(); - if (Function *F = dyn_cast<Function>(V)) { - if (F->getFunctionType()->getReturnType()->isPointerTy() && - N == &GraphNodes[getReturnNode(F)]) { - dbgs() << F->getName() << ":retval"; - return; - } else if (F->getFunctionType()->isVarArg() && - N == &GraphNodes[getVarargNode(F)]) { - dbgs() << F->getName() << ":vararg"; - return; - } - } - - if (Instruction *I = dyn_cast<Instruction>(V)) - dbgs() << I->getParent()->getParent()->getName() << ":"; - else if (Argument *Arg = dyn_cast<Argument>(V)) - dbgs() << Arg->getParent()->getName() << ":"; - - if (V->hasName()) - dbgs() << V->getName(); - else - dbgs() << "(unnamed)"; - - if (isa<GlobalValue>(V) || isa<AllocaInst>(V) || isMalloc(V)) - if (N == &GraphNodes[getObject(V)]) - dbgs() << "<mem>"; -} -void Andersens::PrintConstraint(const Constraint &C) const { - if (C.Type == Constraint::Store) { - dbgs() << "*"; - if (C.Offset != 0) - dbgs() << "("; - } - PrintNode(&GraphNodes[C.Dest]); - if (C.Type == Constraint::Store && C.Offset != 0) - dbgs() << " + " << C.Offset << ")"; - dbgs() << " = "; - if (C.Type == Constraint::Load) { - dbgs() << "*"; - if (C.Offset != 0) - dbgs() << "("; - } - else if (C.Type == Constraint::AddressOf) - dbgs() << "&"; - PrintNode(&GraphNodes[C.Src]); - if (C.Offset != 0 && C.Type != Constraint::Store) - dbgs() << " + " << C.Offset; - if (C.Type == Constraint::Load && C.Offset != 0) - dbgs() << ")"; - dbgs() << "\n"; -} - -void Andersens::PrintConstraints() const { - dbgs() << "Constraints:\n"; - - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) - PrintConstraint(Constraints[i]); -} - -void Andersens::PrintPointsToGraph() const { - dbgs() << "Points-to graph:\n"; - for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) { - const Node *N = &GraphNodes[i]; - if (FindNode(i) != i) { - PrintNode(N); - dbgs() << "\t--> same as "; - PrintNode(&GraphNodes[FindNode(i)]); - dbgs() << "\n"; - } else { - dbgs() << "[" << (N->PointsTo->count()) << "] "; - PrintNode(N); - dbgs() << "\t--> "; - - bool first = true; - for (SparseBitVector<>::iterator bi = N->PointsTo->begin(); - bi != N->PointsTo->end(); - ++bi) { - if (!first) - dbgs() << ", "; - PrintNode(&GraphNodes[*bi]); - first = false; - } - dbgs() << "\n"; - } - } -} |