LLVM API Documentation
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 }