LLVM API Documentation

Andersens.cpp

Go to the documentation of this file.
00001 //===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines an implementation of Andersen's interprocedural alias
00011 // analysis
00012 //
00013 // In pointer analysis terms, this is a subset-based, flow-insensitive,
00014 // field-sensitive, and context-insensitive algorithm pointer algorithm.
00015 //
00016 // This algorithm is implemented as three stages:
00017 //   1. Object identification.
00018 //   2. Inclusion constraint identification.
00019 //   3. Offline constraint graph optimization
00020 //   4. Inclusion constraint solving.
00021 //
00022 // The object identification stage identifies all of the memory objects in the
00023 // program, which includes globals, heap allocated objects, and stack allocated
00024 // objects.
00025 //
00026 // The inclusion constraint identification stage finds all inclusion constraints
00027 // in the program by scanning the program, looking for pointer assignments and
00028 // other statements that effect the points-to graph.  For a statement like "A =
00029 // B", this statement is processed to indicate that A can point to anything that
00030 // B can point to.  Constraints can handle copies, loads, and stores, and
00031 // address taking.
00032 //
00033 // The offline constraint graph optimization portion includes offline variable
00034 // substitution algorithms intended to compute pointer and location
00035 // equivalences.  Pointer equivalences are those pointers that will have the
00036 // same points-to sets, and location equivalences are those variables that
00037 // always appear together in points-to sets.  It also includes an offline
00038 // cycle detection algorithm that allows cycles to be collapsed sooner 
00039 // during solving.
00040 //
00041 // The inclusion constraint solving phase iteratively propagates the inclusion
00042 // constraints until a fixed point is reached.  This is an O(N^3) algorithm.
00043 //
00044 // Function constraints are handled as if they were structs with X fields.
00045 // Thus, an access to argument X of function Y is an access to node index
00046 // getNode(Y) + X.  This representation allows handling of indirect calls
00047 // without any issues.  To wit, an indirect call Y(a,b) is equivalent to
00048 // *(Y + 1) = a, *(Y + 2) = b.
00049 // The return node for a function is always located at getNode(F) +
00050 // CallReturnPos. The arguments start at getNode(F) + CallArgPos.
00051 //
00052 // Future Improvements:
00053 //   Use of BDD's.
00054 //===----------------------------------------------------------------------===//
00055 
00056 #define DEBUG_TYPE "anders-aa"
00057 #include "llvm/Constants.h"
00058 #include "llvm/DerivedTypes.h"
00059 #include "llvm/Instructions.h"
00060 #include "llvm/Module.h"
00061 #include "llvm/Pass.h"
00062 #include "llvm/Support/Compiler.h"
00063 #include "llvm/Support/ErrorHandling.h"
00064 #include "llvm/Support/InstIterator.h"
00065 #include "llvm/Support/InstVisitor.h"
00066 #include "llvm/Analysis/AliasAnalysis.h"
00067 #include "llvm/Analysis/Passes.h"
00068 #include "llvm/Support/Debug.h"
00069 #include "llvm/System/Atomic.h"
00070 #include "llvm/ADT/Statistic.h"
00071 #include "llvm/ADT/SparseBitVector.h"
00072 #include "llvm/ADT/DenseSet.h"
00073 #include <algorithm>
00074 #include <set>
00075 #include <list>
00076 #include <map>
00077 #include <stack>
00078 #include <vector>
00079 #include <queue>
00080 
00081 // Determining the actual set of nodes the universal set can consist of is very
00082 // expensive because it means propagating around very large sets.  We rely on
00083 // other analysis being able to determine which nodes can never be pointed to in
00084 // order to disambiguate further than "points-to anything".
00085 #define FULL_UNIVERSAL 0
00086 
00087 using namespace llvm;
00088 STATISTIC(NumIters      , "Number of iterations to reach convergence");
00089 STATISTIC(NumConstraints, "Number of constraints");
00090 STATISTIC(NumNodes      , "Number of nodes");
00091 STATISTIC(NumUnified    , "Number of variables unified");
00092 STATISTIC(NumErased     , "Number of redundant constraints erased");
00093 
00094 static const unsigned SelfRep = (unsigned)-1;
00095 static const unsigned Unvisited = (unsigned)-1;
00096 // Position of the function return node relative to the function node.
00097 static const unsigned CallReturnPos = 1;
00098 // Position of the function call node relative to the function node.
00099 static const unsigned CallFirstArgPos = 2;
00100 
00101 namespace {
00102   struct BitmapKeyInfo {
00103     static inline SparseBitVector<> *getEmptyKey() {
00104       return reinterpret_cast<SparseBitVector<> *>(-1);
00105     }
00106     static inline SparseBitVector<> *getTombstoneKey() {
00107       return reinterpret_cast<SparseBitVector<> *>(-2);
00108     }
00109     static unsigned getHashValue(const SparseBitVector<> *bitmap) {
00110       return bitmap->getHashValue();
00111     }
00112     static bool isEqual(const SparseBitVector<> *LHS,
00113                         const SparseBitVector<> *RHS) {
00114       if (LHS == RHS)
00115         return true;
00116       else if (LHS == getEmptyKey() || RHS == getEmptyKey()
00117                || LHS == getTombstoneKey() || RHS == getTombstoneKey())
00118         return false;
00119 
00120       return *LHS == *RHS;
00121     }
00122 
00123     static bool isPod() { return true; }
00124   };
00125 
00126   class VISIBILITY_HIDDEN Andersens : public ModulePass, public AliasAnalysis,
00127                                       private InstVisitor<Andersens> {
00128     struct Node;
00129 
00130     /// Constraint - Objects of this structure are used to represent the various
00131     /// constraints identified by the algorithm.  The constraints are 'copy',
00132     /// for statements like "A = B", 'load' for statements like "A = *B",
00133     /// 'store' for statements like "*A = B", and AddressOf for statements like
00134     /// A = alloca;  The Offset is applied as *(A + K) = B for stores,
00135     /// A = *(B + K) for loads, and A = B + K for copies.  It is
00136     /// illegal on addressof constraints (because it is statically
00137     /// resolvable to A = &C where C = B + K)
00138 
00139     struct Constraint {
00140       enum ConstraintType { Copy, Load, Store, AddressOf } Type;
00141       unsigned Dest;
00142       unsigned Src;
00143       unsigned Offset;
00144 
00145       Constraint(ConstraintType Ty, unsigned D, unsigned S, unsigned O = 0)
00146         : Type(Ty), Dest(D), Src(S), Offset(O) {
00147         assert((Offset == 0 || Ty != AddressOf) &&
00148                "Offset is illegal on addressof constraints");
00149       }
00150 
00151       bool operator==(const Constraint &RHS) const {
00152         return RHS.Type == Type
00153           && RHS.Dest == Dest
00154           && RHS.Src == Src
00155           && RHS.Offset == Offset;
00156       }
00157 
00158       bool operator!=(const Constraint &RHS) const {
00159         return !(*this == RHS);
00160       }
00161 
00162       bool operator<(const Constraint &RHS) const {
00163         if (RHS.Type != Type)
00164           return RHS.Type < Type;
00165         else if (RHS.Dest != Dest)
00166           return RHS.Dest < Dest;
00167         else if (RHS.Src != Src)
00168           return RHS.Src < Src;
00169         return RHS.Offset < Offset;
00170       }
00171     };
00172 
00173     // Information DenseSet requires implemented in order to be able to do
00174     // it's thing
00175     struct PairKeyInfo {
00176       static inline std::pair<unsigned, unsigned> getEmptyKey() {
00177         return std::make_pair(~0U, ~0U);
00178       }
00179       static inline std::pair<unsigned, unsigned> getTombstoneKey() {
00180         return std::make_pair(~0U - 1, ~0U - 1);
00181       }
00182       static unsigned getHashValue(const std::pair<unsigned, unsigned> &P) {
00183         return P.first ^ P.second;
00184       }
00185       static unsigned isEqual(const std::pair<unsigned, unsigned> &LHS,
00186                               const std::pair<unsigned, unsigned> &RHS) {
00187         return LHS == RHS;
00188       }
00189     };
00190     
00191     struct ConstraintKeyInfo {
00192       static inline Constraint getEmptyKey() {
00193         return Constraint(Constraint::Copy, ~0U, ~0U, ~0U);
00194       }
00195       static inline Constraint getTombstoneKey() {
00196         return Constraint(Constraint::Copy, ~0U - 1, ~0U - 1, ~0U - 1);
00197       }
00198       static unsigned getHashValue(const Constraint &C) {
00199         return C.Src ^ C.Dest ^ C.Type ^ C.Offset;
00200       }
00201       static bool isEqual(const Constraint &LHS,
00202                           const Constraint &RHS) {
00203         return LHS.Type == RHS.Type && LHS.Dest == RHS.Dest
00204           && LHS.Src == RHS.Src && LHS.Offset == RHS.Offset;
00205       }
00206     };
00207 
00208     // Node class - This class is used to represent a node in the constraint
00209     // graph.  Due to various optimizations, it is not always the case that
00210     // there is a mapping from a Node to a Value.  In particular, we add
00211     // artificial Node's that represent the set of pointed-to variables shared
00212     // for each location equivalent Node.
00213     struct Node {
00214     private:
00215       static volatile sys::cas_flag Counter;
00216 
00217     public:
00218       Value *Val;
00219       SparseBitVector<> *Edges;
00220       SparseBitVector<> *PointsTo;
00221       SparseBitVector<> *OldPointsTo;
00222       std::list<Constraint> Constraints;
00223 
00224       // Pointer and location equivalence labels
00225       unsigned PointerEquivLabel;
00226       unsigned LocationEquivLabel;
00227       // Predecessor edges, both real and implicit
00228       SparseBitVector<> *PredEdges;
00229       SparseBitVector<> *ImplicitPredEdges;
00230       // Set of nodes that point to us, only use for location equivalence.
00231       SparseBitVector<> *PointedToBy;
00232       // Number of incoming edges, used during variable substitution to early
00233       // free the points-to sets
00234       unsigned NumInEdges;
00235       // True if our points-to set is in the Set2PEClass map
00236       bool StoredInHash;
00237       // True if our node has no indirect constraints (complex or otherwise)
00238       bool Direct;
00239       // True if the node is address taken, *or* it is part of a group of nodes
00240       // that must be kept together.  This is set to true for functions and
00241       // their arg nodes, which must be kept at the same position relative to
00242       // their base function node.
00243       bool AddressTaken;
00244 
00245       // Nodes in cycles (or in equivalence classes) are united together using a
00246       // standard union-find representation with path compression.  NodeRep
00247       // gives the index into GraphNodes for the representative Node.
00248       unsigned NodeRep;
00249 
00250       // Modification timestamp.  Assigned from Counter.
00251       // Used for work list prioritization.
00252       unsigned Timestamp;
00253 
00254       explicit Node(bool direct = true) :
00255         Val(0), Edges(0), PointsTo(0), OldPointsTo(0), 
00256         PointerEquivLabel(0), LocationEquivLabel(0), PredEdges(0),
00257         ImplicitPredEdges(0), PointedToBy(0), NumInEdges(0),
00258         StoredInHash(false), Direct(direct), AddressTaken(false),
00259         NodeRep(SelfRep), Timestamp(0) { }
00260 
00261       Node *setValue(Value *V) {
00262         assert(Val == 0 && "Value already set for this node!");
00263         Val = V;
00264         return this;
00265       }
00266 
00267       /// getValue - Return the LLVM value corresponding to this node.
00268       ///
00269       Value *getValue() const { return Val; }
00270 
00271       /// addPointerTo - Add a pointer to the list of pointees of this node,
00272       /// returning true if this caused a new pointer to be added, or false if
00273       /// we already knew about the points-to relation.
00274       bool addPointerTo(unsigned Node) {
00275         return PointsTo->test_and_set(Node);
00276       }
00277 
00278       /// intersects - Return true if the points-to set of this node intersects
00279       /// with the points-to set of the specified node.
00280       bool intersects(Node *N) const;
00281 
00282       /// intersectsIgnoring - Return true if the points-to set of this node
00283       /// intersects with the points-to set of the specified node on any nodes
00284       /// except for the specified node to ignore.
00285       bool intersectsIgnoring(Node *N, unsigned) const;
00286 
00287       // Timestamp a node (used for work list prioritization)
00288       void Stamp() {
00289         Timestamp = sys::AtomicIncrement(&Counter);
00290         --Timestamp;
00291       }
00292 
00293       bool isRep() const {
00294         return( (int) NodeRep < 0 );
00295       }
00296     };
00297 
00298     struct WorkListElement {
00299       Node* node;
00300       unsigned Timestamp;
00301       WorkListElement(Node* n, unsigned t) : node(n), Timestamp(t) {}
00302 
00303       // Note that we reverse the sense of the comparison because we
00304       // actually want to give low timestamps the priority over high,
00305       // whereas priority is typically interpreted as a greater value is
00306       // given high priority.
00307       bool operator<(const WorkListElement& that) const {
00308         return( this->Timestamp > that.Timestamp );
00309       }
00310     };
00311 
00312     // Priority-queue based work list specialized for Nodes.
00313     class WorkList {
00314       std::priority_queue<WorkListElement> Q;
00315 
00316     public:
00317       void insert(Node* n) {
00318         Q.push( WorkListElement(n, n->Timestamp) );
00319       }
00320 
00321       // We automatically discard non-representative nodes and nodes
00322       // that were in the work list twice (we keep a copy of the
00323       // timestamp in the work list so we can detect this situation by
00324       // comparing against the node's current timestamp).
00325       Node* pop() {
00326         while( !Q.empty() ) {
00327           WorkListElement x = Q.top(); Q.pop();
00328           Node* INode = x.node;
00329 
00330           if( INode->isRep() &&
00331               INode->Timestamp == x.Timestamp ) {
00332             return(x.node);
00333           }
00334         }
00335         return(0);
00336       }
00337 
00338       bool empty() {
00339         return Q.empty();
00340       }
00341     };
00342 
00343     /// GraphNodes - This vector is populated as part of the object
00344     /// identification stage of the analysis, which populates this vector with a
00345     /// node for each memory object and fills in the ValueNodes map.
00346     std::vector<Node> GraphNodes;
00347 
00348     /// ValueNodes - This map indicates the Node that a particular Value* is
00349     /// represented by.  This contains entries for all pointers.
00350     DenseMap<Value*, unsigned> ValueNodes;
00351 
00352     /// ObjectNodes - This map contains entries for each memory object in the
00353     /// program: globals, alloca's and mallocs.
00354     DenseMap<Value*, unsigned> ObjectNodes;
00355 
00356     /// ReturnNodes - This map contains an entry for each function in the
00357     /// program that returns a value.
00358     DenseMap<Function*, unsigned> ReturnNodes;
00359 
00360     /// VarargNodes - This map contains the entry used to represent all pointers
00361     /// passed through the varargs portion of a function call for a particular
00362     /// function.  An entry is not present in this map for functions that do not
00363     /// take variable arguments.
00364     DenseMap<Function*, unsigned> VarargNodes;
00365 
00366 
00367     /// Constraints - This vector contains a list of all of the constraints
00368     /// identified by the program.
00369     std::vector<Constraint> Constraints;
00370 
00371     // Map from graph node to maximum K value that is allowed (for functions,
00372     // this is equivalent to the number of arguments + CallFirstArgPos)
00373     std::map<unsigned, unsigned> MaxK;
00374 
00375     /// This enum defines the GraphNodes indices that correspond to important
00376     /// fixed sets.
00377     enum {
00378       UniversalSet = 0,
00379       NullPtr      = 1,
00380       NullObject   = 2,
00381       NumberSpecialNodes
00382     };
00383     // Stack for Tarjan's
00384     std::stack<unsigned> SCCStack;
00385     // Map from Graph Node to DFS number
00386     std::vector<unsigned> Node2DFS;
00387     // Map from Graph Node to Deleted from graph.
00388     std::vector<bool> Node2Deleted;
00389     // Same as Node Maps, but implemented as std::map because it is faster to
00390     // clear 
00391     std::map<unsigned, unsigned> Tarjan2DFS;
00392     std::map<unsigned, bool> Tarjan2Deleted;
00393     // Current DFS number
00394     unsigned DFSNumber;
00395 
00396     // Work lists.
00397     WorkList w1, w2;
00398     WorkList *CurrWL, *NextWL; // "current" and "next" work lists
00399 
00400     // Offline variable substitution related things
00401 
00402     // Temporary rep storage, used because we can't collapse SCC's in the
00403     // predecessor graph by uniting the variables permanently, we can only do so
00404     // for the successor graph.
00405     std::vector<unsigned> VSSCCRep;
00406     // Mapping from node to whether we have visited it during SCC finding yet.
00407     std::vector<bool> Node2Visited;
00408     // During variable substitution, we create unknowns to represent the unknown
00409     // value that is a dereference of a variable.  These nodes are known as
00410     // "ref" nodes (since they represent the value of dereferences).
00411     unsigned FirstRefNode;
00412     // During HVN, we create represent address taken nodes as if they were
00413     // unknown (since HVN, unlike HU, does not evaluate unions).
00414     unsigned FirstAdrNode;
00415     // Current pointer equivalence class number
00416     unsigned PEClass;
00417     // Mapping from points-to sets to equivalence classes
00418     typedef DenseMap<SparseBitVector<> *, unsigned, BitmapKeyInfo> BitVectorMap;
00419     BitVectorMap Set2PEClass;
00420     // Mapping from pointer equivalences to the representative node.  -1 if we
00421     // have no representative node for this pointer equivalence class yet.
00422     std::vector<int> PEClass2Node;
00423     // Mapping from pointer equivalences to representative node.  This includes
00424     // pointer equivalent but not location equivalent variables. -1 if we have
00425     // no representative node for this pointer equivalence class yet.
00426     std::vector<int> PENLEClass2Node;
00427     // Union/Find for HCD
00428     std::vector<unsigned> HCDSCCRep;
00429     // HCD's offline-detected cycles; "Statically DeTected"
00430     // -1 if not part of such a cycle, otherwise a representative node.
00431     std::vector<int> SDT;
00432     // Whether to use SDT (UniteNodes can use it during solving, but not before)
00433     bool SDTActive;
00434 
00435   public:
00436     static char ID;
00437     Andersens() : ModulePass(&ID) {}
00438 
00439     bool runOnModule(Module &M) {
00440       InitializeAliasAnalysis(this);
00441       IdentifyObjects(M);
00442       CollectConstraints(M);
00443 #undef DEBUG_TYPE
00444 #define DEBUG_TYPE "anders-aa-constraints"
00445       DEBUG(PrintConstraints());
00446 #undef DEBUG_TYPE
00447 #define DEBUG_TYPE "anders-aa"
00448       SolveConstraints();
00449       DEBUG(PrintPointsToGraph());
00450 
00451       // Free the constraints list, as we don't need it to respond to alias
00452       // requests.
00453       std::vector<Constraint>().swap(Constraints);
00454       //These are needed for Print() (-analyze in opt)
00455       //ObjectNodes.clear();
00456       //ReturnNodes.clear();
00457       //VarargNodes.clear();
00458       return false;
00459     }
00460 
00461     void releaseMemory() {
00462       // FIXME: Until we have transitively required passes working correctly,
00463       // this cannot be enabled!  Otherwise, using -count-aa with the pass
00464       // causes memory to be freed too early. :(
00465 #if 0
00466       // The memory objects and ValueNodes data structures at the only ones that
00467       // are still live after construction.
00468       std::vector<Node>().swap(GraphNodes);
00469       ValueNodes.clear();
00470 #endif
00471     }
00472 
00473     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00474       AliasAnalysis::getAnalysisUsage(AU);
00475       AU.setPreservesAll();                         // Does not transform code
00476     }
00477 
00478     //------------------------------------------------
00479     // Implement the AliasAnalysis API
00480     //
00481     AliasResult alias(const Value *V1, unsigned V1Size,
00482                       const Value *V2, unsigned V2Size);
00483     virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
00484     virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
00485     void getMustAliases(Value *P, std::vector<Value*> &RetVals);
00486     bool pointsToConstantMemory(const Value *P);
00487 
00488     virtual void deleteValue(Value *V) {
00489       ValueNodes.erase(V);
00490       getAnalysis<AliasAnalysis>().deleteValue(V);
00491     }
00492 
00493     virtual void copyValue(Value *From, Value *To) {
00494       ValueNodes[To] = ValueNodes[From];
00495       getAnalysis<AliasAnalysis>().copyValue(From, To);
00496     }
00497 
00498   private:
00499     /// getNode - Return the node corresponding to the specified pointer scalar.
00500     ///
00501     unsigned getNode(Value *V) {
00502       if (Constant *C = dyn_cast<Constant>(V))
00503         if (!isa<GlobalValue>(C))
00504           return getNodeForConstantPointer(C);
00505 
00506       DenseMap<Value*, unsigned>::iterator I = ValueNodes.find(V);
00507       if (I == ValueNodes.end()) {
00508 #ifndef NDEBUG
00509         V->dump();
00510 #endif
00511         llvm_unreachable("Value does not have a node in the points-to graph!");
00512       }
00513       return I->second;
00514     }
00515 
00516     /// getObject - Return the node corresponding to the memory object for the
00517     /// specified global or allocation instruction.
00518     unsigned getObject(Value *V) const {
00519       DenseMap<Value*, unsigned>::iterator I = ObjectNodes.find(V);
00520       assert(I != ObjectNodes.end() &&
00521              "Value does not have an object in the points-to graph!");
00522       return I->second;
00523     }
00524 
00525     /// getReturnNode - Return the node representing the return value for the
00526     /// specified function.
00527     unsigned getReturnNode(Function *F) const {
00528       DenseMap<Function*, unsigned>::iterator I = ReturnNodes.find(F);
00529       assert(I != ReturnNodes.end() && "Function does not return a value!");
00530       return I->second;
00531     }
00532 
00533     /// getVarargNode - Return the node representing the variable arguments
00534     /// formal for the specified function.
00535     unsigned getVarargNode(Function *F) const {
00536       DenseMap<Function*, unsigned>::iterator I = VarargNodes.find(F);
00537       assert(I != VarargNodes.end() && "Function does not take var args!");
00538       return I->second;
00539     }
00540 
00541     /// getNodeValue - Get the node for the specified LLVM value and set the
00542     /// value for it to be the specified value.
00543     unsigned getNodeValue(Value &V) {
00544       unsigned Index = getNode(&V);
00545       GraphNodes[Index].setValue(&V);
00546       return Index;
00547     }
00548 
00549     unsigned UniteNodes(unsigned First, unsigned Second,
00550                         bool UnionByRank = true);
00551     unsigned FindNode(unsigned Node);
00552     unsigned FindNode(unsigned Node) const;
00553 
00554     void IdentifyObjects(Module &M);
00555     void CollectConstraints(Module &M);
00556     bool AnalyzeUsesOfFunction(Value *);
00557     void CreateConstraintGraph();
00558     void OptimizeConstraints();
00559     unsigned FindEquivalentNode(unsigned, unsigned);
00560     void ClumpAddressTaken();
00561     void RewriteConstraints();
00562     void HU();
00563     void HVN();
00564     void HCD();
00565     void Search(unsigned Node);
00566     void UnitePointerEquivalences();
00567     void SolveConstraints();
00568     bool QueryNode(unsigned Node);
00569     void Condense(unsigned Node);
00570     void HUValNum(unsigned Node);
00571     void HVNValNum(unsigned Node);
00572     unsigned getNodeForConstantPointer(Constant *C);
00573     unsigned getNodeForConstantPointerTarget(Constant *C);
00574     void AddGlobalInitializerConstraints(unsigned, Constant *C);
00575 
00576     void AddConstraintsForNonInternalLinkage(Function *F);
00577     void AddConstraintsForCall(CallSite CS, Function *F);
00578     bool AddConstraintsForExternalCall(CallSite CS, Function *F);
00579 
00580 
00581     void PrintNode(const Node *N) const;
00582     void PrintConstraints() const ;
00583     void PrintConstraint(const Constraint &) const;
00584     void PrintLabels() const;
00585     void PrintPointsToGraph() const;
00586 
00587     //===------------------------------------------------------------------===//
00588     // Instruction visitation methods for adding constraints
00589     //
00590     friend class InstVisitor<Andersens>;
00591     void visitReturnInst(ReturnInst &RI);
00592     void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); }
00593     void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); }
00594     void visitCallSite(CallSite CS);
00595     void visitAllocationInst(AllocationInst &AI);
00596     void visitLoadInst(LoadInst &LI);
00597     void visitStoreInst(StoreInst &SI);
00598     void visitGetElementPtrInst(GetElementPtrInst &GEP);
00599     void visitPHINode(PHINode &PN);
00600     void visitCastInst(CastInst &CI);
00601     void visitICmpInst(ICmpInst &ICI) {} // NOOP!
00602     void visitFCmpInst(FCmpInst &ICI) {} // NOOP!
00603     void visitSelectInst(SelectInst &SI);
00604     void visitVAArg(VAArgInst &I);
00605     void visitInstruction(Instruction &I);
00606 
00607     //===------------------------------------------------------------------===//
00608     // Implement Analyize interface
00609     //
00610     void print(std::ostream &O, const Module* M) const {
00611       PrintPointsToGraph();
00612     }
00613   };
00614 }
00615 
00616 char Andersens::ID = 0;
00617 static RegisterPass<Andersens>
00618 X("anders-aa", "Andersen's Interprocedural Alias Analysis", false, true);
00619 static RegisterAnalysisGroup<AliasAnalysis> Y(X);
00620 
00621 // Initialize Timestamp Counter (static).
00622 volatile llvm::sys::cas_flag Andersens::Node::Counter = 0;
00623 
00624 ModulePass *llvm::createAndersensPass() { return new Andersens(); }
00625 
00626 //===----------------------------------------------------------------------===//
00627 //                  AliasAnalysis Interface Implementation
00628 //===----------------------------------------------------------------------===//
00629 
00630 AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size,
00631                                             const Value *V2, unsigned V2Size) {
00632   Node *N1 = &GraphNodes[FindNode(getNode(const_cast<Value*>(V1)))];
00633   Node *N2 = &GraphNodes[FindNode(getNode(const_cast<Value*>(V2)))];
00634 
00635   // Check to see if the two pointers are known to not alias.  They don't alias
00636   // if their points-to sets do not intersect.
00637   if (!N1->intersectsIgnoring(N2, NullObject))
00638     return NoAlias;
00639 
00640   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
00641 }
00642 
00643 AliasAnalysis::ModRefResult
00644 Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
00645   // The only thing useful that we can contribute for mod/ref information is
00646   // when calling external function calls: if we know that memory never escapes
00647   // from the program, it cannot be modified by an external call.
00648   //
00649   // NOTE: This is not really safe, at least not when the entire program is not
00650   // available.  The deal is that the external function could call back into the
00651   // program and modify stuff.  We ignore this technical niggle for now.  This
00652   // is, after all, a "research quality" implementation of Andersen's analysis.
00653   if (Function *F = CS.getCalledFunction())
00654     if (F->isDeclaration()) {
00655       Node *N1 = &GraphNodes[FindNode(getNode(P))];
00656 
00657       if (N1->PointsTo->empty())
00658         return NoModRef;
00659 #if FULL_UNIVERSAL
00660       if (!UniversalSet->PointsTo->test(FindNode(getNode(P))))
00661         return NoModRef;  // Universal set does not contain P
00662 #else
00663       if (!N1->PointsTo->test(UniversalSet))
00664         return NoModRef;  // P doesn't point to the universal set.
00665 #endif
00666     }
00667 
00668   return AliasAnalysis::getModRefInfo(CS, P, Size);
00669 }
00670 
00671 AliasAnalysis::ModRefResult
00672 Andersens::getModRefInfo(CallSite CS1, CallSite CS2) {
00673   return AliasAnalysis::getModRefInfo(CS1,CS2);
00674 }
00675 
00676 /// getMustAlias - We can provide must alias information if we know that a
00677 /// pointer can only point to a specific function or the null pointer.
00678 /// Unfortunately we cannot determine must-alias information for global
00679 /// variables or any other memory memory objects because we do not track whether
00680 /// a pointer points to the beginning of an object or a field of it.
00681 void Andersens::getMustAliases(Value *P, std::vector<Value*> &RetVals) {
00682   Node *N = &GraphNodes[FindNode(getNode(P))];
00683   if (N->PointsTo->count() == 1) {
00684     Node *Pointee = &GraphNodes[N->PointsTo->find_first()];
00685     // If a function is the only object in the points-to set, then it must be
00686     // the destination.  Note that we can't handle global variables here,
00687     // because we don't know if the pointer is actually pointing to a field of
00688     // the global or to the beginning of it.
00689     if (Value *V = Pointee->getValue()) {
00690       if (Function *F = dyn_cast<Function>(V))
00691         RetVals.push_back(F);
00692     } else {
00693       // If the object in the points-to set is the null object, then the null
00694       // pointer is a must alias.
00695       if (Pointee == &GraphNodes[NullObject])
00696         RetVals.push_back(Constant::getNullValue(P->getType()));
00697     }
00698   }
00699   AliasAnalysis::getMustAliases(P, RetVals);
00700 }
00701 
00702 /// pointsToConstantMemory - If we can determine that this pointer only points
00703 /// to constant memory, return true.  In practice, this means that if the
00704 /// pointer can only point to constant globals, functions, or the null pointer,
00705 /// return true.
00706 ///
00707 bool Andersens::pointsToConstantMemory(const Value *P) {
00708   Node *N = &GraphNodes[FindNode(getNode(const_cast<Value*>(P)))];
00709   unsigned i;
00710 
00711   for (SparseBitVector<>::iterator bi = N->PointsTo->begin();
00712        bi != N->PointsTo->end();
00713        ++bi) {
00714     i = *bi;
00715     Node *Pointee = &GraphNodes[i];
00716     if (Value *V = Pointee->getValue()) {
00717       if (!isa<GlobalValue>(V) || (isa<GlobalVariable>(V) &&
00718                                    !cast<GlobalVariable>(V)->isConstant()))
00719         return AliasAnalysis::pointsToConstantMemory(P);
00720     } else {
00721       if (i != NullObject)
00722         return AliasAnalysis::pointsToConstantMemory(P);
00723     }
00724   }
00725 
00726   return true;
00727 }
00728 
00729 //===----------------------------------------------------------------------===//
00730 //                       Object Identification Phase
00731 //===----------------------------------------------------------------------===//
00732 
00733 /// IdentifyObjects - This stage scans the program, adding an entry to the
00734 /// GraphNodes list for each memory object in the program (global stack or
00735 /// heap), and populates the ValueNodes and ObjectNodes maps for these objects.
00736 ///
00737 void Andersens::IdentifyObjects(Module &M) {
00738   unsigned NumObjects = 0;
00739 
00740   // Object #0 is always the universal set: the object that we don't know
00741   // anything about.
00742   assert(NumObjects == UniversalSet && "Something changed!");
00743   ++NumObjects;
00744 
00745   // Object #1 always represents the null pointer.
00746   assert(NumObjects == NullPtr && "Something changed!");
00747   ++NumObjects;
00748 
00749   // Object #2 always represents the null object (the object pointed to by null)
00750   assert(NumObjects == NullObject && "Something changed!");
00751   ++NumObjects;
00752 
00753   // Add all the globals first.
00754   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
00755        I != E; ++I) {
00756     ObjectNodes[I] = NumObjects++;
00757     ValueNodes[I] = NumObjects++;
00758   }
00759 
00760   // Add nodes for all of the functions and the instructions inside of them.
00761   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
00762     // The function itself is a memory object.
00763     unsigned First = NumObjects;
00764     ValueNodes[F] = NumObjects++;
00765     if (isa<PointerType>(F->getFunctionType()->getReturnType()))
00766       ReturnNodes[F] = NumObjects++;
00767     if (F->getFunctionType()->isVarArg())
00768       VarargNodes[F] = NumObjects++;
00769 
00770 
00771     // Add nodes for all of the incoming pointer arguments.
00772     for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
00773          I != E; ++I)
00774       {
00775         if (isa<PointerType>(I->getType()))
00776           ValueNodes[I] = NumObjects++;
00777       }
00778     MaxK[First] = NumObjects - First;
00779 
00780     // Scan the function body, creating a memory object for each heap/stack
00781     // allocation in the body of the function and a node to represent all
00782     // pointer values defined by instructions and used as operands.
00783     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
00784       // If this is an heap or stack allocation, create a node for the memory
00785       // object.
00786       if (isa<PointerType>(II->getType())) {
00787         ValueNodes[&*II] = NumObjects++;
00788         if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II))
00789           ObjectNodes[AI] = NumObjects++;
00790       }
00791 
00792       // Calls to inline asm need to be added as well because the callee isn't
00793       // referenced anywhere else.
00794       if (CallInst *CI = dyn_cast<CallInst>(&*II)) {
00795         Value *Callee = CI->getCalledValue();
00796         if (isa<InlineAsm>(Callee))
00797           ValueNodes[Callee] = NumObjects++;
00798       }
00799     }
00800   }
00801 
00802   // Now that we know how many objects to create, make them all now!
00803   GraphNodes.resize(NumObjects);
00804   NumNodes += NumObjects;
00805 }
00806 
00807 //===----------------------------------------------------------------------===//
00808 //                     Constraint Identification Phase
00809 //===----------------------------------------------------------------------===//
00810 
00811 /// getNodeForConstantPointer - Return the node corresponding to the constant
00812 /// pointer itself.
00813 unsigned Andersens::getNodeForConstantPointer(Constant *C) {
00814   assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
00815 
00816   if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C))
00817     return NullPtr;
00818   else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
00819     return getNode(GV);
00820   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
00821     switch (CE->getOpcode()) {
00822     case Instruction::GetElementPtr:
00823       return getNodeForConstantPointer(CE->getOperand(0));
00824     case Instruction::IntToPtr:
00825       return UniversalSet;
00826     case Instruction::BitCast:
00827       return getNodeForConstantPointer(CE->getOperand(0));
00828     default:
00829       errs() << "Constant Expr not yet handled: " << *CE << "\n";
00830       llvm_unreachable(0);
00831     }
00832   } else {
00833     llvm_unreachable("Unknown constant pointer!");
00834   }
00835   return 0;
00836 }
00837 
00838 /// getNodeForConstantPointerTarget - Return the node POINTED TO by the
00839 /// specified constant pointer.
00840 unsigned Andersens::getNodeForConstantPointerTarget(Constant *C) {
00841   assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
00842 
00843   if (isa<ConstantPointerNull>(C))
00844     return NullObject;
00845   else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
00846     return getObject(GV);
00847   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
00848     switch (CE->getOpcode()) {
00849     case Instruction::GetElementPtr:
00850       return getNodeForConstantPointerTarget(CE->getOperand(0));
00851     case Instruction::IntToPtr:
00852       return UniversalSet;
00853     case Instruction::BitCast:
00854       return getNodeForConstantPointerTarget(CE->getOperand(0));
00855     default:
00856       errs() << "Constant Expr not yet handled: " << *CE << "\n";
00857       llvm_unreachable(0);
00858     }
00859   } else {
00860     llvm_unreachable("Unknown constant pointer!");
00861   }
00862   return 0;
00863 }
00864 
00865 /// AddGlobalInitializerConstraints - Add inclusion constraints for the memory
00866 /// object N, which contains values indicated by C.
00867 void Andersens::AddGlobalInitializerConstraints(unsigned NodeIndex,
00868                                                 Constant *C) {
00869   if (C->getType()->isSingleValueType()) {
00870     if (isa<PointerType>(C->getType()))
00871       Constraints.push_back(Constraint(Constraint::Copy, NodeIndex,
00872                                        getNodeForConstantPointer(C)));
00873   } else if (C->isNullValue()) {
00874     Constraints.push_back(Constraint(Constraint::Copy, NodeIndex,
00875                                      NullObject));
00876     return;
00877   } else if (!isa<UndefValue>(C)) {
00878     // If this is an array or struct, include constraints for each element.
00879     assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C));
00880     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
00881       AddGlobalInitializerConstraints(NodeIndex,
00882                                       cast<Constant>(C->getOperand(i)));
00883   }
00884 }
00885 
00886 /// AddConstraintsForNonInternalLinkage - If this function does not have
00887 /// internal linkage, realize that we can't trust anything passed into or
00888 /// returned by this function.
00889 void Andersens::AddConstraintsForNonInternalLinkage(Function *F) {
00890   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
00891     if (isa<PointerType>(I->getType()))
00892       // If this is an argument of an externally accessible function, the
00893       // incoming pointer might point to anything.
00894       Constraints.push_back(Constraint(Constraint::Copy, getNode(I),
00895                                        UniversalSet));
00896 }
00897 
00898 /// AddConstraintsForCall - If this is a call to a "known" function, add the
00899 /// constraints and return true.  If this is a call to an unknown function,
00900 /// return false.
00901 bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) {
00902   assert(F->isDeclaration() && "Not an external function!");
00903 
00904   // These functions don't induce any points-to constraints.
00905   if (F->getName() == "atoi" || F->getName() == "atof" ||
00906       F->getName() == "atol" || F->getName() == "atoll" ||
00907       F->getName() == "remove" || F->getName() == "unlink" ||
00908       F->getName() == "rename" || F->getName() == "memcmp" ||
00909       F->getName() == "llvm.memset" ||
00910       F->getName() == "strcmp" || F->getName() == "strncmp" ||
00911       F->getName() == "execl" || F->getName() == "execlp" ||
00912       F->getName() == "execle" || F->getName() == "execv" ||
00913       F->getName() == "execvp" || F->getName() == "chmod" ||
00914       F->getName() == "puts" || F->getName() == "write" ||
00915       F->getName() == "open" || F->getName() == "create" ||
00916       F->getName() == "truncate" || F->getName() == "chdir" ||
00917       F->getName() == "mkdir" || F->getName() == "rmdir" ||
00918       F->getName() == "read" || F->getName() == "pipe" ||
00919       F->getName() == "wait" || F->getName() == "time" ||
00920       F->getName() == "stat" || F->getName() == "fstat" ||
00921       F->getName() == "lstat" || F->getName() == "strtod" ||
00922       F->getName() == "strtof" || F->getName() == "strtold" ||
00923       F->getName() == "fopen" || F->getName() == "fdopen" ||
00924       F->getName() == "freopen" ||
00925       F->getName() == "fflush" || F->getName() == "feof" ||
00926       F->getName() == "fileno" || F->getName() == "clearerr" ||
00927       F->getName() == "rewind" || F->getName() == "ftell" ||
00928       F->getName() == "ferror" || F->getName() == "fgetc" ||
00929       F->getName() == "fgetc" || F->getName() == "_IO_getc" ||
00930       F->getName() == "fwrite" || F->getName() == "fread" ||
00931       F->getName() == "fgets" || F->getName() == "ungetc" ||
00932       F->getName() == "fputc" ||
00933       F->getName() == "fputs" || F->getName() == "putc" ||
00934       F->getName() == "ftell" || F->getName() == "rewind" ||
00935       F->getName() == "_IO_putc" || F->getName() == "fseek" ||
00936       F->getName() == "fgetpos" || F->getName() == "fsetpos" ||
00937       F->getName() == "printf" || F->getName() == "fprintf" ||
00938       F->getName() == "sprintf" || F->getName() == "vprintf" ||
00939       F->getName() == "vfprintf" || F->getName() == "vsprintf" ||
00940       F->getName() == "scanf" || F->getName() == "fscanf" ||
00941       F->getName() == "sscanf" || F->getName() == "__assert_fail" ||
00942       F->getName() == "modf")
00943     return true;
00944 
00945 
00946   // These functions do induce points-to edges.
00947   if (F->getName() == "llvm.memcpy" ||
00948       F->getName() == "llvm.memmove" ||
00949       F->getName() == "memmove") {
00950 
00951     const FunctionType *FTy = F->getFunctionType();
00952     if (FTy->getNumParams() > 1 && 
00953         isa<PointerType>(FTy->getParamType(0)) &&
00954         isa<PointerType>(FTy->getParamType(1))) {
00955 
00956       // *Dest = *Src, which requires an artificial graph node to represent the
00957       // constraint.  It is broken up into *Dest = temp, temp = *Src
00958       unsigned FirstArg = getNode(CS.getArgument(0));
00959       unsigned SecondArg = getNode(CS.getArgument(1));
00960       unsigned TempArg = GraphNodes.size();
00961       GraphNodes.push_back(Node());
00962       Constraints.push_back(Constraint(Constraint::Store,
00963                                        FirstArg, TempArg));
00964       Constraints.push_back(Constraint(Constraint::Load,
00965                                        TempArg, SecondArg));
00966       // In addition, Dest = Src
00967       Constraints.push_back(Constraint(Constraint::Copy,
00968                                        FirstArg, SecondArg));
00969       return true;
00970     }
00971   }
00972 
00973   // Result = Arg0
00974   if (F->getName() == "realloc" || F->getName() == "strchr" ||
00975       F->getName() == "strrchr" || F->getName() == "strstr" ||
00976       F->getName() == "strtok") {
00977     const FunctionType *FTy = F->getFunctionType();
00978     if (FTy->getNumParams() > 0 && 
00979         isa<PointerType>(FTy->getParamType(0))) {
00980       Constraints.push_back(Constraint(Constraint::Copy,
00981                                        getNode(CS.getInstruction()),
00982                                        getNode(CS.getArgument(0))));
00983       return true;
00984     }
00985   }
00986 
00987   return false;
00988 }
00989 
00990 
00991 
00992 /// AnalyzeUsesOfFunction - Look at all of the users of the specified function.
00993 /// If this is used by anything complex (i.e., the address escapes), return
00994 /// true.
00995 bool Andersens::AnalyzeUsesOfFunction(Value *V) {
00996 
00997   if (!isa<PointerType>(V->getType())) return true;
00998 
00999   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
01000     if (isa<LoadInst>(*UI)) {
01001       return false;
01002     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
01003       if (V == SI->getOperand(1)) {
01004         return false;
01005       } else if (SI->getOperand(1)) {
01006         return true;  // Storing the pointer
01007       }
01008     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
01009       if (AnalyzeUsesOfFunction(GEP)) return true;
01010     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
01011       // Make sure that this is just the function being called, not that it is
01012       // passing into the function.
01013       for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
01014         if (CI->getOperand(i) == V) return true;
01015     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
01016       // Make sure that this is just the function being called, not that it is
01017       // passing into the function.
01018       for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i)
01019         if (II->getOperand(i) == V) return true;
01020     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
01021       if (CE->getOpcode() == Instruction::GetElementPtr ||
01022           CE->getOpcode() == Instruction::BitCast) {
01023         if (AnalyzeUsesOfFunction(CE))
01024           return true;
01025       } else {
01026         return true;
01027       }
01028     } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) {
01029       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
01030         return true;  // Allow comparison against null.
01031     } else if (isa<FreeInst>(*UI)) {
01032       return false;
01033     } else {
01034       return true;
01035     }
01036   return false;
01037 }
01038 
01039 /// CollectConstraints - This stage scans the program, adding a constraint to
01040 /// the Constraints list for each instruction in the program that induces a
01041 /// constraint, and setting up the initial points-to graph.
01042 ///
01043 void Andersens::CollectConstraints(Module &M) {
01044   // First, the universal set points to itself.
01045   Constraints.push_back(Constraint(Constraint::AddressOf, UniversalSet,
01046                                    UniversalSet));
01047   Constraints.push_back(Constraint(Constraint::Store, UniversalSet,
01048                                    UniversalSet));
01049 
01050   // Next, the null pointer points to the null object.
01051   Constraints.push_back(Constraint(Constraint::AddressOf, NullPtr, NullObject));
01052 
01053   // Next, add any constraints on global variables and their initializers.
01054   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
01055        I != E; ++I) {
01056     // Associate the address of the global object as pointing to the memory for
01057     // the global: &G = <G memory>
01058     unsigned ObjectIndex = getObject(I);
01059     Node *Object = &GraphNodes[ObjectIndex];
01060     Object->setValue(I);
01061     Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(*I),
01062                                      ObjectIndex));
01063 
01064     if (I->hasDefinitiveInitializer()) {
01065       AddGlobalInitializerConstraints(ObjectIndex, I->getInitializer());
01066     } else {
01067       // If it doesn't have an initializer (i.e. it's defined in another
01068       // translation unit), it points to the universal set.
01069       Constraints.push_back(Constraint(Constraint::Copy, ObjectIndex,
01070                                        UniversalSet));
01071     }
01072   }
01073 
01074   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
01075     // Set up the return value node.
01076     if (isa<PointerType>(F->getFunctionType()->getReturnType()))
01077       GraphNodes[getReturnNode(F)].setValue(F);
01078     if (F->getFunctionType()->isVarArg())
01079       GraphNodes[getVarargNode(F)].setValue(F);
01080 
01081     // Set up incoming argument nodes.
01082     for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
01083          I != E; ++I)
01084       if (isa<PointerType>(I->getType()))
01085         getNodeValue(*I);
01086 
01087     // At some point we should just add constraints for the escaping functions
01088     // at solve time, but this slows down solving. For now, we simply mark
01089     // address taken functions as escaping and treat them as external.
01090     if (!F->hasLocalLinkage() || AnalyzeUsesOfFunction(F))
01091       AddConstraintsForNonInternalLinkage(F);
01092 
01093     if (!F->isDeclaration()) {
01094       // Scan the function body, creating a memory object for each heap/stack
01095       // allocation in the body of the function and a node to represent all
01096       // pointer values defined by instructions and used as operands.
01097       visit(F);
01098     } else {
01099       // External functions that return pointers return the universal set.
01100       if (isa<PointerType>(F->getFunctionType()->getReturnType()))
01101         Constraints.push_back(Constraint(Constraint::Copy,
01102                                          getReturnNode(F),
01103                                          UniversalSet));
01104 
01105       // Any pointers that are passed into the function have the universal set
01106       // stored into them.
01107       for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
01108            I != E; ++I)
01109         if (isa<PointerType>(I->getType())) {
01110           // Pointers passed into external functions could have anything stored
01111           // through them.
01112           Constraints.push_back(Constraint(Constraint::Store, getNode(I),
01113                                            UniversalSet));
01114           // Memory objects passed into external function calls can have the
01115           // universal set point to them.
01116 #if FULL_UNIVERSAL
01117           Constraints.push_back(Constraint(Constraint::Copy,
01118                                            UniversalSet,
01119                                            getNode(I)));
01120 #else
01121           Constraints.push_back(Constraint(Constraint::Copy,
01122                                            getNode(I),
01123                                            UniversalSet));
01124 #endif
01125         }
01126 
01127       // If this is an external varargs function, it can also store pointers
01128       // into any pointers passed through the varargs section.
01129       if (F->getFunctionType()->isVarArg())
01130         Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F),
01131                                          UniversalSet));
01132     }
01133   }
01134   NumConstraints += Constraints.size();
01135 }
01136 
01137 
01138 void Andersens::visitInstruction(Instruction &I) {
01139 #ifdef NDEBUG
01140   return;          // This function is just a big assert.
01141 #endif
01142   if (isa<BinaryOperator>(I))
01143     return;
01144   // Most instructions don't have any effect on pointer values.
01145   switch (I.getOpcode()) {
01146   case Instruction::Br:
01147   case Instruction::Switch:
01148   case Instruction::Unwind:
01149   case Instruction::Unreachable:
01150   case Instruction::Free:
01151   case Instruction::ICmp:
01152   case Instruction::FCmp:
01153     return;
01154   default:
01155     // Is this something we aren't handling yet?
01156     errs() << "Unknown instruction: " << I;
01157     llvm_unreachable(0);
01158   }
01159 }
01160 
01161 void Andersens::visitAllocationInst(AllocationInst &AI) {
01162   unsigned ObjectIndex = getObject(&AI);
01163   GraphNodes[ObjectIndex].setValue(&AI);
01164   Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(AI),
01165                                    ObjectIndex));
01166 }
01167 
01168 void Andersens::visitReturnInst(ReturnInst &RI) {
01169   if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType()))
01170     // return V   -->   <Copy/retval{F}/v>
01171     Constraints.push_back(Constraint(Constraint::Copy,
01172                                      getReturnNode(RI.getParent()->getParent()),
01173                                      getNode(RI.getOperand(0))));
01174 }
01175 
01176 void Andersens::visitLoadInst(LoadInst &LI) {
01177   if (isa<PointerType>(LI.getType()))
01178     // P1 = load P2  -->  <Load/P1/P2>
01179     Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI),
01180                                      getNode(LI.getOperand(0))));
01181 }
01182 
01183 void Andersens::visitStoreInst(StoreInst &SI) {
01184   if (isa<PointerType>(SI.getOperand(0)->getType()))
01185     // store P1, P2  -->  <Store/P2/P1>
01186     Constraints.push_back(Constraint(Constraint::Store,
01187                                      getNode(SI.getOperand(1)),
01188                                      getNode(SI.getOperand(0))));
01189 }
01190 
01191 void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) {
01192   // P1 = getelementptr P2, ... --> <Copy/P1/P2>
01193   Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP),
01194                                    getNode(GEP.getOperand(0))));
01195 }
01196 
01197 void Andersens::visitPHINode(PHINode &PN) {
01198   if (isa<PointerType>(PN.getType())) {
01199     unsigned PNN = getNodeValue(PN);
01200     for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
01201       // P1 = phi P2, P3  -->  <Copy/P1/P2>, <Copy/P1/P3>, ...
01202       Constraints.push_back(Constraint(Constraint::Copy, PNN,
01203                                        getNode(PN.getIncomingValue(i))));
01204   }
01205 }
01206 
01207 void Andersens::visitCastInst(CastInst &CI) {
01208   Value *Op = CI.getOperand(0);
01209   if (isa<PointerType>(CI.getType())) {
01210     if (isa<PointerType>(Op->getType())) {
01211       // P1 = cast P2  --> <Copy/P1/P2>
01212       Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
01213                                        getNode(CI.getOperand(0))));
01214     } else {
01215       // P1 = cast int --> <Copy/P1/Univ>
01216 #if 0
01217       Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
01218                                        UniversalSet));
01219 #else
01220       getNodeValue(CI);
01221 #endif
01222     }
01223   } else if (isa<PointerType>(Op->getType())) {
01224     // int = cast P1 --> <Copy/Univ/P1>
01225 #if 0
01226     Constraints.push_back(Constraint(Constraint::Copy,
01227                                      UniversalSet,
01228                                      getNode(CI.getOperand(0))));
01229 #else
01230     getNode(CI.getOperand(0));
01231 #endif
01232   }
01233 }
01234 
01235 void Andersens::visitSelectInst(SelectInst &SI) {
01236   if (isa<PointerType>(SI.getType())) {
01237     unsigned SIN = getNodeValue(SI);
01238     // P1 = select C, P2, P3   ---> <Copy/P1/P2>, <Copy/P1/P3>
01239     Constraints.push_back(Constraint(Constraint::Copy, SIN,
01240                                      getNode(SI.getOperand(1))));
01241     Constraints.push_back(Constraint(Constraint::Copy, SIN,
01242                                      getNode(SI.getOperand(2))));
01243   }
01244 }
01245 
01246 void Andersens::visitVAArg(VAArgInst &I) {
01247   llvm_unreachable("vaarg not handled yet!");
01248 }
01249 
01250 /// AddConstraintsForCall - Add constraints for a call with actual arguments
01251 /// specified by CS to the function specified by F.  Note that the types of
01252 /// arguments might not match up in the case where this is an indirect call and
01253 /// the function pointer has been casted.  If this is the case, do something
01254 /// reasonable.
01255 void Andersens::AddConstraintsForCall(CallSite CS, Function *F) {
01256   Value *CallValue = CS.getCalledValue();
01257   bool IsDeref = F == NULL;
01258 
01259   // If this is a call to an external function, try to handle it directly to get
01260   // some taste of context sensitivity.
01261   if (F && F->isDeclaration() && AddConstraintsForExternalCall(CS, F))
01262     return;
01263 
01264   if (isa<PointerType>(CS.getType())) {
01265     unsigned CSN = getNode(CS.getInstruction());
01266     if (!F || isa<PointerType>(F->getFunctionType()->getReturnType())) {
01267       if (IsDeref)
01268         Constraints.push_back(Constraint(Constraint::Load, CSN,
01269                                          getNode(CallValue), CallReturnPos));
01270       else
01271         Constraints.push_back(Constraint(Constraint::Copy, CSN,
01272                                          getNode(CallValue) + CallReturnPos));
01273     } else {
01274       // If the function returns a non-pointer value, handle this just like we
01275       // treat a nonpointer cast to pointer.
01276       Constraints.push_back(Constraint(Constraint::Copy, CSN,
01277                                        UniversalSet));
01278     }
01279   } else if (F && isa<PointerType>(F->getFunctionType()->getReturnType())) {
01280 #if FULL_UNIVERSAL
01281     Constraints.push_back(Constraint(Constraint::Copy,
01282                                      UniversalSet,
01283                                      getNode(CallValue) + CallReturnPos));
01284 #else
01285     Constraints.push_back(Constraint(Constraint::Copy,
01286                                       getNode(CallValue) + CallReturnPos,
01287                                       UniversalSet));
01288 #endif
01289                           
01290     
01291   }
01292 
01293   CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end();
01294   bool external = !F ||  F->isDeclaration();
01295   if (F) {
01296     // Direct Call
01297     Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
01298     for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) 
01299       {
01300 #if !FULL_UNIVERSAL
01301         if (external && isa<PointerType>((*ArgI)->getType())) 
01302           {
01303             // Add constraint that ArgI can now point to anything due to
01304             // escaping, as can everything it points to. The second portion of
01305             // this should be taken care of by universal = *universal
01306             Constraints.push_back(Constraint(Constraint::Copy,
01307                                              getNode(*ArgI),
01308                                              UniversalSet));
01309           }
01310 #endif
01311         if (isa<PointerType>(AI->getType())) {
01312           if (isa<PointerType>((*ArgI)->getType())) {
01313             // Copy the actual argument into the formal argument.
01314             Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
01315                                              getNode(*ArgI)));
01316           } else {
01317             Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
01318                                              UniversalSet));
01319           }
01320         } else if (isa<PointerType>((*ArgI)->getType())) {
01321 #if FULL_UNIVERSAL
01322           Constraints.push_back(Constraint(Constraint::Copy,
01323                                            UniversalSet,
01324                                            getNode(*ArgI)));
01325 #else
01326           Constraints.push_back(Constraint(Constraint::Copy,
01327                                            getNode(*ArgI),
01328                                            UniversalSet));
01329 #endif
01330         }
01331       }
01332   } else {
01333     //Indirect Call
01334     unsigned ArgPos = CallFirstArgPos;
01335     for (; ArgI != ArgE; ++ArgI) {
01336       if (isa<PointerType>((*ArgI)->getType())) {
01337         // Copy the actual argument into the formal argument.
01338         Constraints.push_back(Constraint(Constraint::Store,
01339                                          getNode(CallValue),
01340                                          getNode(*ArgI), ArgPos++));
01341       } else {
01342         Constraints.push_back(Constraint(Constraint::Store,
01343                                          getNode (CallValue),
01344                                          UniversalSet, ArgPos++));
01345       }
01346     }
01347   }
01348   // Copy all pointers passed through the varargs section to the varargs node.
01349   if (F && F->getFunctionType()->isVarArg())
01350     for (; ArgI != ArgE; ++ArgI)
01351       if (isa<PointerType>((*ArgI)->getType()))
01352         Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F),
01353                                          getNode(*ArgI)));
01354   // If more arguments are passed in than we track, just drop them on the floor.
01355 }
01356 
01357 void Andersens::visitCallSite(CallSite CS) {
01358   if (isa<PointerType>(CS.getType()))
01359     getNodeValue(*CS.getInstruction());
01360 
01361   if (Function *F = CS.getCalledFunction()) {
01362     AddConstraintsForCall(CS, F);
01363   } else {
01364     AddConstraintsForCall(CS, NULL);
01365   }
01366 }
01367 
01368 //===----------------------------------------------------------------------===//
01369 //                         Constraint Solving Phase
01370 //===----------------------------------------------------------------------===//
01371 
01372 /// intersects - Return true if the points-to set of this node intersects
01373 /// with the points-to set of the specified node.
01374 bool Andersens::Node::intersects(Node *N) const {
01375   return PointsTo->intersects(N->PointsTo);
01376 }
01377 
01378 /// intersectsIgnoring - Return true if the points-to set of this node
01379 /// intersects with the points-to set of the specified node on any nodes
01380 /// except for the specified node to ignore.
01381 bool Andersens::Node::intersectsIgnoring(Node *N, unsigned Ignoring) const {
01382   // TODO: If we are only going to call this with the same value for Ignoring,
01383   // we should move the special values out of the points-to bitmap.
01384   bool WeHadIt = PointsTo->test(Ignoring);
01385   bool NHadIt = N->PointsTo->test(Ignoring);
01386   bool Result = false;
01387   if (WeHadIt)
01388     PointsTo->reset(Ignoring);
01389   if (NHadIt)
01390     N->PointsTo->reset(Ignoring);
01391   Result = PointsTo->intersects(N->PointsTo);
01392   if (WeHadIt)
01393     PointsTo->set(Ignoring);
01394   if (NHadIt)
01395     N->PointsTo->set(Ignoring);
01396   return Result;
01397 }
01398 
01399 
01400 /// Clump together address taken variables so that the points-to sets use up
01401 /// less space and can be operated on faster.
01402 
01403 void Andersens::ClumpAddressTaken() {
01404 #undef DEBUG_TYPE
01405 #define DEBUG_TYPE "anders-aa-renumber"
01406   std::vector<unsigned> Translate;
01407   std::vector<Node> NewGraphNodes;
01408 
01409   Translate.resize(GraphNodes.size());
01410   unsigned NewPos = 0;
01411 
01412   for (unsigned i = 0; i < Constraints.size(); ++i) {
01413     Constraint &C = Constraints[i];
01414     if (C.Type == Constraint::AddressOf) {
01415       GraphNodes[C.Src].AddressTaken = true;
01416     }
01417   }
01418   for (unsigned i = 0; i < NumberSpecialNodes; ++i) {
01419     unsigned Pos = NewPos++;
01420     Translate[i] = Pos;
01421     NewGraphNodes.push_back(GraphNodes[i]);
01422     DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
01423   }
01424 
01425   // I believe this ends up being faster than making two vectors and splicing
01426   // them.
01427   for (unsigned i = NumberSpecialNodes; i < GraphNodes.size(); ++i) {
01428     if (GraphNodes[i].AddressTaken) {
01429       unsigned Pos = NewPos++;
01430       Translate[i] = Pos;
01431       NewGraphNodes.push_back(GraphNodes[i]);
01432       DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
01433     }
01434   }
01435 
01436   for (unsigned i = NumberSpecialNodes; i < GraphNodes.size(); ++i) {
01437     if (!GraphNodes[i].AddressTaken) {
01438       unsigned Pos = NewPos++;
01439       Translate[i] = Pos;
01440       NewGraphNodes.push_back(GraphNodes[i]);
01441       DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
01442     }
01443   }
01444 
01445   for (DenseMap<Value*, unsigned>::iterator Iter = ValueNodes.begin();
01446        Iter != ValueNodes.end();
01447        ++Iter)
01448     Iter->second = Translate[Iter->second];
01449 
01450   for (DenseMap<Value*, unsigned>::iterator Iter = ObjectNodes.begin();
01451        Iter != ObjectNodes.end();
01452        ++Iter)
01453     Iter->second = Translate[Iter->second];
01454 
01455   for (DenseMap<Function*, unsigned>::iterator Iter = ReturnNodes.begin();
01456        Iter != ReturnNodes.end();
01457        ++Iter)
01458     Iter->second = Translate[Iter->second];
01459 
01460   for (DenseMap<Function*, unsigned>::iterator Iter = VarargNodes.begin();
01461        Iter != VarargNodes.end();
01462        ++Iter)
01463     Iter->second = Translate[Iter->second];
01464 
01465   for (unsigned i = 0; i < Constraints.size(); ++i) {
01466     Constraint &C = Constraints[i];
01467     C.Src = Translate[C.Src];
01468     C.Dest = Translate[C.Dest];
01469   }
01470 
01471   GraphNodes.swap(NewGraphNodes);
01472 #undef DEBUG_TYPE
01473 #define DEBUG_TYPE "anders-aa"
01474 }
01475 
01476 /// The technique used here is described in "Exploiting Pointer and Location
01477 /// Equivalence to Optimize Pointer Analysis. In the 14th International Static
01478 /// Analysis Symposium (SAS), August 2007."  It is known as the "HVN" algorithm,
01479 /// and is equivalent to value numbering the collapsed constraint graph without
01480 /// evaluating unions.  This is used as a pre-pass to HU in order to resolve
01481 /// first order pointer dereferences and speed up/reduce memory usage of HU.
01482 /// Running both is equivalent to HRU without the iteration
01483 /// HVN in more detail:
01484 /// Imagine the set of constraints was simply straight line code with no loops
01485 /// (we eliminate cycles, so there are no loops), such as:
01486 /// E = &D
01487 /// E = &C
01488 /// E = F
01489 /// F = G
01490 /// G = F
01491 /// Applying value numbering to this code tells us:
01492 /// G == F == E
01493 ///
01494 /// For HVN, this is as far as it goes.  We assign new value numbers to every
01495 /// "address node", and every "reference node".
01496 /// To get the optimal result for this, we use a DFS + SCC (since all nodes in a
01497 /// cycle must have the same value number since the = operation is really
01498 /// inclusion, not overwrite), and value number nodes we receive points-to sets
01499 /// before we value our own node.
01500 /// The advantage of HU over HVN is that HU considers the inclusion property, so
01501 /// that if you have
01502 /// E = &D
01503 /// E = &C
01504 /// E = F
01505 /// F = G
01506 /// F = &D
01507 /// G = F
01508 /// HU will determine that G == F == E.  HVN will not, because it cannot prove
01509 /// that the points to information ends up being the same because they all
01510 /// receive &D from E anyway.
01511 
01512 void Andersens::HVN() {
01513   DOUT << "Beginning HVN\n";
01514   // Build a predecessor graph.  This is like our constraint graph with the
01515   // edges going in the opposite direction, and there are edges for all the
01516   // constraints, instead of just copy constraints.  We also build implicit
01517   // edges for constraints are implied but not explicit.  I.E for the constraint
01518   // a = &b, we add implicit edges *a = b.  This helps us capture more cycles
01519   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
01520     Constraint &C = Constraints[i];
01521     if (C.Type == Constraint::AddressOf) {
01522       GraphNodes[C.Src].AddressTaken = true;
01523       GraphNodes[C.Src].Direct = false;
01524 
01525       // Dest = &src edge
01526       unsigned AdrNode = C.Src + FirstAdrNode;
01527       if (!GraphNodes[C.Dest].PredEdges)
01528         GraphNodes[C.Dest].PredEdges = new SparseBitVector<>;
01529       GraphNodes[C.Dest].PredEdges->set(AdrNode);
01530 
01531       // *Dest = src edge
01532       unsigned RefNode = C.Dest + FirstRefNode;
01533       if (!GraphNodes[RefNode].ImplicitPredEdges)
01534         GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>;
01535       GraphNodes[RefNode].ImplicitPredEdges->set(C.Src);
01536     } else if (C.Type == Constraint::Load) {
01537       if (C.Offset == 0) {
01538         // dest = *src edge
01539         if (!GraphNodes[C.Dest].PredEdges)
01540           GraphNodes[C.Dest].PredEdges = new SparseBitVector<>;
01541         GraphNodes[C.Dest].PredEdges->set(C.Src + FirstRefNode);
01542       } else {
01543         GraphNodes[C.Dest].Direct = false;
01544       }
01545     } else if (C.Type == Constraint::Store) {
01546       if (C.Offset == 0) {
01547         // *dest = src edge
01548         unsigned RefNode = C.Dest + FirstRefNode;
01549         if (!GraphNodes[RefNode].PredEdges)
01550           GraphNodes[RefNode].PredEdges = new SparseBitVector<>;
01551         GraphNodes[RefNode].PredEdges->set(C.Src);
01552       }
01553     } else {
01554       // Dest = Src edge and *Dest = *Src edge
01555       if (!GraphNodes[C.Dest].PredEdges)
01556         GraphNodes[C.Dest].PredEdges = new SparseBitVector<>;
01557       GraphNodes[C.Dest].PredEdges->set(C.Src);
01558       unsigned RefNode = C.Dest + FirstRefNode;
01559       if (!GraphNodes[RefNode].ImplicitPredEdges)
01560         GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>;
01561       GraphNodes[RefNode].ImplicitPredEdges->set(C.Src + FirstRefNode);
01562     }
01563   }
01564   PEClass = 1;
01565   // Do SCC finding first to condense our predecessor graph
01566   DFSNumber = 0;
01567   Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0);
01568   Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false);
01569   Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false);
01570 
01571   for (unsigned i = 0; i < FirstRefNode; ++i) {
01572     unsigned Node = VSSCCRep[i];
01573     if (!Node2Visited[Node])
01574       HVNValNum(Node);
01575   }
01576   for (BitVectorMap::iterator Iter = Set2PEClass.begin();
01577        Iter != Set2PEClass.end();
01578        ++Iter)
01579     delete Iter->first;
01580   Set2PEClass.clear();
01581   Node2DFS.clear();
01582   Node2Deleted.clear();
01583   Node2Visited.clear();
01584   DOUT << "Finished HVN\n";
01585 
01586 }
01587 
01588 /// This is the workhorse of HVN value numbering. We combine SCC finding at the
01589 /// same time because it's easy.
01590 void Andersens::HVNValNum(unsigned NodeIndex) {
01591   unsigned MyDFS = DFSNumber++;
01592   Node *N = &GraphNodes[NodeIndex];
01593   Node2Visited[NodeIndex] = true;
01594   Node2DFS[NodeIndex] = MyDFS;
01595 
01596   // First process all our explicit edges
01597   if (N->PredEdges)
01598     for (SparseBitVector<>::iterator Iter = N->PredEdges->begin();
01599          Iter != N->PredEdges->end();
01600          ++Iter) {
01601       unsigned j = VSSCCRep[*Iter];
01602       if (!Node2Deleted[j]) {
01603         if (!Node2Visited[j])
01604           HVNValNum(j);
01605         if (Node2DFS[NodeIndex] > Node2DFS[j])
01606           Node2DFS[NodeIndex] = Node2DFS[j];
01607       }
01608     }
01609 
01610   // Now process all the implicit edges
01611   if (N->ImplicitPredEdges)
01612     for (SparseBitVector<>::iterator Iter = N->ImplicitPredEdges->begin();
01613          Iter != N->ImplicitPredEdges->end();
01614          ++Iter) {
01615       unsigned j = VSSCCRep[*Iter];
01616       if (!Node2Deleted[j]) {
01617         if (!Node2Visited[j])
01618           HVNValNum(j);
01619         if (Node2DFS[NodeIndex] > Node2DFS[j])
01620           Node2DFS[NodeIndex] = Node2DFS[j];
01621       }
01622     }
01623 
01624   // See if we found any cycles
01625   if (MyDFS == Node2DFS[NodeIndex]) {
01626     while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) {
01627       unsigned CycleNodeIndex = SCCStack.top();
01628       Node *CycleNode = &GraphNodes[CycleNodeIndex];
01629       VSSCCRep[CycleNodeIndex] = NodeIndex;
01630       // Unify the nodes
01631       N->Direct &= CycleNode->Direct;
01632 
01633       if (CycleNode->PredEdges) {
01634         if (!N->PredEdges)
01635           N->PredEdges = new SparseBitVector<>;
01636         *(N->PredEdges) |= CycleNode->PredEdges;
01637         delete CycleNode->PredEdges;
01638         CycleNode->PredEdges = NULL;
01639       }
01640       if (CycleNode->ImplicitPredEdges) {
01641         if (!N->ImplicitPredEdges)
01642           N->ImplicitPredEdges = new SparseBitVector<>;
01643         *(N->ImplicitPredEdges) |= CycleNode->ImplicitPredEdges;
01644         delete CycleNode->ImplicitPredEdges;
01645         CycleNode->ImplicitPredEdges = NULL;
01646       }
01647 
01648       SCCStack.pop();
01649     }
01650 
01651     Node2Deleted[NodeIndex] = true;
01652 
01653     if (!N->Direct) {
01654       GraphNodes[NodeIndex].PointerEquivLabel = PEClass++;
01655       return;
01656     }
01657 
01658     // Collect labels of successor nodes
01659     bool AllSame = true;
01660     unsigned First = ~0;
01661     SparseBitVector<> *Labels = new SparseBitVector<>;
01662     bool Used = false;
01663 
01664     if (N->PredEdges)
01665       for (SparseBitVector<>::iterator Iter = N->PredEdges->begin();
01666            Iter != N->PredEdges->end();
01667          ++Iter) {
01668         unsigned j = VSSCCRep[*Iter];
01669         unsigned Label = GraphNodes[j].PointerEquivLabel;
01670         // Ignore labels that are equal to us or non-pointers
01671         if (j == NodeIndex || Label == 0)
01672           continue;
01673         if (First == (unsigned)~0)
01674           First = Label;
01675         else if (First != Label)
01676           AllSame = false;
01677         Labels->set(Label);
01678     }
01679 
01680     // We either have a non-pointer, a copy of an existing node, or a new node.
01681     // Assign the appropriate pointer equivalence label.
01682     if (Labels->empty()) {
01683       GraphNodes[NodeIndex].PointerEquivLabel = 0;
01684     } else if (AllSame) {
01685       GraphNodes[NodeIndex].PointerEquivLabel = First;
01686     } else {
01687       GraphNodes[NodeIndex].PointerEquivLabel = Set2PEClass[Labels];
01688       if (GraphNodes[NodeIndex].PointerEquivLabel == 0) {
01689         unsigned EquivClass = PEClass++;
01690         Set2PEClass[Labels] = EquivClass;
01691         GraphNodes[NodeIndex].PointerEquivLabel = EquivClass;
01692         Used = true;
01693       }
01694     }
01695     if (!Used)
01696       delete Labels;
01697   } else {
01698     SCCStack.push(NodeIndex);
01699   }
01700 }
01701 
01702 /// The technique used here is described in "Exploiting Pointer and Location
01703 /// Equivalence to Optimize Pointer Analysis. In the 14th International Static
01704 /// Analysis Symposium (SAS), August 2007."  It is known as the "HU" algorithm,
01705 /// and is equivalent to value numbering the collapsed constraint graph
01706 /// including evaluating unions.
01707 void Andersens::HU() {
01708   DOUT << "Beginning HU\n";
01709   // Build a predecessor graph.  This is like our constraint graph with the
01710   // edges going in the opposite direction, and there are edges for all the
01711   // constraints, instead of just copy constraints.  We also build implicit
01712   // edges for constraints are implied but not explicit.  I.E for the constraint
01713   // a = &b, we add implicit edges *a = b.  This helps us capture more cycles
01714   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
01715     Constraint &C = Constraints[i];
01716     if (C.Type == Constraint::AddressOf) {
01717       GraphNodes[C.Src].AddressTaken = true;
01718       GraphNodes[C.Src].Direct = false;
01719 
01720       GraphNodes[C.Dest].PointsTo->set(C.Src);
01721       // *Dest = src edge
01722       unsigned RefNode = C.Dest + FirstRefNode;
01723       if (!GraphNodes[RefNode].ImplicitPredEdges)
01724         GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>;
01725       GraphNodes[RefNode].ImplicitPredEdges->set(C.Src);
01726       GraphNodes[C.Src].PointedToBy->set(C.Dest);
01727     } else if (C.Type == Constraint::Load) {
01728       if (C.Offset == 0) {
01729         // dest = *src edge
01730         if (!GraphNodes[C.Dest].PredEdges)
01731           GraphNodes[C.Dest].PredEdges = new SparseBitVector<>;
01732         GraphNodes[C.Dest].PredEdges->set(C.Src + FirstRefNode);
01733       } else {
01734         GraphNodes[C.Dest].Direct = false;
01735       }
01736     } else if (C.Type == Constraint::Store) {
01737       if (C.Offset == 0) {
01738         // *dest = src edge
01739         unsigned RefNode = C.Dest + FirstRefNode;
01740         if (!GraphNodes[RefNode].PredEdges)
01741           GraphNodes[RefNode].PredEdges = new SparseBitVector<>;
01742         GraphNodes[RefNode].PredEdges->set(C.Src);
01743       }
01744     } else {
01745       // Dest = Src edge and *Dest = *Src edg
01746       if (!GraphNodes[C.Dest].PredEdges)
01747         GraphNodes[C.Dest].PredEdges = new SparseBitVector<>;
01748       GraphNodes[C.Dest].PredEdges->set(C.Src);
01749       unsigned RefNode = C.Dest + FirstRefNode;
01750       if (!GraphNodes[RefNode].ImplicitPredEdges)
01751         GraphNodes[RefNode].ImplicitPredEdges = new SparseBitVector<>;
01752       GraphNodes[RefNode].ImplicitPredEdges->set(C.Src + FirstRefNode);
01753     }
01754   }
01755   PEClass = 1;
01756   // Do SCC finding first to condense our predecessor graph
01757   DFSNumber = 0;
01758   Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0);
01759   Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false);
01760   Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false);
01761 
01762   for (unsigned i = 0; i < FirstRefNode; ++i) {
01763     if (FindNode(i) == i) {
01764       unsigned Node = VSSCCRep[i];
01765       if (!Node2Visited[Node])
01766         Condense(Node);
01767     }
01768   }
01769 
01770   // Reset tables for actual labeling
01771   Node2DFS.clear();
01772   Node2Visited.clear();
01773   Node2Deleted.clear();
01774   // Pre-grow our densemap so that we don't get really bad behavior
01775   Set2PEClass.resize(GraphNodes.size());
01776 
01777   // Visit the condensed graph and generate pointer equivalence labels.
01778   Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false);
01779   for (unsigned i = 0; i < FirstRefNode; ++i) {
01780     if (FindNode(i) == i) {
01781       unsigned Node = VSSCCRep[i];
01782       if (!Node2Visited[Node])
01783         HUValNum(Node);
01784     }
01785   }
01786   // PEClass nodes will be deleted by the deleting of N->PointsTo in our caller.
01787   Set2PEClass.clear();
01788   DOUT << "Finished HU\n";
01789 }
01790 
01791 
01792 /// Implementation of standard Tarjan SCC algorithm as modified by Nuutilla.
01793 void Andersens::Condense(unsigned NodeIndex) {
01794   unsigned MyDFS = DFSNumber++;
01795   Node *N = &GraphNodes[NodeIndex];
01796   Node2Visited[NodeIndex] = true;
01797   Node2DFS[NodeIndex] = MyDFS;
01798 
01799   // First process all our explicit edges
01800   if (N->PredEdges)
01801     for (SparseBitVector<>::iterator Iter = N->PredEdges->begin();
01802          Iter != N->PredEdges->end();
01803          ++Iter) {
01804       unsigned j = VSSCCRep[*Iter];
01805       if (!Node2Deleted[j]) {
01806         if (!Node2Visited[j])
01807           Condense(j);
01808         if (Node2DFS[NodeIndex] > Node2DFS[j])
01809           Node2DFS[NodeIndex] = Node2DFS[j];
01810       }
01811     }
01812 
01813   // Now process all the implicit edges
01814   if (N->ImplicitPredEdges)
01815     for (SparseBitVector<>::iterator Iter = N->ImplicitPredEdges->begin();
01816          Iter != N->ImplicitPredEdges->end();
01817          ++Iter) {
01818       unsigned j = VSSCCRep[*Iter];
01819       if (!Node2Deleted[j]) {
01820         if (!Node2Visited[j])
01821           Condense(j);
01822         if (Node2DFS[NodeIndex] > Node2DFS[j])
01823           Node2DFS[NodeIndex] = Node2DFS[j];
01824       }
01825     }
01826 
01827   // See if we found any cycles
01828   if (MyDFS == Node2DFS[NodeIndex]) {
01829     while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) {
01830       unsigned CycleNodeIndex = SCCStack.top();
01831       Node *CycleNode = &GraphNodes[CycleNodeIndex];
01832       VSSCCRep[CycleNodeIndex] = NodeIndex;
01833       // Unify the nodes
01834       N->Direct &= CycleNode->Direct;
01835 
01836       *(N->PointsTo) |= CycleNode->PointsTo;
01837       delete CycleNode->PointsTo;
01838       CycleNode->PointsTo = NULL;
01839       if (CycleNode->PredEdges) {
01840         if (!N->PredEdges)
01841           N->PredEdges = new SparseBitVector<>;
01842         *(N->PredEdges) |= CycleNode->PredEdges;
01843         delete CycleNode->PredEdges;
01844         CycleNode->PredEdges = NULL;
01845       }
01846       if (CycleNode->ImplicitPredEdges) {
01847         if (!N->ImplicitPredEdges)
01848           N->ImplicitPredEdges = new SparseBitVector<>;
01849         *(N->ImplicitPredEdges) |= CycleNode->ImplicitPredEdges;
01850         delete CycleNode->ImplicitPredEdges;
01851         CycleNode->ImplicitPredEdges = NULL;
01852       }
01853       SCCStack.pop();
01854     }
01855 
01856     Node2Deleted[NodeIndex] = true;
01857 
01858     // Set up number of incoming edges for other nodes
01859     if (N->PredEdges)
01860       for (SparseBitVector<>::iterator Iter = N->PredEdges->begin();
01861            Iter != N->PredEdges->end();
01862            ++Iter)
01863         ++GraphNodes[VSSCCRep[*Iter]].NumInEdges;
01864   } else {
01865     SCCStack.push(NodeIndex);
01866   }
01867 }
01868 
01869 void Andersens::HUValNum(unsigned NodeIndex) {
01870   Node *N = &GraphNodes[NodeIndex];
01871   Node2Visited[NodeIndex] = true;
01872 
01873   // Eliminate dereferences of non-pointers for those non-pointers we have
01874   // already identified.  These are ref nodes whose non-ref node:
01875   // 1. Has already been visited determined to point to nothing (and thus, a
01876   // dereference of it must point to nothing)
01877   // 2. Any direct node with no predecessor edges in our graph and with no
01878   // points-to set (since it can't point to anything either, being that it
01879   // receives no points-to sets and has none).
01880   if (NodeIndex >= FirstRefNode) {
01881     unsigned j = VSSCCRep[FindNode(NodeIndex - FirstRefNode)];
01882     if ((Node2Visited[j] && !GraphNodes[j].PointerEquivLabel)
01883         || (GraphNodes[j].Direct && !GraphNodes[j].PredEdges
01884             && GraphNodes[j].PointsTo->empty())){
01885       return;
01886     }
01887   }
01888     // Process all our explicit edges
01889   if (N->PredEdges)
01890     for (SparseBitVector<>::iterator Iter = N->PredEdges->begin();
01891          Iter != N->PredEdges->end();
01892          ++Iter) {
01893       unsigned j = VSSCCRep[*Iter];
01894       if (!Node2Visited[j])
01895         HUValNum(j);
01896 
01897       // If this edge turned out to be the same as us, or got no pointer
01898       // equivalence label (and thus points to nothing) , just decrement our
01899       // incoming edges and continue.
01900       if (j == NodeIndex || GraphNodes[j].PointerEquivLabel == 0) {
01901         --GraphNodes[j].NumInEdges;
01902         continue;
01903       }
01904 
01905       *(N->PointsTo) |= GraphNodes[j].PointsTo;
01906 
01907       // If we didn't end up storing this in the hash, and we're done with all
01908       // the edges, we don't need the points-to set anymore.
01909       --GraphNodes[j].NumInEdges;
01910       if (!GraphNodes[j].NumInEdges && !GraphNodes[j].StoredInHash) {
01911         delete GraphNodes[j].PointsTo;
01912         GraphNodes[j].PointsTo = NULL;
01913       }
01914     }
01915   // If this isn't a direct node, generate a fresh variable.
01916   if (!N->Direct) {
01917     N->PointsTo->set(FirstRefNode + NodeIndex);
01918   }
01919 
01920   // See If we have something equivalent to us, if not, generate a new
01921   // equivalence class.
01922   if (N->PointsTo->empty()) {
01923     delete N->PointsTo;
01924     N->PointsTo = NULL;
01925   } else {
01926     if (N->Direct) {
01927       N->PointerEquivLabel = Set2PEClass[N->PointsTo];
01928       if (N->PointerEquivLabel == 0) {
01929         unsigned EquivClass = PEClass++;
01930         N->StoredInHash = true;
01931         Set2PEClass[N->PointsTo] = EquivClass;
01932         N->PointerEquivLabel = EquivClass;
01933       }
01934     } else {
01935       N->PointerEquivLabel = PEClass++;
01936     }
01937   }
01938 }
01939 
01940 /// Rewrite our list of constraints so that pointer equivalent nodes are
01941 /// replaced by their the pointer equivalence class representative.
01942 void Andersens::RewriteConstraints() {
01943   std::vector<Constraint> NewConstraints;
01944   DenseSet<Constraint, ConstraintKeyInfo> Seen;
01945 
01946   PEClass2Node.clear();
01947   PENLEClass2Node.clear();
01948 
01949   // We may have from 1 to Graphnodes + 1 equivalence classes.
01950   PEClass2Node.insert(PEClass2Node.begin(), GraphNodes.size() + 1, -1);
01951   PENLEClass2Node.insert(PENLEClass2Node.begin(), GraphNodes.size() + 1, -1);
01952 
01953   // Rewrite constraints, ignoring non-pointer constraints, uniting equivalent
01954   // nodes, and rewriting constraints to use the representative nodes.
01955   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
01956     Constraint &C = Constraints[i];
01957     unsigned RHSNode = FindNode(C.Src);
01958     unsigned LHSNode = FindNode(C.Dest);
01959     unsigned RHSLabel = GraphNodes[VSSCCRep[RHSNode]].PointerEquivLabel;
01960     unsigned LHSLabel = GraphNodes[VSSCCRep[LHSNode]].PointerEquivLabel;
01961 
01962     // First we try to eliminate constraints for things we can prove don't point
01963     // to anything.
01964     if (LHSLabel == 0) {
01965       DEBUG(PrintNode(&GraphNodes[LHSNode]));
01966       DOUT << " is a non-pointer, ignoring constraint.\n";
01967       continue;
01968     }
01969     if (RHSLabel == 0) {
01970       DEBUG(PrintNode(&GraphNodes[RHSNode]));
01971       DOUT << " is a non-pointer, ignoring constraint.\n";
01972       continue;
01973     }
01974     // This constraint may be useless, and it may become useless as we translate
01975     // it.
01976     if (C.Src == C.Dest && C.Type == Constraint::Copy)
01977       continue;
01978 
01979     C.Src = FindEquivalentNode(RHSNode, RHSLabel);
01980     C.Dest = FindEquivalentNode(FindNode(LHSNode), LHSLabel);
01981     if ((C.Src == C.Dest && C.Type == Constraint::Copy)
01982         || Seen.count(C))
01983       continue;
01984 
01985     Seen.insert(C);
01986     NewConstraints.push_back(C);
01987   }
01988   Constraints.swap(NewConstraints);
01989   PEClass2Node.clear();
01990 }
01991 
01992 /// See if we have a node that is pointer equivalent to the one being asked
01993 /// about, and if so, unite them and return the equivalent node.  Otherwise,
01994 /// return the original node.
01995 unsigned Andersens::FindEquivalentNode(unsigned NodeIndex,
01996                                        unsigned NodeLabel) {
01997   if (!GraphNodes[NodeIndex].AddressTaken) {
01998     if (PEClass2Node[NodeLabel] != -1) {
01999       // We found an existing node with the same pointer label, so unify them.
02000       // We specifically request that Union-By-Rank not be used so that
02001       // PEClass2Node[NodeLabel] U= NodeIndex and not the other way around.
02002       return UniteNodes(PEClass2Node[NodeLabel], NodeIndex, false);
02003     } else {
02004       PEClass2Node[NodeLabel] = NodeIndex;
02005       PENLEClass2Node[NodeLabel] = NodeIndex;
02006     }
02007   } else if (PENLEClass2Node[NodeLabel] == -1) {
02008     PENLEClass2Node[NodeLabel] = NodeIndex;
02009   }
02010 
02011   return NodeIndex;
02012 }
02013 
02014 void Andersens::PrintLabels() const {
02015   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02016     if (i < FirstRefNode) {
02017       PrintNode(&GraphNodes[i]);
02018     } else if (i < FirstAdrNode) {
02019       DOUT << "REF(";
02020       PrintNode(&GraphNodes[i-FirstRefNode]);
02021       DOUT <<")";
02022     } else {
02023       DOUT << "ADR(";
02024       PrintNode(&GraphNodes[i-FirstAdrNode]);
02025       DOUT <<")";
02026     }
02027 
02028     DOUT << " has pointer label " << GraphNodes[i].PointerEquivLabel
02029          << " and SCC rep " << VSSCCRep[i]
02030          << " and is " << (GraphNodes[i].Direct ? "Direct" : "Not direct")
02031          << "\n";
02032   }
02033 }
02034 
02035 /// The technique used here is described in "The Ant and the
02036 /// Grasshopper: Fast and Accurate Pointer Analysis for Millions of
02037 /// Lines of Code. In Programming Language Design and Implementation
02038 /// (PLDI), June 2007." It is known as the "HCD" (Hybrid Cycle
02039 /// Detection) algorithm. It is called a hybrid because it performs an
02040 /// offline analysis and uses its results during the solving (online)
02041 /// phase. This is just the offline portion; the results of this
02042 /// operation are stored in SDT and are later used in SolveContraints()
02043 /// and UniteNodes().
02044 void Andersens::HCD() {
02045   DOUT << "Starting HCD.\n";
02046   HCDSCCRep.resize(GraphNodes.size());
02047 
02048   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02049     GraphNodes[i].Edges = new SparseBitVector<>;
02050     HCDSCCRep[i] = i;
02051   }
02052 
02053   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
02054     Constraint &C = Constraints[i];
02055     assert (C.Src < GraphNodes.size() && C.Dest < GraphNodes.size());
02056     if (C.Type == Constraint::AddressOf) {
02057       continue;
02058     } else if (C.Type == Constraint::Load) {
02059       if( C.Offset == 0 )
02060         GraphNodes[C.Dest].Edges->set(C.Src + FirstRefNode);
02061     } else if (C.Type == Constraint::Store) {
02062       if( C.Offset == 0 )
02063         GraphNodes[C.Dest + FirstRefNode].Edges->set(C.Src);
02064     } else {
02065       GraphNodes[C.Dest].Edges->set(C.Src);
02066     }
02067   }
02068 
02069   Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0);
02070   Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false);
02071   Node2Visited.insert(Node2Visited.begin(), GraphNodes.size(), false);
02072   SDT.insert(SDT.begin(), GraphNodes.size() / 2, -1);
02073 
02074   DFSNumber = 0;
02075   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02076     unsigned Node = HCDSCCRep[i];
02077     if (!Node2Deleted[Node])
02078       Search(Node);
02079   }
02080 
02081   for (unsigned i = 0; i < GraphNodes.size(); ++i)
02082     if (GraphNodes[i].Edges != NULL) {
02083       delete GraphNodes[i].Edges;
02084       GraphNodes[i].Edges = NULL;
02085     }
02086 
02087   while( !SCCStack.empty() )
02088     SCCStack.pop();
02089 
02090   Node2DFS.clear();
02091   Node2Visited.clear();
02092   Node2Deleted.clear();
02093   HCDSCCRep.clear();
02094   DOUT << "HCD complete.\n";
02095 }
02096 
02097 // Component of HCD: 
02098 // Use Nuutila's variant of Tarjan's algorithm to detect
02099 // Strongly-Connected Components (SCCs). For non-trivial SCCs
02100 // containing ref nodes, insert the appropriate information in SDT.
02101 void Andersens::Search(unsigned Node) {
02102   unsigned MyDFS = DFSNumber++;
02103 
02104   Node2Visited[Node] = true;
02105   Node2DFS[Node] = MyDFS;
02106 
02107   for (SparseBitVector<>::iterator Iter = GraphNodes[Node].Edges->begin(),
02108                                    End  = GraphNodes[Node].Edges->end();
02109        Iter != End;
02110        ++Iter) {
02111     unsigned J = HCDSCCRep[*Iter];
02112     assert(GraphNodes[J].isRep() && "Debug check; must be representative");
02113     if (!Node2Deleted[J]) {
02114       if (!Node2Visited[J])
02115         Search(J);
02116       if (Node2DFS[Node] > Node2DFS[J])
02117         Node2DFS[Node] = Node2DFS[J];
02118     }
02119   }
02120 
02121   if( MyDFS != Node2DFS[Node] ) {
02122     SCCStack.push(Node);
02123     return;
02124   }
02125 
02126   // This node is the root of a SCC, so process it.
02127   //
02128   // If the SCC is "non-trivial" (not a singleton) and contains a reference 
02129   // node, we place this SCC into SDT.  We unite the nodes in any case.
02130   if (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS) {
02131     SparseBitVector<> SCC;
02132 
02133     SCC.set(Node);
02134 
02135     bool Ref = (Node >= FirstRefNode);
02136 
02137     Node2Deleted[Node] = true;
02138 
02139     do {
02140       unsigned P = SCCStack.top(); SCCStack.pop();
02141       Ref |= (P >= FirstRefNode);
02142       SCC.set(P);
02143       HCDSCCRep[P] = Node;
02144     } while (!SCCStack.empty() && Node2DFS[SCCStack.top()] >= MyDFS);
02145 
02146     if (Ref) {
02147       unsigned Rep = SCC.find_first();
02148       assert(Rep < FirstRefNode && "The SCC didn't have a non-Ref node!");
02149 
02150       SparseBitVector<>::iterator i = SCC.begin();
02151 
02152       // Skip over the non-ref nodes
02153       while( *i < FirstRefNode )
02154         ++i;
02155 
02156       while( i != SCC.end() )
02157         SDT[ (*i++) - FirstRefNode ] = Rep;
02158     }
02159   }
02160 }
02161 
02162 
02163 /// Optimize the constraints by performing offline variable substitution and
02164 /// other optimizations.
02165 void Andersens::OptimizeConstraints() {
02166   DOUT << "Beginning constraint optimization\n";
02167 
02168   SDTActive = false;
02169 
02170   // Function related nodes need to stay in the same relative position and can't
02171   // be location equivalent.
02172   for (std::map<unsigned, unsigned>::iterator Iter = MaxK.begin();
02173        Iter != MaxK.end();
02174        ++Iter) {
02175     for (unsigned i = Iter->first;
02176          i != Iter->first + Iter->second;
02177          ++i) {
02178       GraphNodes[i].AddressTaken = true;
02179       GraphNodes[i].Direct = false;
02180     }
02181   }
02182 
02183   ClumpAddressTaken();
02184   FirstRefNode = GraphNodes.size();
02185   FirstAdrNode = FirstRefNode + GraphNodes.size();
02186   GraphNodes.insert(GraphNodes.end(), 2 * GraphNodes.size(),
02187                     Node(false));
02188   VSSCCRep.resize(GraphNodes.size());
02189   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02190     VSSCCRep[i] = i;
02191   }
02192   HVN();
02193   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02194     Node *N = &GraphNodes[i];
02195     delete N->PredEdges;
02196     N->PredEdges = NULL;
02197     delete N->ImplicitPredEdges;
02198     N->ImplicitPredEdges = NULL;
02199   }
02200 #undef DEBUG_TYPE
02201 #define DEBUG_TYPE "anders-aa-labels"
02202   DEBUG(PrintLabels());
02203 #undef DEBUG_TYPE
02204 #define DEBUG_TYPE "anders-aa"
02205   RewriteConstraints();
02206   // Delete the adr nodes.
02207   GraphNodes.resize(FirstRefNode * 2);
02208 
02209   // Now perform HU
02210   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02211     Node *N = &GraphNodes[i];
02212     if (FindNode(i) == i) {
02213       N->PointsTo = new SparseBitVector<>;
02214       N->PointedToBy = new SparseBitVector<>;
02215       // Reset our labels
02216     }
02217     VSSCCRep[i] = i;
02218     N->PointerEquivLabel = 0;
02219   }
02220   HU();
02221 #undef DEBUG_TYPE
02222 #define DEBUG_TYPE "anders-aa-labels"
02223   DEBUG(PrintLabels());
02224 #undef DEBUG_TYPE
02225 #define DEBUG_TYPE "anders-aa"
02226   RewriteConstraints();
02227   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02228     if (FindNode(i) == i) {
02229       Node *N = &GraphNodes[i];
02230       delete N->PointsTo;
02231       N->PointsTo = NULL;
02232       delete N->PredEdges;
02233       N->PredEdges = NULL;
02234       delete N->ImplicitPredEdges;
02235       N->ImplicitPredEdges = NULL;
02236       delete N->PointedToBy;
02237       N->PointedToBy = NULL;
02238     }
02239   }
02240 
02241   // perform Hybrid Cycle Detection (HCD)
02242   HCD();
02243   SDTActive = true;
02244 
02245   // No longer any need for the upper half of GraphNodes (for ref nodes).
02246   GraphNodes.erase(GraphNodes.begin() + FirstRefNode, GraphNodes.end());
02247 
02248   // HCD complete.
02249 
02250   DOUT << "Finished constraint optimization\n";
02251   FirstRefNode = 0;
02252   FirstAdrNode = 0;
02253 }
02254 
02255 /// Unite pointer but not location equivalent variables, now that the constraint
02256 /// graph is built.
02257 void Andersens::UnitePointerEquivalences() {
02258   DOUT << "Uniting remaining pointer equivalences\n";
02259   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02260     if (GraphNodes[i].AddressTaken && GraphNodes[i].isRep()) {
02261       unsigned Label = GraphNodes[i].PointerEquivLabel;
02262 
02263       if (Label && PENLEClass2Node[Label] != -1)
02264         UniteNodes(i, PENLEClass2Node[Label]);
02265     }
02266   }
02267   DOUT << "Finished remaining pointer equivalences\n";
02268   PENLEClass2Node.clear();
02269 }
02270 
02271 /// Create the constraint graph used for solving points-to analysis.
02272 ///
02273 void Andersens::CreateConstraintGraph() {
02274   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
02275     Constraint &C = Constraints[i];
02276     assert (C.Src < GraphNodes.size() && C.Dest < GraphNodes.size());
02277     if (C.Type == Constraint::AddressOf)
02278       GraphNodes[C.Dest].PointsTo->set(C.Src);
02279     else if (C.Type == Constraint::Load)
02280       GraphNodes[C.Src].Constraints.push_back(C);
02281     else if (C.Type == Constraint::Store)
02282       GraphNodes[C.Dest].Constraints.push_back(C);
02283     else if (C.Offset != 0)
02284       GraphNodes[C.Src].Constraints.push_back(C);
02285     else
02286       GraphNodes[C.Src].Edges->set(C.Dest);
02287   }
02288 }
02289 
02290 // Perform DFS and cycle detection.
02291 bool Andersens::QueryNode(unsigned Node) {
02292   assert(GraphNodes[Node].isRep() && "Querying a non-rep node");
02293   unsigned OurDFS = ++DFSNumber;
02294   SparseBitVector<> ToErase;
02295   SparseBitVector<> NewEdges;
02296   Tarjan2DFS[Node] = OurDFS;
02297 
02298   // Changed denotes a change from a recursive call that we will bubble up.
02299   // Merged is set if we actually merge a node ourselves.
02300   bool Changed = false, Merged = false;
02301 
02302   for (SparseBitVector<>::iterator bi = GraphNodes[Node].Edges->begin();
02303        bi != GraphNodes[Node].Edges->end();
02304        ++bi) {
02305     unsigned RepNode = FindNode(*bi);
02306     // If this edge points to a non-representative node but we are
02307     // already planning to add an edge to its representative, we have no
02308     // need for this edge anymore.
02309     if (RepNode != *bi && NewEdges.test(RepNode)){
02310       ToErase.set(*bi);
02311       continue;
02312     }
02313 
02314     // Continue about our DFS.
02315     if (!Tarjan2Deleted[RepNode]){
02316       if (Tarjan2DFS[RepNode] == 0) {
02317         Changed |= QueryNode(RepNode);
02318         // May have been changed by QueryNode
02319         RepNode = FindNode(RepNode);
02320       }
02321       if (Tarjan2DFS[RepNode] < Tarjan2DFS[Node])
02322         Tarjan2DFS[Node] = Tarjan2DFS[RepNode];
02323     }
02324 
02325     // We may have just discovered that this node is part of a cycle, in
02326     // which case we can also erase it.
02327     if (RepNode != *bi) {
02328       ToErase.set(*bi);
02329       NewEdges.set(RepNode);
02330     }
02331   }
02332 
02333   GraphNodes[Node].Edges->intersectWithComplement(ToErase);
02334   GraphNodes[Node].Edges |= NewEdges;
02335 
02336   // If this node is a root of a non-trivial SCC, place it on our 
02337   // worklist to be processed.
02338   if (OurDFS == Tarjan2DFS[Node]) {
02339     while (!SCCStack.empty() && Tarjan2DFS[SCCStack.top()] >= OurDFS) {
02340       Node = UniteNodes(Node, SCCStack.top());
02341 
02342       SCCStack.pop();
02343       Merged = true;
02344     }
02345     Tarjan2Deleted[Node] = true;
02346 
02347     if (Merged)
02348       NextWL->insert(&GraphNodes[Node]);
02349   } else {
02350     SCCStack.push(Node);
02351   }
02352 
02353   return(Changed | Merged);
02354 }
02355 
02356 /// SolveConstraints - This stage iteratively processes the constraints list
02357 /// propagating constraints (adding edges to the Nodes in the points-to graph)
02358 /// until a fixed point is reached.
02359 ///
02360 /// We use a variant of the technique called "Lazy Cycle Detection", which is
02361 /// described in "The Ant and the Grasshopper: Fast and Accurate Pointer
02362 /// Analysis for Millions of Lines of Code. In Programming Language Design and
02363 /// Implementation (PLDI), June 2007."
02364 /// The paper describes performing cycle detection one node at a time, which can
02365 /// be expensive if there are no cycles, but there are long chains of nodes that
02366 /// it heuristically believes are cycles (because it will DFS from each node
02367 /// without state from previous nodes).
02368 /// Instead, we use the heuristic to build a worklist of nodes to check, then
02369 /// cycle detect them all at the same time to do this more cheaply.  This
02370 /// catches cycles slightly later than the original technique did, but does it
02371 /// make significantly cheaper.
02372 
02373 void Andersens::SolveConstraints() {
02374   CurrWL = &w1;
02375   NextWL = &w2;
02376 
02377   OptimizeConstraints();
02378 #undef DEBUG_TYPE
02379 #define DEBUG_TYPE "anders-aa-constraints"
02380       DEBUG(PrintConstraints());
02381 #undef DEBUG_TYPE
02382 #define DEBUG_TYPE "anders-aa"
02383 
02384   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02385     Node *N = &GraphNodes[i];
02386     N->PointsTo = new SparseBitVector<>;
02387     N->OldPointsTo = new SparseBitVector<>;
02388     N->Edges = new SparseBitVector<>;
02389   }
02390   CreateConstraintGraph();
02391   UnitePointerEquivalences();
02392   assert(SCCStack.empty() && "SCC Stack should be empty by now!");
02393   Node2DFS.clear();
02394   Node2Deleted.clear();
02395   Node2DFS.insert(Node2DFS.begin(), GraphNodes.size(), 0);
02396   Node2Deleted.insert(Node2Deleted.begin(), GraphNodes.size(), false);
02397   DFSNumber = 0;
02398   DenseSet<Constraint, ConstraintKeyInfo> Seen;
02399   DenseSet<std::pair<unsigned,unsigned>, PairKeyInfo> EdgesChecked;
02400 
02401   // Order graph and add initial nodes to work list.
02402   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02403     Node *INode = &GraphNodes[i];
02404 
02405     // Add to work list if it's a representative and can contribute to the
02406     // calculation right now.
02407     if (INode->isRep() && !INode->PointsTo->empty()
02408         && (!INode->Edges->empty() || !INode->Constraints.empty())) {
02409       INode->Stamp();
02410       CurrWL->insert(INode);
02411     }
02412   }
02413   std::queue<unsigned int> TarjanWL;
02414 #if !FULL_UNIVERSAL
02415   // "Rep and special variables" - in order for HCD to maintain conservative
02416   // results when !FULL_UNIVERSAL, we need to treat the special variables in
02417   // the same way that the !FULL_UNIVERSAL tweak does throughout the rest of
02418   // the analysis - it's ok to add edges from the special nodes, but never
02419   // *to* the special nodes.
02420   std::vector<unsigned int> RSV;
02421 #endif
02422   while( !CurrWL->empty() ) {
02423     DOUT << "Starting iteration #" << ++NumIters << "\n";
02424 
02425     Node* CurrNode;
02426     unsigned CurrNodeIndex;
02427 
02428     // Actual cycle checking code.  We cycle check all of the lazy cycle
02429     // candidates from the last iteration in one go.
02430     if (!TarjanWL.empty()) {
02431       DFSNumber = 0;
02432       
02433       Tarjan2DFS.clear();
02434       Tarjan2Deleted.clear();
02435       while (!TarjanWL.empty()) {
02436         unsigned int ToTarjan = TarjanWL.front();
02437         TarjanWL.pop();
02438         if (!Tarjan2Deleted[ToTarjan]
02439             && GraphNodes[ToTarjan].isRep()
02440             && Tarjan2DFS[ToTarjan] == 0)
02441           QueryNode(ToTarjan);
02442       }
02443     }
02444     
02445     // Add to work list if it's a representative and can contribute to the
02446     // calculation right now.
02447     while( (CurrNode = CurrWL->pop()) != NULL ) {
02448       CurrNodeIndex = CurrNode - &GraphNodes[0];
02449       CurrNode->Stamp();
02450       
02451           
02452       // Figure out the changed points to bits
02453       SparseBitVector<> CurrPointsTo;
02454       CurrPointsTo.intersectWithComplement(CurrNode->PointsTo,
02455                                            CurrNode->OldPointsTo);
02456       if (CurrPointsTo.empty())
02457         continue;
02458 
02459       *(CurrNode->OldPointsTo) |= CurrPointsTo;
02460 
02461       // Check the offline-computed equivalencies from HCD.
02462       bool SCC = false;
02463       unsigned Rep;
02464 
02465       if (SDT[CurrNodeIndex] >= 0) {
02466         SCC = true;
02467         Rep = FindNode(SDT[CurrNodeIndex]);
02468 
02469 #if !FULL_UNIVERSAL
02470         RSV.clear();
02471 #endif
02472         for (SparseBitVector<>::iterator bi = CurrPointsTo.begin();
02473              bi != CurrPointsTo.end(); ++bi) {
02474           unsigned Node = FindNode(*bi);
02475 #if !FULL_UNIVERSAL
02476           if (Node < NumberSpecialNodes) {
02477             RSV.push_back(Node);
02478             continue;
02479           }
02480 #endif
02481           Rep = UniteNodes(Rep,Node);
02482         }
02483 #if !FULL_UNIVERSAL
02484         RSV.push_back(Rep);
02485 #endif
02486 
02487         NextWL->insert(&GraphNodes[Rep]);
02488 
02489         if ( ! CurrNode->isRep() )
02490           continue;
02491       }
02492 
02493       Seen.clear();
02494 
02495       /* Now process the constraints for this node.  */
02496       for (std::list<Constraint>::iterator li = CurrNode->Constraints.begin();
02497            li != CurrNode->Constraints.end(); ) {
02498         li->Src = FindNode(li->Src);
02499         li->Dest = FindNode(li->Dest);
02500 
02501         // Delete redundant constraints
02502         if( Seen.count(*li) ) {
02503           std::list<Constraint>::iterator lk = li; li++;
02504 
02505           CurrNode->Constraints.erase(lk);
02506           ++NumErased;
02507           continue;
02508         }
02509         Seen.insert(*li);
02510 
02511         // Src and Dest will be the vars we are going to process.
02512         // This may look a bit ugly, but what it does is allow us to process
02513         // both store and load constraints with the same code.
02514         // Load constraints say that every member of our RHS solution has K
02515         // added to it, and that variable gets an edge to LHS. We also union
02516         // RHS+K's solution into the LHS solution.
02517         // Store constraints say that every member of our LHS solution has K
02518         // added to it, and that variable gets an edge from RHS. We also union
02519         // RHS's solution into the LHS+K solution.
02520         unsigned *Src;
02521         unsigned *Dest;
02522         unsigned K = li->Offset;
02523         unsigned CurrMember;
02524         if (li->Type == Constraint::Load) {
02525           Src = &CurrMember;
02526           Dest = &li->Dest;
02527         } else if (li->Type == Constraint::Store) {
02528           Src = &li->Src;
02529           Dest = &CurrMember;
02530         } else {
02531           // TODO Handle offseted copy constraint
02532           li++;
02533           continue;
02534         }
02535 
02536         // See if we can use Hybrid Cycle Detection (that is, check
02537         // if it was a statically detected offline equivalence that
02538         // involves pointers; if so, remove the redundant constraints).
02539         if( SCC && K == 0 ) {
02540 #if FULL_UNIVERSAL
02541           CurrMember = Rep;
02542 
02543           if (GraphNodes[*Src].Edges->test_and_set(*Dest))
02544             if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo))
02545               NextWL->insert(&GraphNodes[*Dest]);
02546 #else
02547           for (unsigned i=0; i < RSV.size(); ++i) {
02548             CurrMember = RSV[i];
02549 
02550             if (*Dest < NumberSpecialNodes)
02551               continue;
02552             if (GraphNodes[*Src].Edges->test_and_set(*Dest))
02553               if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo))
02554                 NextWL->insert(&GraphNodes[*Dest]);
02555           }
02556 #endif
02557           // since all future elements of the points-to set will be
02558           // equivalent to the current ones, the complex constraints
02559           // become redundant.
02560           //
02561           std::list<Constraint>::iterator lk = li; li++;
02562 #if !FULL_UNIVERSAL
02563           // In this case, we can still erase the constraints when the
02564           // elements of the points-to sets are referenced by *Dest,
02565           // but not when they are referenced by *Src (i.e. for a Load
02566           // constraint). This is because if another special variable is
02567           // put into the points-to set later, we still need to add the
02568           // new edge from that special variable.
02569           if( lk->Type != Constraint::Load)
02570 #endif
02571           GraphNodes[CurrNodeIndex].Constraints.erase(lk);
02572         } else {
02573           const SparseBitVector<> &Solution = CurrPointsTo;
02574 
02575           for (SparseBitVector<>::iterator bi = Solution.begin();
02576                bi != Solution.end();
02577                ++bi) {
02578             CurrMember = *bi;
02579 
02580             // Need to increment the member by K since that is where we are
02581             // supposed to copy to/from.  Note that in positive weight cycles,
02582             // which occur in address taking of fields, K can go past
02583             // MaxK[CurrMember] elements, even though that is all it could point
02584             // to.
02585             if (K > 0 && K > MaxK[CurrMember])
02586               continue;
02587             else
02588               CurrMember = FindNode(CurrMember + K);
02589 
02590             // Add an edge to the graph, so we can just do regular
02591             // bitmap ior next time.  It may also let us notice a cycle.
02592 #if !FULL_UNIVERSAL
02593             if (*Dest < NumberSpecialNodes)
02594               continue;
02595 #endif
02596             if (GraphNodes[*Src].Edges->test_and_set(*Dest))
02597               if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo))
02598                 NextWL->insert(&GraphNodes[*Dest]);
02599 
02600           }
02601           li++;
02602         }
02603       }
02604       SparseBitVector<> NewEdges;
02605       SparseBitVector<> ToErase;
02606 
02607       // Now all we have left to do is propagate points-to info along the
02608       // edges, erasing the redundant edges.
02609       for (SparseBitVector<>::iterator bi = CurrNode->Edges->begin();
02610            bi != CurrNode->Edges->end();
02611            ++bi) {
02612 
02613         unsigned DestVar = *bi;
02614         unsigned Rep = FindNode(DestVar);
02615 
02616         // If we ended up with this node as our destination, or we've already
02617         // got an edge for the representative, delete the current edge.
02618         if (Rep == CurrNodeIndex ||
02619             (Rep != DestVar && NewEdges.test(Rep))) {
02620             ToErase.set(DestVar);
02621             continue;
02622         }
02623         
02624         std::pair<unsigned,unsigned> edge(CurrNodeIndex,Rep);
02625         
02626         // This is where we do lazy cycle detection.
02627         // If this is a cycle candidate (equal points-to sets and this
02628         // particular edge has not been cycle-checked previously), add to the
02629         // list to check for cycles on the next iteration.
02630         if (!EdgesChecked.count(edge) &&
02631             *(GraphNodes[Rep].PointsTo) == *(CurrNode->PointsTo)) {
02632           EdgesChecked.insert(edge);
02633           TarjanWL.push(Rep);
02634         }
02635         // Union the points-to sets into the dest
02636 #if !FULL_UNIVERSAL
02637         if (Rep >= NumberSpecialNodes)
02638 #endif
02639         if (GraphNodes[Rep].PointsTo |= CurrPointsTo) {
02640           NextWL->insert(&GraphNodes[Rep]);
02641         }
02642         // If this edge's destination was collapsed, rewrite the edge.
02643         if (Rep != DestVar) {
02644           ToErase.set(DestVar);
02645           NewEdges.set(Rep);
02646         }
02647       }
02648       CurrNode->Edges->intersectWithComplement(ToErase);
02649       CurrNode->Edges |= NewEdges;
02650     }
02651 
02652     // Switch to other work list.
02653     WorkList* t = CurrWL; CurrWL = NextWL; NextWL = t;
02654   }
02655 
02656 
02657   Node2DFS.clear();
02658   Node2Deleted.clear();
02659   for (unsigned i = 0; i < GraphNodes.size(); ++i) {
02660     Node *N = &GraphNodes[i];
02661     delete N->OldPointsTo;
02662     delete N->Edges;
02663   }
02664   SDTActive = false;
02665   SDT.clear();
02666 }
02667 
02668 //===----------------------------------------------------------------------===//
02669 //                               Union-Find
02670 //===----------------------------------------------------------------------===//
02671 
02672 // Unite nodes First and Second, returning the one which is now the
02673 // representative node.  First and Second are indexes into GraphNodes
02674 unsigned Andersens::UniteNodes(unsigned First, unsigned Second,
02675                                bool UnionByRank) {
02676   assert (First < GraphNodes.size() && Second < GraphNodes.size() &&
02677           "Attempting to merge nodes that don't exist");
02678 
02679   Node *FirstNode = &GraphNodes[First];
02680   Node *SecondNode = &GraphNodes[Second];
02681 
02682   assert (SecondNode->isRep() && FirstNode->isRep() &&
02683           "Trying to unite two non-representative nodes!");
02684   if (First == Second)
02685     return First;
02686 
02687   if (UnionByRank) {
02688     int RankFirst  = (int) FirstNode ->NodeRep;
02689     int RankSecond = (int) SecondNode->NodeRep;
02690 
02691     // Rank starts at -1 and gets decremented as it increases.
02692     // Translation: higher rank, lower NodeRep value, which is always negative.
02693     if (RankFirst > RankSecond) {
02694       unsigned t = First; First = Second; Second = t;
02695       Node* tp = FirstNode; FirstNode = SecondNode; SecondNode = tp;
02696     } else if (RankFirst == RankSecond) {
02697       FirstNode->NodeRep = (unsigned) (RankFirst - 1);
02698     }
02699   }
02700 
02701   SecondNode->NodeRep = First;
02702 #if !FULL_UNIVERSAL
02703   if (First >= NumberSpecialNodes)
02704 #endif
02705   if (FirstNode->PointsTo && SecondNode->PointsTo)
02706     FirstNode->PointsTo |= *(SecondNode->PointsTo);
02707   if (FirstNode->Edges && SecondNode->Edges)
02708     FirstNode->Edges |= *(SecondNode->Edges);
02709   if (!SecondNode->Constraints.empty())
02710     FirstNode->Constraints.splice(FirstNode->Constraints.begin(),
02711                                   SecondNode->Constraints);
02712   if (FirstNode->OldPointsTo) {
02713     delete FirstNode->OldPointsTo;
02714     FirstNode->OldPointsTo = new SparseBitVector<>;
02715   }
02716 
02717   // Destroy interesting parts of the merged-from node.
02718   delete SecondNode->OldPointsTo;
02719   delete SecondNode->Edges;
02720   delete SecondNode->PointsTo;
02721   SecondNode->Edges = NULL;
02722   SecondNode->PointsTo = NULL;
02723   SecondNode->OldPointsTo = NULL;
02724 
02725   NumUnified++;
02726   DOUT << "Unified Node ";
02727   DEBUG(PrintNode(FirstNode));
02728   DOUT << " and Node ";
02729   DEBUG(PrintNode(SecondNode));
02730   DOUT << "\n";
02731 
02732   if (SDTActive)
02733     if (SDT[Second] >= 0) {
02734       if (SDT[First] < 0)
02735         SDT[First] = SDT[Second];
02736       else {
02737         UniteNodes( FindNode(SDT[First]), FindNode(SDT[Second]) );
02738         First = FindNode(First);
02739       }
02740     }
02741 
02742   return First;
02743 }
02744 
02745 // Find the index into GraphNodes of the node representing Node, performing
02746 // path compression along the way
02747 unsigned Andersens::FindNode(unsigned NodeIndex) {
02748   assert (NodeIndex < GraphNodes.size()
02749           && "Attempting to find a node that can't exist");
02750   Node *N = &GraphNodes[NodeIndex];
02751   if (N->isRep())
02752     return NodeIndex;
02753   else
02754     return (N->NodeRep = FindNode(N->NodeRep));
02755 }
02756 
02757 // Find the index into GraphNodes of the node representing Node, 
02758 // don't perform path compression along the way (for Print)
02759 unsigned Andersens::FindNode(unsigned NodeIndex) const {
02760   assert (NodeIndex < GraphNodes.size()
02761           && "Attempting to find a node that can't exist");
02762   const Node *N = &GraphNodes[NodeIndex];
02763   if (N->isRep())
02764     return NodeIndex;
02765   else
02766     return FindNode(N->NodeRep);
02767 }
02768 
02769 //===----------------------------------------------------------------------===//
02770 //                               Debugging Output
02771 //===----------------------------------------------------------------------===//
02772 
02773 void Andersens::PrintNode(const Node *N) const {
02774   if (N == &GraphNodes[UniversalSet]) {
02775     errs() << "<universal>";
02776     return;
02777   } else if (N == &GraphNodes[NullPtr]) {
02778     errs() << "<nullptr>";
02779     return;
02780   } else if (N == &GraphNodes[NullObject]) {
02781     errs() << "<null>";
02782     return;
02783   }
02784   if (!N->getValue()) {
02785     errs() << "artificial" << (intptr_t) N;
02786     return;
02787   }
02788 
02789   assert(N->getValue() != 0 && "Never set node label!");
02790   Value *V = N->getValue();
02791   if (Function *F = dyn_cast<Function>(V)) {
02792     if (isa<PointerType>(F->getFunctionType()->getReturnType()) &&
02793         N == &GraphNodes[getReturnNode(F)]) {
02794       errs() << F->getName() << ":retval";
02795       return;
02796     } else if (F->getFunctionType()->isVarArg() &&
02797                N == &GraphNodes[getVarargNode(F)]) {
02798       errs() << F->getName() << ":vararg";
02799       return;
02800     }
02801   }
02802 
02803   if (Instruction *I = dyn_cast<Instruction>(V))
02804     errs() << I->getParent()->getParent()->getName() << ":";
02805   else if (Argument *Arg = dyn_cast<Argument>(V))
02806     errs() << Arg->getParent()->getName() << ":";
02807 
02808   if (V->hasName())
02809     errs() << V->getName();
02810   else
02811     errs() << "(unnamed)";
02812 
02813   if (isa<GlobalValue>(V) || isa<AllocationInst>(V))
02814     if (N == &GraphNodes[getObject(V)])
02815       errs() << "<mem>";
02816 }
02817 void Andersens::PrintConstraint(const Constraint &C) const {
02818   if (C.Type == Constraint::Store) {
02819     errs() << "*";
02820     if (C.Offset != 0)
02821       errs() << "(";
02822   }
02823   PrintNode(&GraphNodes[C.Dest]);
02824   if (C.Type == Constraint::Store && C.Offset != 0)
02825     errs() << " + " << C.Offset << ")";
02826   errs() << " = ";
02827   if (C.Type == Constraint::Load) {
02828     errs() << "*";
02829     if (C.Offset != 0)
02830       errs() << "(";
02831   }
02832   else if (C.Type == Constraint::AddressOf)
02833     errs() << "&";
02834   PrintNode(&GraphNodes[C.Src]);
02835   if (C.Offset != 0 && C.Type != Constraint::Store)
02836     errs() << " + " << C.Offset;
02837   if (C.Type == Constraint::Load && C.Offset != 0)
02838     errs() << ")";
02839   errs() << "\n";
02840 }
02841 
02842 void Andersens::PrintConstraints() const {
02843   errs() << "Constraints:\n";
02844 
02845   for (unsigned i = 0, e = Constraints.size(); i != e; ++i)
02846     PrintConstraint(Constraints[i]);
02847 }
02848 
02849 void Andersens::PrintPointsToGraph() const {
02850   errs() << "Points-to graph:\n";
02851   for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) {
02852     const Node *N = &GraphNodes[i];
02853     if (FindNode(i) != i) {
02854       PrintNode(N);
02855       errs() << "\t--> same as ";
02856       PrintNode(&GraphNodes[FindNode(i)]);
02857       errs() << "\n";
02858     } else {
02859       errs() << "[" << (N->PointsTo->count()) << "] ";
02860       PrintNode(N);
02861       errs() << "\t--> ";
02862 
02863       bool first = true;
02864       for (SparseBitVector<>::iterator bi = N->PointsTo->begin();
02865            bi != N->PointsTo->end();
02866            ++bi) {
02867         if (!first)
02868           errs() << ", ";
02869         PrintNode(&GraphNodes[*bi]);
02870         first = false;
02871       }
02872       errs() << "\n";
02873     }
02874   }
02875 }