X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FAndersens.cpp;h=cc7ad7e7a779096ac07ab62e167fd0b1abc3fcfb;hb=3a3f163ba620c771238130905b873826af33b022;hp=54dfd7458d1257ff7a7cfd6f3e3caeca06662bac;hpb=df9b7bc09019fa42682d8905505c4a58888dc147;p=oota-llvm.git diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp index 54dfd7458d1..cc7ad7e7a77 100644 --- a/lib/Analysis/IPA/Andersens.cpp +++ b/lib/Analysis/IPA/Andersens.cpp @@ -1,25 +1,23 @@ //===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // -// This file defines a very simple implementation of Andersen's interprocedural -// alias analysis. This implementation does not include any of the fancy -// features that make Andersen's reasonably efficient (like cycle elimination or -// variable substitution), but it should be useful for getting precision -// numbers and can be extended in the future. +// This file defines an implementation of Andersen's interprocedural alias +// analysis // // In pointer analysis terms, this is a subset-based, flow-insensitive, -// field-insensitive, and context-insensitive algorithm pointer algorithm. +// field-sensitive, and context-insensitive algorithm pointer algorithm. // // This algorithm is implemented as three stages: // 1. Object identification. // 2. Inclusion constraint identification. -// 3. Inclusion constraint solving. +// 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 @@ -29,24 +27,28 @@ // 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. +// 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 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. // // The inclusion constraint solving phase iteratively propagates the inclusion // constraints until a fixed point is reached. This is an O(N^3) algorithm. // -// In the initial pass, all indirect function calls are completely ignored. As -// the analysis discovers new targets of function pointers, it iteratively -// resolves a precise (and conservative) call graph. Also related, this -// analysis initially assumes that all internal functions have known incoming -// pointers. If we find that an internal function's address escapes outside of -// the program, we update this assumption. +// 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: -// This implementation of Andersen's algorithm is extremely slow. To make it -// scale reasonably well, the inclusion constraints could be sorted (easy), -// offline variable substitution would be a huge win (straight-forward), and -// online cycle elimination (trickier) might help as well. -// +// Offline detection of online cycles. Use of BDD's. //===----------------------------------------------------------------------===// #define DEBUG_TYPE "anders-aa" @@ -55,35 +57,202 @@ #include "llvm/Instructions.h" #include "llvm/Module.h" #include "llvm/Pass.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/InstIterator.h" #include "llvm/Support/InstVisitor.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "Support/Debug.h" -#include "Support/Statistic.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/ADT/DenseSet.h" +#include #include +#include +#include +#include +#include + +// 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; +STATISTIC(NumIters , "Number of iterations to reach convergence"); +STATISTIC(NumConstraints, "Number of constraints"); +STATISTIC(NumNodes , "Number of nodes"); +STATISTIC(NumUnified , "Number of variables unified"); +STATISTIC(NumErased , "Number of redundant constraints erased"); namespace { - Statistic<> - NumIters("anders-aa", "Number of iterations to reach convergence"); - Statistic<> - NumConstraints("anders-aa", "Number of constraints"); - Statistic<> - NumNodes("anders-aa", "Number of nodes"); - Statistic<> - NumEscapingFunctions("anders-aa", "Number of internal functions that escape"); - Statistic<> - NumIndirectCallees("anders-aa", "Number of indirect callees found"); - - class Andersens : public Pass, public AliasAnalysis, - private InstVisitor { - /// Node class - This class is used to represent a memory object in the - /// program, and is the primitive used to build the points-to graph. - class Node { - std::vector Pointees; - Value *Val; + const unsigned SelfRep = (unsigned)-1; + const unsigned Unvisited = (unsigned)-1; + // Position of the function return node relative to the function node. + const unsigned CallReturnPos = 1; + // Position of the function call node relative to the function node. + const unsigned CallFirstArgPos = 2; + + struct BitmapKeyInfo { + static inline SparseBitVector<> *getEmptyKey() { + return reinterpret_cast *>(-1); + } + static inline SparseBitVector<> *getTombstoneKey() { + return reinterpret_cast *>(-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; + } + + static bool isPod() { return true; } + }; + + class VISIBILITY_HIDDEN Andersens : public ModulePass, public AliasAnalysis, + private InstVisitor { + 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 getEmptyKey() { + return std::make_pair(~0UL, ~0UL); + } + static inline std::pair getTombstoneKey() { + return std::make_pair(~0UL - 1, ~0UL - 1); + } + static unsigned getHashValue(const std::pair &P) { + return P.first ^ P.second; + } + static unsigned isEqual(const std::pair &LHS, + const std::pair &RHS) { + return LHS == RHS; + } + }; + + struct ConstraintKeyInfo { + static inline Constraint getEmptyKey() { + return Constraint(Constraint::Copy, ~0UL, ~0UL, ~0UL); + } + static inline Constraint getTombstoneKey() { + return Constraint(Constraint::Copy, ~0UL - 1, ~0UL - 1, ~0UL - 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 unsigned Counter; + public: - Node() : Val(0) {} + Value *Val; + SparseBitVector<> *Edges; + SparseBitVector<> *PointsTo; + SparseBitVector<> *OldPointsTo; + std::list 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; + + 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; @@ -91,23 +260,14 @@ namespace { } /// getValue - Return the LLVM value corresponding to this node. + /// Value *getValue() const { return Val; } - typedef std::vector::const_iterator iterator; - iterator begin() const { return Pointees.begin(); } - iterator end() const { return Pointees.end(); } - /// 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(Node *N) { - std::vector::iterator I = std::lower_bound(Pointees.begin(), - Pointees.end(), - N); - if (I != Pointees.end() && *I == N) - return false; - Pointees.insert(I, N); - return true; + bool addPointerTo(unsigned Node) { + return PointsTo->test_and_set(Node); } /// intersects - Return true if the points-to set of this node intersects @@ -117,12 +277,61 @@ namespace { /// 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, Node *Ignoring) const; + bool intersectsIgnoring(Node *N, unsigned) const; - // Constraint application methods. - bool copyFrom(Node *N); - bool loadFrom(Node *N); - bool storeThrough(Node *N); + // Timestamp a node (used for work list prioritization) + void Stamp() { + Timestamp = Counter++; + } + + bool isRep() { + 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 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 @@ -132,57 +341,30 @@ namespace { /// ValueNodes - This map indicates the Node that a particular Value* is /// represented by. This contains entries for all pointers. - std::map ValueNodes; + DenseMap ValueNodes; /// ObjectNodes - This map contains entries for each memory object in the - /// program: globals, alloca's and mallocs. - std::map ObjectNodes; + /// program: globals, alloca's and mallocs. + DenseMap ObjectNodes; /// ReturnNodes - This map contains an entry for each function in the /// program that returns a value. - std::map ReturnNodes; + DenseMap 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. - std::map VarargNodes; + DenseMap VarargNodes; - /// 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", and - /// 'store' for statements like "*A = B". - struct Constraint { - enum ConstraintType { Copy, Load, Store } Type; - Node *Dest, *Src; - Constraint(ConstraintType Ty, Node *D, Node *S) - : Type(Ty), Dest(D), Src(S) {} - }; - /// Constraints - This vector contains a list of all of the constraints /// identified by the program. std::vector Constraints; - /// EscapingInternalFunctions - This set contains all of the internal - /// functions that are found to escape from the program. If the address of - /// an internal function is passed to an external function or otherwise - /// escapes from the analyzed portion of the program, we must assume that - /// any pointer arguments can alias the universal node. This set keeps - /// track of those functions we are assuming to escape so far. - std::set EscapingInternalFunctions; - - /// IndirectCalls - This contains a list of all of the indirect call sites - /// in the program. Since the call graph is iteratively discovered, we may - /// need to add constraints to our graph as we find new targets of function - /// pointers. - std::vector IndirectCalls; - - /// IndirectCallees - For each call site in the indirect calls list, keep - /// track of the callees that we have discovered so far. As the analysis - /// proceeds, more callees are discovered, until the call graph finally - /// stabilizes. - std::map > IndirectCallees; + // Map from graph node to maximum K value that is allowed (for functions, + // this is equivalent to the number of arguments + CallFirstArgPos) + std::map MaxK; /// This enum defines the GraphNodes indices that correspond to important /// fixed sets. @@ -190,14 +372,66 @@ namespace { UniversalSet = 0, NullPtr = 1, NullObject = 2, + NumberSpecialNodes }; - + // Stack for Tarjan's + std::stack SCCStack; + // Map from Graph Node to DFS number + std::vector Node2DFS; + // Map from Graph Node to Deleted from graph. + std::vector Node2Deleted; + // Same as Node Maps, but implemented as std::map because it is faster to + // clear + std::map Tarjan2DFS; + std::map 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 VSSCCRep; + // Mapping from node to whether we have visited it during SCC finding yet. + std::vector 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 *, 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 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 PENLEClass2Node; + public: - bool run(Module &M) { + static char ID; + Andersens() : ModulePass((intptr_t)&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()); @@ -206,8 +440,7 @@ namespace { ObjectNodes.clear(); ReturnNodes.clear(); VarargNodes.clear(); - EscapingInternalFunctions.clear(); - std::vector().swap(Constraints); + std::vector().swap(Constraints); return false; } @@ -230,9 +463,11 @@ namespace { //------------------------------------------------ // 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); void getMustAliases(Value *P, std::vector &RetVals); bool pointsToConstantMemory(const Value *P); @@ -249,64 +484,87 @@ namespace { private: /// getNode - Return the node corresponding to the specified pointer scalar. /// - Node *getNode(Value *V) { + unsigned getNode(Value *V) { if (Constant *C = dyn_cast(V)) if (!isa(C)) return getNodeForConstantPointer(C); - std::map::iterator I = ValueNodes.find(V); + DenseMap::iterator I = ValueNodes.find(V); if (I == ValueNodes.end()) { +#ifndef NDEBUG V->dump(); - assert(I != ValueNodes.end() && - "Value does not have a node in the points-to graph!"); +#endif + assert(0 && "Value does not have a node in the points-to graph!"); } - return &GraphNodes[I->second]; + return I->second; } - + /// getObject - Return the node corresponding to the memory object for the /// specified global or allocation instruction. - Node *getObject(Value *V) { - std::map::iterator I = ObjectNodes.find(V); + unsigned getObject(Value *V) { + DenseMap::iterator I = ObjectNodes.find(V); assert(I != ObjectNodes.end() && "Value does not have an object in the points-to graph!"); - return &GraphNodes[I->second]; + return I->second; } /// getReturnNode - Return the node representing the return value for the /// specified function. - Node *getReturnNode(Function *F) { - std::map::iterator I = ReturnNodes.find(F); + unsigned getReturnNode(Function *F) { + DenseMap::iterator I = ReturnNodes.find(F); assert(I != ReturnNodes.end() && "Function does not return a value!"); - return &GraphNodes[I->second]; + return I->second; } /// getVarargNode - Return the node representing the variable arguments /// formal for the specified function. - Node *getVarargNode(Function *F) { - std::map::iterator I = VarargNodes.find(F); + unsigned getVarargNode(Function *F) { + DenseMap::iterator I = VarargNodes.find(F); assert(I != VarargNodes.end() && "Function does not take var args!"); - return &GraphNodes[I->second]; + return I->second; } /// getNodeValue - Get the node for the specified LLVM value and set the /// value for it to be the specified value. - Node *getNodeValue(Value &V) { - return getNode(&V)->setValue(&V); + 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); + 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 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); - Node *getNodeForConstantPointer(Constant *C); - Node *getNodeForConstantPointerTarget(Constant *C); - void AddGlobalInitializerConstraints(Node *N, Constant *C); void AddConstraintsForNonInternalLinkage(Function *F); void AddConstraintsForCall(CallSite CS, Function *F); + bool AddConstraintsForExternalCall(CallSite CS, Function *F); void PrintNode(Node *N); void PrintConstraints(); + void PrintConstraint(const Constraint &); + void PrintLabels(); void PrintPointsToGraph(); //===------------------------------------------------------------------===// @@ -323,64 +581,94 @@ namespace { 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 visitVANext(VANextInst &I); void visitVAArg(VAArgInst &I); void visitInstruction(Instruction &I); + }; - RegisterOpt X("anders-aa", - "Andersen's Interprocedural Alias Analysis"); - RegisterAnalysisGroup Y; + char Andersens::ID = 0; + RegisterPass X("anders-aa", + "Andersen's Interprocedural Alias Analysis"); + RegisterAnalysisGroup Y(X); + + // Initialize Timestamp Counter (static). + unsigned 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 = getNode((Value*)V1); - Node *N2 = getNode((Value*)V2); + Node *N1 = &GraphNodes[FindNode(getNode(const_cast(V1)))]; + Node *N2 = &GraphNodes[FindNode(getNode(const_cast(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, &GraphNodes[NullObject])) + 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 (!N1->PointsTo->test(UniversalSet)) + return NoModRef; // P doesn't point to the universal set. + } + + return AliasAnalysis::getModRefInfo(CS, P, Size); +} + +AliasAnalysis::ModRefResult +Andersens::getModRefInfo(CallSite CS1, CallSite CS2) { + return AliasAnalysis::getModRefInfo(CS1,CS2); +} + /// getMustAlias - We can provide must alias information if we know that a /// pointer can only point to a specific function or the null pointer. /// Unfortunately we cannot determine must-alias information for global /// variables or any other memory memory objects because we do not track whether /// a pointer points to the beginning of an object or a field of it. void Andersens::getMustAliases(Value *P, std::vector &RetVals) { - Node *N = getNode(P); - Node::iterator I = N->begin(); - if (I != N->end()) { - // If there is exactly one element in the points-to set for the object... - ++I; - if (I == N->end()) { - Node *Pointee = *N->begin(); - - // If a function is the only object in the points-to set, then it must be - // the destination. Note that we can't handle global variables here, - // because we don't know if the pointer is actually pointing to a field of - // the global or to the beginning of it. - if (Value *V = Pointee->getValue()) { - if (Function *F = dyn_cast(V)) - RetVals.push_back(F); - } else { - // If the object in the points-to set is the null object, then the null - // pointer is a must alias. - if (Pointee == &GraphNodes[NullObject]) - RetVals.push_back(Constant::getNullValue(P->getType())); - } + Node *N = &GraphNodes[FindNode(getNode(P))]; + if (N->PointsTo->count() == 1) { + Node *Pointee = &GraphNodes[N->PointsTo->find_first()]; + // If a function is the only object in the points-to set, then it must be + // the destination. Note that we can't handle global variables here, + // because we don't know if the pointer is actually pointing to a field of + // the global or to the beginning of it. + if (Value *V = Pointee->getValue()) { + if (Function *F = dyn_cast(V)) + RetVals.push_back(F); + } else { + // If the object in the points-to set is the null object, then the null + // pointer is a must alias. + if (Pointee == &GraphNodes[NullObject]) + RetVals.push_back(Constant::getNullValue(P->getType())); } } - AliasAnalysis::getMustAliases(P, RetVals); } @@ -390,14 +678,20 @@ void Andersens::getMustAliases(Value *P, std::vector &RetVals) { /// return true. /// bool Andersens::pointsToConstantMemory(const Value *P) { - Node *N = getNode((Value*)P); - for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { - if (Value *V = (*I)->getValue()) { + Node *N = &GraphNodes[FindNode(getNode((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(V) || (isa(V) && !cast(V)->isConstant())) return AliasAnalysis::pointsToConstantMemory(P); } else { - if (*I != &GraphNodes[NullObject]) + if (i != NullObject) return AliasAnalysis::pointsToConstantMemory(P); } } @@ -430,7 +724,8 @@ void Andersens::IdentifyObjects(Module &M) { ++NumObjects; // Add all the globals first. - for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) { + for (Module::global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) { ObjectNodes[I] = NumObjects++; ValueNodes[I] = NumObjects++; } @@ -438,17 +733,22 @@ void Andersens::IdentifyObjects(Module &M) { // 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++; - ObjectNodes[F] = NumObjects++; if (isa(F->getFunctionType()->getReturnType())) ReturnNodes[F] = NumObjects++; if (F->getFunctionType()->isVarArg()) VarargNodes[F] = NumObjects++; + // Add nodes for all of the incoming pointer arguments. - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) - if (isa(I->getType())) - ValueNodes[I] = NumObjects++; + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); + I != E; ++I) + { + if (isa(I->getType())) + 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 @@ -461,6 +761,14 @@ void Andersens::IdentifyObjects(Module &M) { if (AllocationInst *AI = dyn_cast(&*II)) ObjectNodes[AI] = NumObjects++; } + + // Calls to inline asm need to be added as well because the callee isn't + // referenced anywhere else. + if (CallInst *CI = dyn_cast(&*II)) { + Value *Callee = CI->getCalledValue(); + if (isa(Callee)) + ValueNodes[Callee] = NumObjects++; + } } } @@ -475,24 +783,23 @@ void Andersens::IdentifyObjects(Module &M) { /// getNodeForConstantPointer - Return the node corresponding to the constant /// pointer itself. -Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) { +unsigned Andersens::getNodeForConstantPointer(Constant *C) { assert(isa(C->getType()) && "Not a constant pointer!"); - if (isa(C)) - return &GraphNodes[NullPtr]; + if (isa(C) || isa(C)) + return NullPtr; else if (GlobalValue *GV = dyn_cast(C)) return getNode(GV); else if (ConstantExpr *CE = dyn_cast(C)) { switch (CE->getOpcode()) { case Instruction::GetElementPtr: return getNodeForConstantPointer(CE->getOperand(0)); - case Instruction::Cast: - if (isa(CE->getOperand(0)->getType())) - return getNodeForConstantPointer(CE->getOperand(0)); - else - return &GraphNodes[UniversalSet]; + case Instruction::IntToPtr: + return UniversalSet; + case Instruction::BitCast: + return getNodeForConstantPointer(CE->getOperand(0)); default: - std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; + cerr << "Constant Expr not yet handled: " << *CE << "\n"; assert(0); } } else { @@ -503,24 +810,23 @@ Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) { /// getNodeForConstantPointerTarget - Return the node POINTED TO by the /// specified constant pointer. -Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) { +unsigned Andersens::getNodeForConstantPointerTarget(Constant *C) { assert(isa(C->getType()) && "Not a constant pointer!"); if (isa(C)) - return &GraphNodes[NullObject]; + return NullObject; else if (GlobalValue *GV = dyn_cast(C)) return getObject(GV); else if (ConstantExpr *CE = dyn_cast(C)) { switch (CE->getOpcode()) { case Instruction::GetElementPtr: return getNodeForConstantPointerTarget(CE->getOperand(0)); - case Instruction::Cast: - if (isa(CE->getOperand(0)->getType())) - return getNodeForConstantPointerTarget(CE->getOperand(0)); - else - return &GraphNodes[UniversalSet]; + case Instruction::IntToPtr: + return UniversalSet; + case Instruction::BitCast: + return getNodeForConstantPointerTarget(CE->getOperand(0)); default: - std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; + cerr << "Constant Expr not yet handled: " << *CE << "\n"; assert(0); } } else { @@ -531,79 +837,221 @@ Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) { /// AddGlobalInitializerConstraints - Add inclusion constraints for the memory /// object N, which contains values indicated by C. -void Andersens::AddGlobalInitializerConstraints(Node *N, Constant *C) { +void Andersens::AddGlobalInitializerConstraints(unsigned NodeIndex, + Constant *C) { if (C->getType()->isFirstClassType()) { if (isa(C->getType())) - N->addPointerTo(getNodeForConstantPointer(C)); + Constraints.push_back(Constraint(Constraint::Copy, NodeIndex, + getNodeForConstantPointer(C))); } else if (C->isNullValue()) { - N->addPointerTo(&GraphNodes[NullObject]); + Constraints.push_back(Constraint(Constraint::Copy, NodeIndex, + NullObject)); return; - } else { + } else if (!isa(C)) { // If this is an array or struct, include constraints for each element. assert(isa(C) || isa(C)); for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) - AddGlobalInitializerConstraints(N, cast(C->getOperand(i))); + AddGlobalInitializerConstraints(NodeIndex, + cast(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::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) if (isa(I->getType())) // 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), - &GraphNodes[UniversalSet])); + 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.i32" || + F->getName() == "llvm.memset.i64" || + 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.i32" || F->getName() == "llvm.memcpy.i64" || + F->getName() == "llvm.memmove.i32" ||F->getName() == "llvm.memmove.i64" || + F->getName() == "memmove") { + + // *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)); + return true; + } + + // Result = Arg0 + if (F->getName() == "realloc" || F->getName() == "strchr" || + F->getName() == "strrchr" || F->getName() == "strstr" || + F->getName() == "strtok") { + 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 (!isa(V->getType())) return true; + + for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) + if (dyn_cast(*UI)) { + return false; + } else if (StoreInst *SI = dyn_cast(*UI)) { + if (V == SI->getOperand(1)) { + return false; + } else if (SI->getOperand(1)) { + return true; // Storing the pointer + } + } else if (GetElementPtrInst *GEP = dyn_cast(*UI)) { + if (AnalyzeUsesOfFunction(GEP)) return true; + } else if (CallInst *CI = dyn_cast(*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(*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(*UI)) { + if (CE->getOpcode() == Instruction::GetElementPtr || + CE->getOpcode() == Instruction::BitCast) { + if (AnalyzeUsesOfFunction(CE)) + return true; + } else { + return true; + } + } else if (ICmpInst *ICI = dyn_cast(*UI)) { + if (!isa(ICI->getOperand(1))) + return true; // Allow comparison against null. + } else if (dyn_cast(*UI)) { + return false; + } 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. - GraphNodes[UniversalSet].addPointerTo(&GraphNodes[UniversalSet]); + 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. - GraphNodes[NullPtr].addPointerTo(&GraphNodes[NullObject]); + Constraints.push_back(Constraint(Constraint::AddressOf, NullPtr, NullObject)); // Next, add any constraints on global variables and their initializers. - for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) { + 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 = - Node *Object = getObject(I); + unsigned ObjectIndex = getObject(I); + Node *Object = &GraphNodes[ObjectIndex]; Object->setValue(I); - getNodeValue(*I)->addPointerTo(Object); + Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(*I), + ObjectIndex)); if (I->hasInitializer()) { - AddGlobalInitializerConstraints(Object, I->getInitializer()); + 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, Object, - &GraphNodes[UniversalSet])); + Constraints.push_back(Constraint(Constraint::Copy, ObjectIndex, + UniversalSet)); } } - - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - // Make the function address point to the function object. - getNodeValue(*F)->addPointerTo(getObject(F)->setValue(F)); + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { // Set up the return value node. if (isa(F->getFunctionType()->getReturnType())) - getReturnNode(F)->setValue(F); + GraphNodes[getReturnNode(F)].setValue(F); if (F->getFunctionType()->isVarArg()) - getVarargNode(F)->setValue(F); + GraphNodes[getVarargNode(F)].setValue(F); // Set up incoming argument nodes. - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); + I != E; ++I) if (isa(I->getType())) getNodeValue(*I); - if (!F->hasInternalLinkage()) + // 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->hasInternalLinkage() || AnalyzeUsesOfFunction(F)) AddConstraintsForNonInternalLinkage(F); - if (!F->isExternal()) { + 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. @@ -613,28 +1061,35 @@ void Andersens::CollectConstraints(Module &M) { if (isa(F->getFunctionType()->getReturnType())) Constraints.push_back(Constraint(Constraint::Copy, getReturnNode(F), - &GraphNodes[UniversalSet])); + UniversalSet)); // Any pointers that are passed into the function have the universal set // stored into them. - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); + I != E; ++I) if (isa(I->getType())) { // Pointers passed into external functions could have anything stored // through them. Constraints.push_back(Constraint(Constraint::Store, getNode(I), - &GraphNodes[UniversalSet])); + 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, - &GraphNodes[UniversalSet], + 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), - &GraphNodes[UniversalSet])); + UniversalSet)); } } NumConstraints += Constraints.size(); @@ -652,19 +1107,23 @@ void Andersens::visitInstruction(Instruction &I) { case Instruction::Br: case Instruction::Switch: case Instruction::Unwind: + case Instruction::Unreachable: case Instruction::Free: - case Instruction::Shl: - case Instruction::Shr: + case Instruction::ICmp: + case Instruction::FCmp: return; default: // Is this something we aren't handling yet? - std::cerr << "Unknown instruction: " << I; + cerr << "Unknown instruction: " << I; abort(); } } void Andersens::visitAllocationInst(AllocationInst &AI) { - getNodeValue(AI)->addPointerTo(getObject(&AI)->setValue(&AI)); + unsigned ObjectIndex = getObject(&AI); + GraphNodes[ObjectIndex].setValue(&AI); + Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(AI), + ObjectIndex)); } void Andersens::visitReturnInst(ReturnInst &RI) { @@ -698,7 +1157,7 @@ void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) { void Andersens::visitPHINode(PHINode &PN) { if (isa(PN.getType())) { - Node *PNN = getNodeValue(PN); + unsigned PNN = getNodeValue(PN); for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) // P1 = phi P2, P3 --> , , ... Constraints.push_back(Constraint(Constraint::Copy, PNN, @@ -715,20 +1174,28 @@ void Andersens::visitCastInst(CastInst &CI) { getNode(CI.getOperand(0)))); } else { // P1 = cast int --> +#if 0 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), - &GraphNodes[UniversalSet])); + UniversalSet)); +#else + getNodeValue(CI); +#endif } } else if (isa(Op->getType())) { // int = cast P1 --> +#if 0 Constraints.push_back(Constraint(Constraint::Copy, - &GraphNodes[UniversalSet], + UniversalSet, getNode(CI.getOperand(0)))); +#else + getNode(CI.getOperand(0)); +#endif } } void Andersens::visitSelectInst(SelectInst &SI) { if (isa(SI.getType())) { - Node *SIN = getNodeValue(SI); + unsigned SIN = getNodeValue(SI); // P1 = select C, P2, P3 ---> , Constraints.push_back(Constraint(Constraint::Copy, SIN, getNode(SI.getOperand(1)))); @@ -737,10 +1204,6 @@ void Andersens::visitSelectInst(SelectInst &SI) { } } -void Andersens::visitVANext(VANextInst &I) { - // FIXME: Implement - assert(0 && "vanext not handled yet!"); -} void Andersens::visitVAArg(VAArgInst &I) { assert(0 && "vaarg not handled yet!"); } @@ -751,43 +1214,86 @@ void Andersens::visitVAArg(VAArgInst &I) { /// 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 (isa(CS.getType())) { - Node *CSN = getNode(CS.getInstruction()); - if (isa(F->getFunctionType()->getReturnType())) { - Constraints.push_back(Constraint(Constraint::Copy, CSN, - getReturnNode(F))); + unsigned CSN = getNode(CS.getInstruction()); + if (!F || isa(F->getFunctionType()->getReturnType())) { + 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, - &GraphNodes[UniversalSet])); + UniversalSet)); } - } else if (isa(F->getFunctionType()->getReturnType())) { + } else if (F && isa(F->getFunctionType()->getReturnType())) { +#if FULL_UNIVERSAL Constraints.push_back(Constraint(Constraint::Copy, - &GraphNodes[UniversalSet], - getReturnNode(F))); + UniversalSet, + getNode(CallValue) + CallReturnPos)); +#else + Constraints.push_back(Constraint(Constraint::Copy, + getNode(CallValue) + CallReturnPos, + UniversalSet)); +#endif + + } - - Function::aiterator AI = F->abegin(), AE = F->aend(); + CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end(); - for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) - if (isa(AI->getType())) { + if (F) { + // Direct Call + Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); + for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) + if (isa(AI->getType())) { + if (isa((*ArgI)->getType())) { + // 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 (isa((*ArgI)->getType())) { +#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 (isa((*ArgI)->getType())) { // Copy the actual argument into the formal argument. - Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), - getNode(*ArgI))); + Constraints.push_back(Constraint(Constraint::Store, + getNode(CallValue), + getNode(*ArgI), ArgPos++)); } else { - Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), - &GraphNodes[UniversalSet])); + Constraints.push_back(Constraint(Constraint::Store, + getNode (CallValue), + UniversalSet, ArgPos++)); } - } else if (isa((*ArgI)->getType())) { - Constraints.push_back(Constraint(Constraint::Copy, - &GraphNodes[UniversalSet], - getNode(*ArgI))); } - + } // Copy all pointers passed through the varargs section to the varargs node. - if (F->getFunctionType()->isVarArg()) + if (F && F->getFunctionType()->isVarArg()) for (; ArgI != ArgE; ++ArgI) if (isa((*ArgI)->getType())) Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F), @@ -802,9 +1308,7 @@ void Andersens::visitCallSite(CallSite CS) { if (Function *F = CS.getCalledFunction()) { AddConstraintsForCall(CS, F); } else { - // We don't handle indirect call sites yet. Keep track of them for when we - // discover the call graph incrementally. - IndirectCalls.push_back(CS); + AddConstraintsForCall(CS, NULL); } } @@ -815,152 +1319,1163 @@ void Andersens::visitCallSite(CallSite CS) { /// 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 { - iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); - while (I1 != E1 && I2 != E2) { - if (*I1 == *I2) return true; - if (*I1 < *I2) - ++I1; - else - ++I2; - } - return false; + 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, Node *Ignoring) const { - iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); - while (I1 != E1 && I2 != E2) { - if (*I1 == *I2) { - if (*I1 != Ignoring) return true; - ++I1; ++I2; - } else if (*I1 < *I2) - ++I1; - else - ++I2; +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; +} + +void dumpToDOUT(SparseBitVector<> *bitmap) { +#ifndef NDEBUG + dump(*bitmap, DOUT); +#endif +} + + +/// 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 Translate; + std::vector 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; + } } - return false; + for (unsigned i = 0; i < NumberSpecialNodes; ++i) { + unsigned Pos = NewPos++; + Translate[i] = Pos; + NewGraphNodes.push_back(GraphNodes[i]); + DOUT << "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]); + DOUT << "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]); + DOUT << "Renumbering node " << i << " to node " << Pos << "\n"; + } + } + + for (DenseMap::iterator Iter = ValueNodes.begin(); + Iter != ValueNodes.end(); + ++Iter) + Iter->second = Translate[Iter->second]; + + for (DenseMap::iterator Iter = ObjectNodes.begin(); + Iter != ObjectNodes.end(); + ++Iter) + Iter->second = Translate[Iter->second]; + + for (DenseMap::iterator Iter = ReturnNodes.begin(); + Iter != ReturnNodes.end(); + ++Iter) + Iter->second = Translate[Iter->second]; + + for (DenseMap::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() { + DOUT << "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(); + DOUT << "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() { + DOUT << "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(); + DOUT << "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 NewConstraints; + DenseSet 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])); + DOUT << " is a non-pointer, ignoring constraint.\n"; + continue; + } + if (RHSLabel == 0) { + DEBUG(PrintNode(&GraphNodes[RHSNode])); + DOUT << " 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; } -// Copy constraint: all edges out of the source node get copied to the -// destination node. This returns true if a change is made. -bool Andersens::Node::copyFrom(Node *N) { - // Use a mostly linear-time merge since both of the lists are sorted. - bool Changed = false; - iterator I = N->begin(), E = N->end(); - unsigned i = 0; - while (I != E && i != Pointees.size()) { - if (Pointees[i] < *I) { - ++i; - } else if (Pointees[i] == *I) { - ++i; ++I; +void Andersens::PrintLabels() { + for (unsigned i = 0; i < GraphNodes.size(); ++i) { + if (i < FirstRefNode) { + PrintNode(&GraphNodes[i]); + } else if (i < FirstAdrNode) { + DOUT << "REF("; + PrintNode(&GraphNodes[i-FirstRefNode]); + DOUT <<")"; } else { - // We found a new element to copy over. - Changed = true; - Pointees.insert(Pointees.begin()+i, *I); - ++i; ++I; + DOUT << "ADR("; + PrintNode(&GraphNodes[i-FirstAdrNode]); + DOUT <<")"; + } + + DOUT << " has pointer label " << GraphNodes[i].PointerEquivLabel + << " and SCC rep " << VSSCCRep[i] + << " and is " << (GraphNodes[i].Direct ? "Direct" : "Not direct") + << "\n"; + } +} + +/// Optimize the constraints by performing offline variable substitution and +/// other optimizations. +void Andersens::OptimizeConstraints() { + DOUT << "Beginning constraint optimization\n"; + + // Function related nodes need to stay in the same relative position and can't + // be location equivalent. + for (std::map::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; } } - if (I != E) { - Pointees.insert(Pointees.end(), I, E); - Changed = true; + 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); - return Changed; + // 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; + delete N->PredEdges; + delete N->ImplicitPredEdges; + delete N->PointedToBy; + } + } + GraphNodes.erase(GraphNodes.begin() + FirstRefNode, GraphNodes.end()); + DOUT << "Finished constraint optimization\n"; + FirstRefNode = 0; + FirstAdrNode = 0; } -bool Andersens::Node::loadFrom(Node *N) { - bool Changed = false; - for (iterator I = N->begin(), E = N->end(); I != E; ++I) - Changed |= copyFrom(*I); - return Changed; +/// Unite pointer but not location equivalent variables, now that the constraint +/// graph is built. +void Andersens::UnitePointerEquivalences() { + DOUT << "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]); + } + } + DOUT << "Finished remaining pointer equivalences\n"; + PENLEClass2Node.clear(); } -bool Andersens::Node::storeThrough(Node *N) { - bool Changed = false; - for (iterator I = begin(), E = end(); I != E; ++I) - Changed |= (*I)->copyFrom(N); - return Changed; +/// 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() { - bool Changed = true; - unsigned Iteration = 0; - while (Changed) { - Changed = false; - ++NumIters; - DEBUG(std::cerr << "Starting iteration #" << Iteration++ << "!\n"); - - // Loop over all of the constraints, applying them in turn. - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - Constraint &C = Constraints[i]; - switch (C.Type) { - case Constraint::Copy: - Changed |= C.Dest->copyFrom(C.Src); - break; - case Constraint::Load: - Changed |= C.Dest->loadFrom(C.Src); - break; - case Constraint::Store: - Changed |= C.Dest->storeThrough(C.Src); - break; - default: - assert(0 && "Unknown constraint!"); + 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 Seen; + DenseSet, 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 TarjanWL; + while( !CurrWL->empty() ) { + DOUT << "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; + Seen.clear(); + + /* Now process the constraints for this node. */ + for (std::list::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::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; + } + // TODO: hybrid cycle detection would go here, we should check + // if it was a statically detected offline equivalence that + // involves pointers , and if so, remove the redundant constraints. + + 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]); - if (Changed) { - // Check to see if any internal function's addresses have been passed to - // external functions. If so, we have to assume that their incoming - // arguments could be anything. If there are any internal functions in - // the universal node that we don't know about, we must iterate. - for (Node::iterator I = GraphNodes[UniversalSet].begin(), - E = GraphNodes[UniversalSet].end(); I != E; ++I) - if (Function *F = dyn_cast_or_null((*I)->getValue())) - if (F->hasInternalLinkage() && - EscapingInternalFunctions.insert(F).second) { - // We found a function that is just now escaping. Mark it as if it - // didn't have internal linkage. - AddConstraintsForNonInternalLinkage(F); - DEBUG(std::cerr << "Found escaping internal function: " - << F->getName() << "\n"); - ++NumEscapingFunctions; - } - - // Check to see if we have discovered any new callees of the indirect call - // sites. If so, add constraints to the analysis. - for (unsigned i = 0, e = IndirectCalls.size(); i != e; ++i) { - CallSite CS = IndirectCalls[i]; - std::vector &KnownCallees = IndirectCallees[CS]; - Node *CN = getNode(CS.getCalledValue()); - - for (Node::iterator NI = CN->begin(), E = CN->end(); NI != E; ++NI) - if (Function *F = dyn_cast_or_null((*NI)->getValue())) { - std::vector::iterator IP = - std::lower_bound(KnownCallees.begin(), KnownCallees.end(), F); - if (IP == KnownCallees.end() || *IP != F) { - // Add the constraints for the call now. - AddConstraintsForCall(CS, F); - DEBUG(std::cerr << "Found actual callee '" - << F->getName() << "' for call: " - << *CS.getInstruction() << "\n"); - ++NumIndirectCallees; - KnownCallees.insert(IP, F); - } - } + } + 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 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; } } +//===----------------------------------------------------------------------===// +// 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++; + DOUT << "Unified Node "; + DEBUG(PrintNode(FirstNode)); + DOUT << " and Node "; + DEBUG(PrintNode(SecondNode)); + DOUT << "\n"; + + // TODO: Handle SDT + 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)); +} //===----------------------------------------------------------------------===// // Debugging Output @@ -968,13 +2483,17 @@ void Andersens::SolveConstraints() { void Andersens::PrintNode(Node *N) { if (N == &GraphNodes[UniversalSet]) { - std::cerr << ""; + cerr << ""; return; } else if (N == &GraphNodes[NullPtr]) { - std::cerr << ""; + cerr << ""; return; } else if (N == &GraphNodes[NullObject]) { - std::cerr << ""; + cerr << ""; + return; + } + if (!N->getValue()) { + cerr << "artificial" << (intptr_t) N; return; } @@ -982,57 +2501,86 @@ void Andersens::PrintNode(Node *N) { Value *V = N->getValue(); if (Function *F = dyn_cast(V)) { if (isa(F->getFunctionType()->getReturnType()) && - N == getReturnNode(F)) { - std::cerr << F->getName() << ":retval"; + N == &GraphNodes[getReturnNode(F)]) { + cerr << F->getName() << ":retval"; return; - } else if (F->getFunctionType()->isVarArg() && N == getVarargNode(F)) { - std::cerr << F->getName() << ":vararg"; + } else if (F->getFunctionType()->isVarArg() && + N == &GraphNodes[getVarargNode(F)]) { + cerr << F->getName() << ":vararg"; return; } } if (Instruction *I = dyn_cast(V)) - std::cerr << I->getParent()->getParent()->getName() << ":"; + cerr << I->getParent()->getParent()->getName() << ":"; else if (Argument *Arg = dyn_cast(V)) - std::cerr << Arg->getParent()->getName() << ":"; + cerr << Arg->getParent()->getName() << ":"; if (V->hasName()) - std::cerr << V->getName(); + cerr << V->getName(); else - std::cerr << "(unnamed)"; + cerr << "(unnamed)"; if (isa(V) || isa(V)) - if (N == getObject(V)) - std::cerr << ""; + if (N == &GraphNodes[getObject(V)]) + cerr << ""; +} +void Andersens::PrintConstraint(const Constraint &C) { + if (C.Type == Constraint::Store) { + cerr << "*"; + if (C.Offset != 0) + cerr << "("; + } + PrintNode(&GraphNodes[C.Dest]); + if (C.Type == Constraint::Store && C.Offset != 0) + cerr << " + " << C.Offset << ")"; + cerr << " = "; + if (C.Type == Constraint::Load) { + cerr << "*"; + if (C.Offset != 0) + cerr << "("; + } + else if (C.Type == Constraint::AddressOf) + cerr << "&"; + PrintNode(&GraphNodes[C.Src]); + if (C.Offset != 0 && C.Type != Constraint::Store) + cerr << " + " << C.Offset; + if (C.Type == Constraint::Load && C.Offset != 0) + cerr << ")"; + cerr << "\n"; } void Andersens::PrintConstraints() { - std::cerr << "Constraints:\n"; - for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { - std::cerr << " #" << i << ": "; - Constraint &C = Constraints[i]; - if (C.Type == Constraint::Store) - std::cerr << "*"; - PrintNode(C.Dest); - std::cerr << " = "; - if (C.Type == Constraint::Load) - std::cerr << "*"; - PrintNode(C.Src); - std::cerr << "\n"; - } + cerr << "Constraints:\n"; + + for (unsigned i = 0, e = Constraints.size(); i != e; ++i) + PrintConstraint(Constraints[i]); } void Andersens::PrintPointsToGraph() { - std::cerr << "Points-to graph:\n"; + cerr << "Points-to graph:\n"; for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) { Node *N = &GraphNodes[i]; - std::cerr << "[" << (N->end() - N->begin()) << "] "; - PrintNode(N); - std::cerr << "\t--> "; - for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { - if (I != N->begin()) std::cerr << ", "; - PrintNode(*I); + if (FindNode (i) != i) { + PrintNode(N); + cerr << "\t--> same as "; + PrintNode(&GraphNodes[FindNode(i)]); + cerr << "\n"; + } else { + cerr << "[" << (N->PointsTo->count()) << "] "; + PrintNode(N); + cerr << "\t--> "; + + bool first = true; + for (SparseBitVector<>::iterator bi = N->PointsTo->begin(); + bi != N->PointsTo->end(); + ++bi) { + if (!first) + cerr << ", "; + PrintNode(&GraphNodes[*bi]); + first = false; + } + cerr << "\n"; } - std::cerr << "\n"; } }