LLVM API Documentation
00001 //===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines a very simple implementation of Andersen's interprocedural 00011 // alias analysis. This implementation does not include any of the fancy 00012 // features that make Andersen's reasonably efficient (like cycle elimination or 00013 // variable substitution), but it should be useful for getting precision 00014 // numbers and can be extended in the future. 00015 // 00016 // In pointer analysis terms, this is a subset-based, flow-insensitive, 00017 // field-insensitive, and context-insensitive algorithm pointer algorithm. 00018 // 00019 // This algorithm is implemented as three stages: 00020 // 1. Object identification. 00021 // 2. Inclusion constraint identification. 00022 // 3. Inclusion constraint solving. 00023 // 00024 // The object identification stage identifies all of the memory objects in the 00025 // program, which includes globals, heap allocated objects, and stack allocated 00026 // objects. 00027 // 00028 // The inclusion constraint identification stage finds all inclusion constraints 00029 // in the program by scanning the program, looking for pointer assignments and 00030 // other statements that effect the points-to graph. For a statement like "A = 00031 // B", this statement is processed to indicate that A can point to anything that 00032 // B can point to. Constraints can handle copies, loads, and stores. 00033 // 00034 // The inclusion constraint solving phase iteratively propagates the inclusion 00035 // constraints until a fixed point is reached. This is an O(N^3) algorithm. 00036 // 00037 // In the initial pass, all indirect function calls are completely ignored. As 00038 // the analysis discovers new targets of function pointers, it iteratively 00039 // resolves a precise (and conservative) call graph. Also related, this 00040 // analysis initially assumes that all internal functions have known incoming 00041 // pointers. If we find that an internal function's address escapes outside of 00042 // the program, we update this assumption. 00043 // 00044 // Future Improvements: 00045 // This implementation of Andersen's algorithm is extremely slow. To make it 00046 // scale reasonably well, the inclusion constraints could be sorted (easy), 00047 // offline variable substitution would be a huge win (straight-forward), and 00048 // online cycle elimination (trickier) might help as well. 00049 // 00050 //===----------------------------------------------------------------------===// 00051 00052 #define DEBUG_TYPE "anders-aa" 00053 #include "llvm/Constants.h" 00054 #include "llvm/DerivedTypes.h" 00055 #include "llvm/Instructions.h" 00056 #include "llvm/Module.h" 00057 #include "llvm/Pass.h" 00058 #include "llvm/Support/InstIterator.h" 00059 #include "llvm/Support/InstVisitor.h" 00060 #include "llvm/Analysis/AliasAnalysis.h" 00061 #include "llvm/Analysis/Passes.h" 00062 #include "llvm/Support/Debug.h" 00063 #include "llvm/ADT/Statistic.h" 00064 #include <set> 00065 #include <iostream> 00066 using namespace llvm; 00067 00068 namespace { 00069 Statistic<> 00070 NumIters("anders-aa", "Number of iterations to reach convergence"); 00071 Statistic<> 00072 NumConstraints("anders-aa", "Number of constraints"); 00073 Statistic<> 00074 NumNodes("anders-aa", "Number of nodes"); 00075 Statistic<> 00076 NumEscapingFunctions("anders-aa", "Number of internal functions that escape"); 00077 Statistic<> 00078 NumIndirectCallees("anders-aa", "Number of indirect callees found"); 00079 00080 class Andersens : public ModulePass, public AliasAnalysis, 00081 private InstVisitor<Andersens> { 00082 /// Node class - This class is used to represent a memory object in the 00083 /// program, and is the primitive used to build the points-to graph. 00084 class Node { 00085 std::vector<Node*> Pointees; 00086 Value *Val; 00087 public: 00088 Node() : Val(0) {} 00089 Node *setValue(Value *V) { 00090 assert(Val == 0 && "Value already set for this node!"); 00091 Val = V; 00092 return this; 00093 } 00094 00095 /// getValue - Return the LLVM value corresponding to this node. 00096 /// 00097 Value *getValue() const { return Val; } 00098 00099 typedef std::vector<Node*>::const_iterator iterator; 00100 iterator begin() const { return Pointees.begin(); } 00101 iterator end() const { return Pointees.end(); } 00102 00103 /// addPointerTo - Add a pointer to the list of pointees of this node, 00104 /// returning true if this caused a new pointer to be added, or false if 00105 /// we already knew about the points-to relation. 00106 bool addPointerTo(Node *N) { 00107 std::vector<Node*>::iterator I = std::lower_bound(Pointees.begin(), 00108 Pointees.end(), 00109 N); 00110 if (I != Pointees.end() && *I == N) 00111 return false; 00112 Pointees.insert(I, N); 00113 return true; 00114 } 00115 00116 /// intersects - Return true if the points-to set of this node intersects 00117 /// with the points-to set of the specified node. 00118 bool intersects(Node *N) const; 00119 00120 /// intersectsIgnoring - Return true if the points-to set of this node 00121 /// intersects with the points-to set of the specified node on any nodes 00122 /// except for the specified node to ignore. 00123 bool intersectsIgnoring(Node *N, Node *Ignoring) const; 00124 00125 // Constraint application methods. 00126 bool copyFrom(Node *N); 00127 bool loadFrom(Node *N); 00128 bool storeThrough(Node *N); 00129 }; 00130 00131 /// GraphNodes - This vector is populated as part of the object 00132 /// identification stage of the analysis, which populates this vector with a 00133 /// node for each memory object and fills in the ValueNodes map. 00134 std::vector<Node> GraphNodes; 00135 00136 /// ValueNodes - This map indicates the Node that a particular Value* is 00137 /// represented by. This contains entries for all pointers. 00138 std::map<Value*, unsigned> ValueNodes; 00139 00140 /// ObjectNodes - This map contains entries for each memory object in the 00141 /// program: globals, alloca's and mallocs. 00142 std::map<Value*, unsigned> ObjectNodes; 00143 00144 /// ReturnNodes - This map contains an entry for each function in the 00145 /// program that returns a value. 00146 std::map<Function*, unsigned> ReturnNodes; 00147 00148 /// VarargNodes - This map contains the entry used to represent all pointers 00149 /// passed through the varargs portion of a function call for a particular 00150 /// function. An entry is not present in this map for functions that do not 00151 /// take variable arguments. 00152 std::map<Function*, unsigned> VarargNodes; 00153 00154 /// Constraint - Objects of this structure are used to represent the various 00155 /// constraints identified by the algorithm. The constraints are 'copy', 00156 /// for statements like "A = B", 'load' for statements like "A = *B", and 00157 /// 'store' for statements like "*A = B". 00158 struct Constraint { 00159 enum ConstraintType { Copy, Load, Store } Type; 00160 Node *Dest, *Src; 00161 00162 Constraint(ConstraintType Ty, Node *D, Node *S) 00163 : Type(Ty), Dest(D), Src(S) {} 00164 }; 00165 00166 /// Constraints - This vector contains a list of all of the constraints 00167 /// identified by the program. 00168 std::vector<Constraint> Constraints; 00169 00170 /// EscapingInternalFunctions - This set contains all of the internal 00171 /// functions that are found to escape from the program. If the address of 00172 /// an internal function is passed to an external function or otherwise 00173 /// escapes from the analyzed portion of the program, we must assume that 00174 /// any pointer arguments can alias the universal node. This set keeps 00175 /// track of those functions we are assuming to escape so far. 00176 std::set<Function*> EscapingInternalFunctions; 00177 00178 /// IndirectCalls - This contains a list of all of the indirect call sites 00179 /// in the program. Since the call graph is iteratively discovered, we may 00180 /// need to add constraints to our graph as we find new targets of function 00181 /// pointers. 00182 std::vector<CallSite> IndirectCalls; 00183 00184 /// IndirectCallees - For each call site in the indirect calls list, keep 00185 /// track of the callees that we have discovered so far. As the analysis 00186 /// proceeds, more callees are discovered, until the call graph finally 00187 /// stabilizes. 00188 std::map<CallSite, std::vector<Function*> > IndirectCallees; 00189 00190 /// This enum defines the GraphNodes indices that correspond to important 00191 /// fixed sets. 00192 enum { 00193 UniversalSet = 0, 00194 NullPtr = 1, 00195 NullObject = 2 00196 }; 00197 00198 public: 00199 bool runOnModule(Module &M) { 00200 InitializeAliasAnalysis(this); 00201 IdentifyObjects(M); 00202 CollectConstraints(M); 00203 DEBUG(PrintConstraints()); 00204 SolveConstraints(); 00205 DEBUG(PrintPointsToGraph()); 00206 00207 // Free the constraints list, as we don't need it to respond to alias 00208 // requests. 00209 ObjectNodes.clear(); 00210 ReturnNodes.clear(); 00211 VarargNodes.clear(); 00212 EscapingInternalFunctions.clear(); 00213 std::vector<Constraint>().swap(Constraints); 00214 return false; 00215 } 00216 00217 void releaseMemory() { 00218 // FIXME: Until we have transitively required passes working correctly, 00219 // this cannot be enabled! Otherwise, using -count-aa with the pass 00220 // causes memory to be freed too early. :( 00221 #if 0 00222 // The memory objects and ValueNodes data structures at the only ones that 00223 // are still live after construction. 00224 std::vector<Node>().swap(GraphNodes); 00225 ValueNodes.clear(); 00226 #endif 00227 } 00228 00229 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00230 AliasAnalysis::getAnalysisUsage(AU); 00231 AU.setPreservesAll(); // Does not transform code 00232 } 00233 00234 //------------------------------------------------ 00235 // Implement the AliasAnalysis API 00236 // 00237 AliasResult alias(const Value *V1, unsigned V1Size, 00238 const Value *V2, unsigned V2Size); 00239 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00240 void getMustAliases(Value *P, std::vector<Value*> &RetVals); 00241 bool pointsToConstantMemory(const Value *P); 00242 00243 virtual void deleteValue(Value *V) { 00244 ValueNodes.erase(V); 00245 getAnalysis<AliasAnalysis>().deleteValue(V); 00246 } 00247 00248 virtual void copyValue(Value *From, Value *To) { 00249 ValueNodes[To] = ValueNodes[From]; 00250 getAnalysis<AliasAnalysis>().copyValue(From, To); 00251 } 00252 00253 private: 00254 /// getNode - Return the node corresponding to the specified pointer scalar. 00255 /// 00256 Node *getNode(Value *V) { 00257 if (Constant *C = dyn_cast<Constant>(V)) 00258 if (!isa<GlobalValue>(C)) 00259 return getNodeForConstantPointer(C); 00260 00261 std::map<Value*, unsigned>::iterator I = ValueNodes.find(V); 00262 if (I == ValueNodes.end()) { 00263 #ifndef NDEBUG 00264 V->dump(); 00265 #endif 00266 assert(0 && "Value does not have a node in the points-to graph!"); 00267 } 00268 return &GraphNodes[I->second]; 00269 } 00270 00271 /// getObject - Return the node corresponding to the memory object for the 00272 /// specified global or allocation instruction. 00273 Node *getObject(Value *V) { 00274 std::map<Value*, unsigned>::iterator I = ObjectNodes.find(V); 00275 assert(I != ObjectNodes.end() && 00276 "Value does not have an object in the points-to graph!"); 00277 return &GraphNodes[I->second]; 00278 } 00279 00280 /// getReturnNode - Return the node representing the return value for the 00281 /// specified function. 00282 Node *getReturnNode(Function *F) { 00283 std::map<Function*, unsigned>::iterator I = ReturnNodes.find(F); 00284 assert(I != ReturnNodes.end() && "Function does not return a value!"); 00285 return &GraphNodes[I->second]; 00286 } 00287 00288 /// getVarargNode - Return the node representing the variable arguments 00289 /// formal for the specified function. 00290 Node *getVarargNode(Function *F) { 00291 std::map<Function*, unsigned>::iterator I = VarargNodes.find(F); 00292 assert(I != VarargNodes.end() && "Function does not take var args!"); 00293 return &GraphNodes[I->second]; 00294 } 00295 00296 /// getNodeValue - Get the node for the specified LLVM value and set the 00297 /// value for it to be the specified value. 00298 Node *getNodeValue(Value &V) { 00299 return getNode(&V)->setValue(&V); 00300 } 00301 00302 void IdentifyObjects(Module &M); 00303 void CollectConstraints(Module &M); 00304 void SolveConstraints(); 00305 00306 Node *getNodeForConstantPointer(Constant *C); 00307 Node *getNodeForConstantPointerTarget(Constant *C); 00308 void AddGlobalInitializerConstraints(Node *N, Constant *C); 00309 00310 void AddConstraintsForNonInternalLinkage(Function *F); 00311 void AddConstraintsForCall(CallSite CS, Function *F); 00312 bool AddConstraintsForExternalCall(CallSite CS, Function *F); 00313 00314 00315 void PrintNode(Node *N); 00316 void PrintConstraints(); 00317 void PrintPointsToGraph(); 00318 00319 //===------------------------------------------------------------------===// 00320 // Instruction visitation methods for adding constraints 00321 // 00322 friend class InstVisitor<Andersens>; 00323 void visitReturnInst(ReturnInst &RI); 00324 void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); } 00325 void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); } 00326 void visitCallSite(CallSite CS); 00327 void visitAllocationInst(AllocationInst &AI); 00328 void visitLoadInst(LoadInst &LI); 00329 void visitStoreInst(StoreInst &SI); 00330 void visitGetElementPtrInst(GetElementPtrInst &GEP); 00331 void visitPHINode(PHINode &PN); 00332 void visitCastInst(CastInst &CI); 00333 void visitSetCondInst(SetCondInst &SCI) {} // NOOP! 00334 void visitSelectInst(SelectInst &SI); 00335 void visitVAArg(VAArgInst &I); 00336 void visitInstruction(Instruction &I); 00337 }; 00338 00339 RegisterOpt<Andersens> X("anders-aa", 00340 "Andersen's Interprocedural Alias Analysis"); 00341 RegisterAnalysisGroup<AliasAnalysis, Andersens> Y; 00342 } 00343 00344 ModulePass *llvm::createAndersensPass() { return new Andersens(); } 00345 00346 //===----------------------------------------------------------------------===// 00347 // AliasAnalysis Interface Implementation 00348 //===----------------------------------------------------------------------===// 00349 00350 AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size, 00351 const Value *V2, unsigned V2Size) { 00352 Node *N1 = getNode(const_cast<Value*>(V1)); 00353 Node *N2 = getNode(const_cast<Value*>(V2)); 00354 00355 // Check to see if the two pointers are known to not alias. They don't alias 00356 // if their points-to sets do not intersect. 00357 if (!N1->intersectsIgnoring(N2, &GraphNodes[NullObject])) 00358 return NoAlias; 00359 00360 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00361 } 00362 00363 AliasAnalysis::ModRefResult 00364 Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00365 // The only thing useful that we can contribute for mod/ref information is 00366 // when calling external function calls: if we know that memory never escapes 00367 // from the program, it cannot be modified by an external call. 00368 // 00369 // NOTE: This is not really safe, at least not when the entire program is not 00370 // available. The deal is that the external function could call back into the 00371 // program and modify stuff. We ignore this technical niggle for now. This 00372 // is, after all, a "research quality" implementation of Andersen's analysis. 00373 if (Function *F = CS.getCalledFunction()) 00374 if (F->isExternal()) { 00375 Node *N1 = getNode(P); 00376 bool PointsToUniversalSet = false; 00377 00378 if (N1->begin() == N1->end()) 00379 return NoModRef; // P doesn't point to anything. 00380 00381 // Get the first pointee. 00382 Node *FirstPointee = *N1->begin(); 00383 if (FirstPointee != &GraphNodes[UniversalSet]) 00384 return NoModRef; // P doesn't point to the universal set. 00385 } 00386 00387 return AliasAnalysis::getModRefInfo(CS, P, Size); 00388 } 00389 00390 /// getMustAlias - We can provide must alias information if we know that a 00391 /// pointer can only point to a specific function or the null pointer. 00392 /// Unfortunately we cannot determine must-alias information for global 00393 /// variables or any other memory memory objects because we do not track whether 00394 /// a pointer points to the beginning of an object or a field of it. 00395 void Andersens::getMustAliases(Value *P, std::vector<Value*> &RetVals) { 00396 Node *N = getNode(P); 00397 Node::iterator I = N->begin(); 00398 if (I != N->end()) { 00399 // If there is exactly one element in the points-to set for the object... 00400 ++I; 00401 if (I == N->end()) { 00402 Node *Pointee = *N->begin(); 00403 00404 // If a function is the only object in the points-to set, then it must be 00405 // the destination. Note that we can't handle global variables here, 00406 // because we don't know if the pointer is actually pointing to a field of 00407 // the global or to the beginning of it. 00408 if (Value *V = Pointee->getValue()) { 00409 if (Function *F = dyn_cast<Function>(V)) 00410 RetVals.push_back(F); 00411 } else { 00412 // If the object in the points-to set is the null object, then the null 00413 // pointer is a must alias. 00414 if (Pointee == &GraphNodes[NullObject]) 00415 RetVals.push_back(Constant::getNullValue(P->getType())); 00416 } 00417 } 00418 } 00419 00420 AliasAnalysis::getMustAliases(P, RetVals); 00421 } 00422 00423 /// pointsToConstantMemory - If we can determine that this pointer only points 00424 /// to constant memory, return true. In practice, this means that if the 00425 /// pointer can only point to constant globals, functions, or the null pointer, 00426 /// return true. 00427 /// 00428 bool Andersens::pointsToConstantMemory(const Value *P) { 00429 Node *N = getNode((Value*)P); 00430 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { 00431 if (Value *V = (*I)->getValue()) { 00432 if (!isa<GlobalValue>(V) || (isa<GlobalVariable>(V) && 00433 !cast<GlobalVariable>(V)->isConstant())) 00434 return AliasAnalysis::pointsToConstantMemory(P); 00435 } else { 00436 if (*I != &GraphNodes[NullObject]) 00437 return AliasAnalysis::pointsToConstantMemory(P); 00438 } 00439 } 00440 00441 return true; 00442 } 00443 00444 //===----------------------------------------------------------------------===// 00445 // Object Identification Phase 00446 //===----------------------------------------------------------------------===// 00447 00448 /// IdentifyObjects - This stage scans the program, adding an entry to the 00449 /// GraphNodes list for each memory object in the program (global stack or 00450 /// heap), and populates the ValueNodes and ObjectNodes maps for these objects. 00451 /// 00452 void Andersens::IdentifyObjects(Module &M) { 00453 unsigned NumObjects = 0; 00454 00455 // Object #0 is always the universal set: the object that we don't know 00456 // anything about. 00457 assert(NumObjects == UniversalSet && "Something changed!"); 00458 ++NumObjects; 00459 00460 // Object #1 always represents the null pointer. 00461 assert(NumObjects == NullPtr && "Something changed!"); 00462 ++NumObjects; 00463 00464 // Object #2 always represents the null object (the object pointed to by null) 00465 assert(NumObjects == NullObject && "Something changed!"); 00466 ++NumObjects; 00467 00468 // Add all the globals first. 00469 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 00470 I != E; ++I) { 00471 ObjectNodes[I] = NumObjects++; 00472 ValueNodes[I] = NumObjects++; 00473 } 00474 00475 // Add nodes for all of the functions and the instructions inside of them. 00476 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 00477 // The function itself is a memory object. 00478 ValueNodes[F] = NumObjects++; 00479 ObjectNodes[F] = NumObjects++; 00480 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00481 ReturnNodes[F] = NumObjects++; 00482 if (F->getFunctionType()->isVarArg()) 00483 VarargNodes[F] = NumObjects++; 00484 00485 // Add nodes for all of the incoming pointer arguments. 00486 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00487 I != E; ++I) 00488 if (isa<PointerType>(I->getType())) 00489 ValueNodes[I] = NumObjects++; 00490 00491 // Scan the function body, creating a memory object for each heap/stack 00492 // allocation in the body of the function and a node to represent all 00493 // pointer values defined by instructions and used as operands. 00494 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 00495 // If this is an heap or stack allocation, create a node for the memory 00496 // object. 00497 if (isa<PointerType>(II->getType())) { 00498 ValueNodes[&*II] = NumObjects++; 00499 if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II)) 00500 ObjectNodes[AI] = NumObjects++; 00501 } 00502 } 00503 } 00504 00505 // Now that we know how many objects to create, make them all now! 00506 GraphNodes.resize(NumObjects); 00507 NumNodes += NumObjects; 00508 } 00509 00510 //===----------------------------------------------------------------------===// 00511 // Constraint Identification Phase 00512 //===----------------------------------------------------------------------===// 00513 00514 /// getNodeForConstantPointer - Return the node corresponding to the constant 00515 /// pointer itself. 00516 Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) { 00517 assert(isa<PointerType>(C->getType()) && "Not a constant pointer!"); 00518 00519 if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C)) 00520 return &GraphNodes[NullPtr]; 00521 else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 00522 return getNode(GV); 00523 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00524 switch (CE->getOpcode()) { 00525 case Instruction::GetElementPtr: 00526 return getNodeForConstantPointer(CE->getOperand(0)); 00527 case Instruction::Cast: 00528 if (isa<PointerType>(CE->getOperand(0)->getType())) 00529 return getNodeForConstantPointer(CE->getOperand(0)); 00530 else 00531 return &GraphNodes[UniversalSet]; 00532 default: 00533 std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; 00534 assert(0); 00535 } 00536 } else { 00537 assert(0 && "Unknown constant pointer!"); 00538 } 00539 return 0; 00540 } 00541 00542 /// getNodeForConstantPointerTarget - Return the node POINTED TO by the 00543 /// specified constant pointer. 00544 Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) { 00545 assert(isa<PointerType>(C->getType()) && "Not a constant pointer!"); 00546 00547 if (isa<ConstantPointerNull>(C)) 00548 return &GraphNodes[NullObject]; 00549 else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 00550 return getObject(GV); 00551 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00552 switch (CE->getOpcode()) { 00553 case Instruction::GetElementPtr: 00554 return getNodeForConstantPointerTarget(CE->getOperand(0)); 00555 case Instruction::Cast: 00556 if (isa<PointerType>(CE->getOperand(0)->getType())) 00557 return getNodeForConstantPointerTarget(CE->getOperand(0)); 00558 else 00559 return &GraphNodes[UniversalSet]; 00560 default: 00561 std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; 00562 assert(0); 00563 } 00564 } else { 00565 assert(0 && "Unknown constant pointer!"); 00566 } 00567 return 0; 00568 } 00569 00570 /// AddGlobalInitializerConstraints - Add inclusion constraints for the memory 00571 /// object N, which contains values indicated by C. 00572 void Andersens::AddGlobalInitializerConstraints(Node *N, Constant *C) { 00573 if (C->getType()->isFirstClassType()) { 00574 if (isa<PointerType>(C->getType())) 00575 N->copyFrom(getNodeForConstantPointer(C)); 00576 00577 } else if (C->isNullValue()) { 00578 N->addPointerTo(&GraphNodes[NullObject]); 00579 return; 00580 } else if (!isa<UndefValue>(C)) { 00581 // If this is an array or struct, include constraints for each element. 00582 assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C)); 00583 for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) 00584 AddGlobalInitializerConstraints(N, cast<Constant>(C->getOperand(i))); 00585 } 00586 } 00587 00588 /// AddConstraintsForNonInternalLinkage - If this function does not have 00589 /// internal linkage, realize that we can't trust anything passed into or 00590 /// returned by this function. 00591 void Andersens::AddConstraintsForNonInternalLinkage(Function *F) { 00592 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) 00593 if (isa<PointerType>(I->getType())) 00594 // If this is an argument of an externally accessible function, the 00595 // incoming pointer might point to anything. 00596 Constraints.push_back(Constraint(Constraint::Copy, getNode(I), 00597 &GraphNodes[UniversalSet])); 00598 } 00599 00600 /// AddConstraintsForCall - If this is a call to a "known" function, add the 00601 /// constraints and return true. If this is a call to an unknown function, 00602 /// return false. 00603 bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) { 00604 assert(F->isExternal() && "Not an external function!"); 00605 00606 // These functions don't induce any points-to constraints. 00607 if (F->getName() == "atoi" || F->getName() == "atof" || 00608 F->getName() == "atol" || F->getName() == "atoll" || 00609 F->getName() == "remove" || F->getName() == "unlink" || 00610 F->getName() == "rename" || F->getName() == "memcmp" || 00611 F->getName() == "llvm.memset.i32" || 00612 F->getName() == "llvm.memset.i64" || 00613 F->getName() == "strcmp" || F->getName() == "strncmp" || 00614 F->getName() == "execl" || F->getName() == "execlp" || 00615 F->getName() == "execle" || F->getName() == "execv" || 00616 F->getName() == "execvp" || F->getName() == "chmod" || 00617 F->getName() == "puts" || F->getName() == "write" || 00618 F->getName() == "open" || F->getName() == "create" || 00619 F->getName() == "truncate" || F->getName() == "chdir" || 00620 F->getName() == "mkdir" || F->getName() == "rmdir" || 00621 F->getName() == "read" || F->getName() == "pipe" || 00622 F->getName() == "wait" || F->getName() == "time" || 00623 F->getName() == "stat" || F->getName() == "fstat" || 00624 F->getName() == "lstat" || F->getName() == "strtod" || 00625 F->getName() == "strtof" || F->getName() == "strtold" || 00626 F->getName() == "fopen" || F->getName() == "fdopen" || 00627 F->getName() == "freopen" || 00628 F->getName() == "fflush" || F->getName() == "feof" || 00629 F->getName() == "fileno" || F->getName() == "clearerr" || 00630 F->getName() == "rewind" || F->getName() == "ftell" || 00631 F->getName() == "ferror" || F->getName() == "fgetc" || 00632 F->getName() == "fgetc" || F->getName() == "_IO_getc" || 00633 F->getName() == "fwrite" || F->getName() == "fread" || 00634 F->getName() == "fgets" || F->getName() == "ungetc" || 00635 F->getName() == "fputc" || 00636 F->getName() == "fputs" || F->getName() == "putc" || 00637 F->getName() == "ftell" || F->getName() == "rewind" || 00638 F->getName() == "_IO_putc" || F->getName() == "fseek" || 00639 F->getName() == "fgetpos" || F->getName() == "fsetpos" || 00640 F->getName() == "printf" || F->getName() == "fprintf" || 00641 F->getName() == "sprintf" || F->getName() == "vprintf" || 00642 F->getName() == "vfprintf" || F->getName() == "vsprintf" || 00643 F->getName() == "scanf" || F->getName() == "fscanf" || 00644 F->getName() == "sscanf" || F->getName() == "__assert_fail" || 00645 F->getName() == "modf") 00646 return true; 00647 00648 00649 // These functions do induce points-to edges. 00650 if (F->getName() == "llvm.memcpy.i32" || F->getName() == "llvm.memcpy.i64" || 00651 F->getName() == "llvm.memmove.i32" ||F->getName() == "llvm.memmove.i64" || 00652 F->getName() == "memmove") { 00653 // Note: this is a poor approximation, this says Dest = Src, instead of 00654 // *Dest = *Src. 00655 Constraints.push_back(Constraint(Constraint::Copy, 00656 getNode(CS.getArgument(0)), 00657 getNode(CS.getArgument(1)))); 00658 return true; 00659 } 00660 00661 // Result = Arg0 00662 if (F->getName() == "realloc" || F->getName() == "strchr" || 00663 F->getName() == "strrchr" || F->getName() == "strstr" || 00664 F->getName() == "strtok") { 00665 Constraints.push_back(Constraint(Constraint::Copy, 00666 getNode(CS.getInstruction()), 00667 getNode(CS.getArgument(0)))); 00668 return true; 00669 } 00670 00671 return false; 00672 } 00673 00674 00675 00676 /// CollectConstraints - This stage scans the program, adding a constraint to 00677 /// the Constraints list for each instruction in the program that induces a 00678 /// constraint, and setting up the initial points-to graph. 00679 /// 00680 void Andersens::CollectConstraints(Module &M) { 00681 // First, the universal set points to itself. 00682 GraphNodes[UniversalSet].addPointerTo(&GraphNodes[UniversalSet]); 00683 //Constraints.push_back(Constraint(Constraint::Load, &GraphNodes[UniversalSet], 00684 // &GraphNodes[UniversalSet])); 00685 Constraints.push_back(Constraint(Constraint::Store, &GraphNodes[UniversalSet], 00686 &GraphNodes[UniversalSet])); 00687 00688 // Next, the null pointer points to the null object. 00689 GraphNodes[NullPtr].addPointerTo(&GraphNodes[NullObject]); 00690 00691 // Next, add any constraints on global variables and their initializers. 00692 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 00693 I != E; ++I) { 00694 // Associate the address of the global object as pointing to the memory for 00695 // the global: &G = <G memory> 00696 Node *Object = getObject(I); 00697 Object->setValue(I); 00698 getNodeValue(*I)->addPointerTo(Object); 00699 00700 if (I->hasInitializer()) { 00701 AddGlobalInitializerConstraints(Object, I->getInitializer()); 00702 } else { 00703 // If it doesn't have an initializer (i.e. it's defined in another 00704 // translation unit), it points to the universal set. 00705 Constraints.push_back(Constraint(Constraint::Copy, Object, 00706 &GraphNodes[UniversalSet])); 00707 } 00708 } 00709 00710 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 00711 // Make the function address point to the function object. 00712 getNodeValue(*F)->addPointerTo(getObject(F)->setValue(F)); 00713 00714 // Set up the return value node. 00715 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00716 getReturnNode(F)->setValue(F); 00717 if (F->getFunctionType()->isVarArg()) 00718 getVarargNode(F)->setValue(F); 00719 00720 // Set up incoming argument nodes. 00721 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00722 I != E; ++I) 00723 if (isa<PointerType>(I->getType())) 00724 getNodeValue(*I); 00725 00726 if (!F->hasInternalLinkage()) 00727 AddConstraintsForNonInternalLinkage(F); 00728 00729 if (!F->isExternal()) { 00730 // Scan the function body, creating a memory object for each heap/stack 00731 // allocation in the body of the function and a node to represent all 00732 // pointer values defined by instructions and used as operands. 00733 visit(F); 00734 } else { 00735 // External functions that return pointers return the universal set. 00736 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00737 Constraints.push_back(Constraint(Constraint::Copy, 00738 getReturnNode(F), 00739 &GraphNodes[UniversalSet])); 00740 00741 // Any pointers that are passed into the function have the universal set 00742 // stored into them. 00743 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00744 I != E; ++I) 00745 if (isa<PointerType>(I->getType())) { 00746 // Pointers passed into external functions could have anything stored 00747 // through them. 00748 Constraints.push_back(Constraint(Constraint::Store, getNode(I), 00749 &GraphNodes[UniversalSet])); 00750 // Memory objects passed into external function calls can have the 00751 // universal set point to them. 00752 Constraints.push_back(Constraint(Constraint::Copy, 00753 &GraphNodes[UniversalSet], 00754 getNode(I))); 00755 } 00756 00757 // If this is an external varargs function, it can also store pointers 00758 // into any pointers passed through the varargs section. 00759 if (F->getFunctionType()->isVarArg()) 00760 Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F), 00761 &GraphNodes[UniversalSet])); 00762 } 00763 } 00764 NumConstraints += Constraints.size(); 00765 } 00766 00767 00768 void Andersens::visitInstruction(Instruction &I) { 00769 #ifdef NDEBUG 00770 return; // This function is just a big assert. 00771 #endif 00772 if (isa<BinaryOperator>(I)) 00773 return; 00774 // Most instructions don't have any effect on pointer values. 00775 switch (I.getOpcode()) { 00776 case Instruction::Br: 00777 case Instruction::Switch: 00778 case Instruction::Unwind: 00779 case Instruction::Unreachable: 00780 case Instruction::Free: 00781 case Instruction::Shl: 00782 case Instruction::Shr: 00783 return; 00784 default: 00785 // Is this something we aren't handling yet? 00786 std::cerr << "Unknown instruction: " << I; 00787 abort(); 00788 } 00789 } 00790 00791 void Andersens::visitAllocationInst(AllocationInst &AI) { 00792 getNodeValue(AI)->addPointerTo(getObject(&AI)->setValue(&AI)); 00793 } 00794 00795 void Andersens::visitReturnInst(ReturnInst &RI) { 00796 if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) 00797 // return V --> <Copy/retval{F}/v> 00798 Constraints.push_back(Constraint(Constraint::Copy, 00799 getReturnNode(RI.getParent()->getParent()), 00800 getNode(RI.getOperand(0)))); 00801 } 00802 00803 void Andersens::visitLoadInst(LoadInst &LI) { 00804 if (isa<PointerType>(LI.getType())) 00805 // P1 = load P2 --> <Load/P1/P2> 00806 Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI), 00807 getNode(LI.getOperand(0)))); 00808 } 00809 00810 void Andersens::visitStoreInst(StoreInst &SI) { 00811 if (isa<PointerType>(SI.getOperand(0)->getType())) 00812 // store P1, P2 --> <Store/P2/P1> 00813 Constraints.push_back(Constraint(Constraint::Store, 00814 getNode(SI.getOperand(1)), 00815 getNode(SI.getOperand(0)))); 00816 } 00817 00818 void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) { 00819 // P1 = getelementptr P2, ... --> <Copy/P1/P2> 00820 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP), 00821 getNode(GEP.getOperand(0)))); 00822 } 00823 00824 void Andersens::visitPHINode(PHINode &PN) { 00825 if (isa<PointerType>(PN.getType())) { 00826 Node *PNN = getNodeValue(PN); 00827 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 00828 // P1 = phi P2, P3 --> <Copy/P1/P2>, <Copy/P1/P3>, ... 00829 Constraints.push_back(Constraint(Constraint::Copy, PNN, 00830 getNode(PN.getIncomingValue(i)))); 00831 } 00832 } 00833 00834 void Andersens::visitCastInst(CastInst &CI) { 00835 Value *Op = CI.getOperand(0); 00836 if (isa<PointerType>(CI.getType())) { 00837 if (isa<PointerType>(Op->getType())) { 00838 // P1 = cast P2 --> <Copy/P1/P2> 00839 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), 00840 getNode(CI.getOperand(0)))); 00841 } else { 00842 // P1 = cast int --> <Copy/P1/Univ> 00843 #if 0 00844 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), 00845 &GraphNodes[UniversalSet])); 00846 #else 00847 getNodeValue(CI); 00848 #endif 00849 } 00850 } else if (isa<PointerType>(Op->getType())) { 00851 // int = cast P1 --> <Copy/Univ/P1> 00852 #if 0 00853 Constraints.push_back(Constraint(Constraint::Copy, 00854 &GraphNodes[UniversalSet], 00855 getNode(CI.getOperand(0)))); 00856 #else 00857 getNode(CI.getOperand(0)); 00858 #endif 00859 } 00860 } 00861 00862 void Andersens::visitSelectInst(SelectInst &SI) { 00863 if (isa<PointerType>(SI.getType())) { 00864 Node *SIN = getNodeValue(SI); 00865 // P1 = select C, P2, P3 ---> <Copy/P1/P2>, <Copy/P1/P3> 00866 Constraints.push_back(Constraint(Constraint::Copy, SIN, 00867 getNode(SI.getOperand(1)))); 00868 Constraints.push_back(Constraint(Constraint::Copy, SIN, 00869 getNode(SI.getOperand(2)))); 00870 } 00871 } 00872 00873 void Andersens::visitVAArg(VAArgInst &I) { 00874 assert(0 && "vaarg not handled yet!"); 00875 } 00876 00877 /// AddConstraintsForCall - Add constraints for a call with actual arguments 00878 /// specified by CS to the function specified by F. Note that the types of 00879 /// arguments might not match up in the case where this is an indirect call and 00880 /// the function pointer has been casted. If this is the case, do something 00881 /// reasonable. 00882 void Andersens::AddConstraintsForCall(CallSite CS, Function *F) { 00883 // If this is a call to an external function, handle it directly to get some 00884 // taste of context sensitivity. 00885 if (F->isExternal() && AddConstraintsForExternalCall(CS, F)) 00886 return; 00887 00888 if (isa<PointerType>(CS.getType())) { 00889 Node *CSN = getNode(CS.getInstruction()); 00890 if (isa<PointerType>(F->getFunctionType()->getReturnType())) { 00891 Constraints.push_back(Constraint(Constraint::Copy, CSN, 00892 getReturnNode(F))); 00893 } else { 00894 // If the function returns a non-pointer value, handle this just like we 00895 // treat a nonpointer cast to pointer. 00896 Constraints.push_back(Constraint(Constraint::Copy, CSN, 00897 &GraphNodes[UniversalSet])); 00898 } 00899 } else if (isa<PointerType>(F->getFunctionType()->getReturnType())) { 00900 Constraints.push_back(Constraint(Constraint::Copy, 00901 &GraphNodes[UniversalSet], 00902 getReturnNode(F))); 00903 } 00904 00905 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 00906 CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end(); 00907 for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) 00908 if (isa<PointerType>(AI->getType())) { 00909 if (isa<PointerType>((*ArgI)->getType())) { 00910 // Copy the actual argument into the formal argument. 00911 Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), 00912 getNode(*ArgI))); 00913 } else { 00914 Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), 00915 &GraphNodes[UniversalSet])); 00916 } 00917 } else if (isa<PointerType>((*ArgI)->getType())) { 00918 Constraints.push_back(Constraint(Constraint::Copy, 00919 &GraphNodes[UniversalSet], 00920 getNode(*ArgI))); 00921 } 00922 00923 // Copy all pointers passed through the varargs section to the varargs node. 00924 if (F->getFunctionType()->isVarArg()) 00925 for (; ArgI != ArgE; ++ArgI) 00926 if (isa<PointerType>((*ArgI)->getType())) 00927 Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F), 00928 getNode(*ArgI))); 00929 // If more arguments are passed in than we track, just drop them on the floor. 00930 } 00931 00932 void Andersens::visitCallSite(CallSite CS) { 00933 if (isa<PointerType>(CS.getType())) 00934 getNodeValue(*CS.getInstruction()); 00935 00936 if (Function *F = CS.getCalledFunction()) { 00937 AddConstraintsForCall(CS, F); 00938 } else { 00939 // We don't handle indirect call sites yet. Keep track of them for when we 00940 // discover the call graph incrementally. 00941 IndirectCalls.push_back(CS); 00942 } 00943 } 00944 00945 //===----------------------------------------------------------------------===// 00946 // Constraint Solving Phase 00947 //===----------------------------------------------------------------------===// 00948 00949 /// intersects - Return true if the points-to set of this node intersects 00950 /// with the points-to set of the specified node. 00951 bool Andersens::Node::intersects(Node *N) const { 00952 iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); 00953 while (I1 != E1 && I2 != E2) { 00954 if (*I1 == *I2) return true; 00955 if (*I1 < *I2) 00956 ++I1; 00957 else 00958 ++I2; 00959 } 00960 return false; 00961 } 00962 00963 /// intersectsIgnoring - Return true if the points-to set of this node 00964 /// intersects with the points-to set of the specified node on any nodes 00965 /// except for the specified node to ignore. 00966 bool Andersens::Node::intersectsIgnoring(Node *N, Node *Ignoring) const { 00967 iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); 00968 while (I1 != E1 && I2 != E2) { 00969 if (*I1 == *I2) { 00970 if (*I1 != Ignoring) return true; 00971 ++I1; ++I2; 00972 } else if (*I1 < *I2) 00973 ++I1; 00974 else 00975 ++I2; 00976 } 00977 return false; 00978 } 00979 00980 // Copy constraint: all edges out of the source node get copied to the 00981 // destination node. This returns true if a change is made. 00982 bool Andersens::Node::copyFrom(Node *N) { 00983 // Use a mostly linear-time merge since both of the lists are sorted. 00984 bool Changed = false; 00985 iterator I = N->begin(), E = N->end(); 00986 unsigned i = 0; 00987 while (I != E && i != Pointees.size()) { 00988 if (Pointees[i] < *I) { 00989 ++i; 00990 } else if (Pointees[i] == *I) { 00991 ++i; ++I; 00992 } else { 00993 // We found a new element to copy over. 00994 Changed = true; 00995 Pointees.insert(Pointees.begin()+i, *I); 00996 ++i; ++I; 00997 } 00998 } 00999 01000 if (I != E) { 01001 Pointees.insert(Pointees.end(), I, E); 01002 Changed = true; 01003 } 01004 01005 return Changed; 01006 } 01007 01008 bool Andersens::Node::loadFrom(Node *N) { 01009 bool Changed = false; 01010 for (iterator I = N->begin(), E = N->end(); I != E; ++I) 01011 Changed |= copyFrom(*I); 01012 return Changed; 01013 } 01014 01015 bool Andersens::Node::storeThrough(Node *N) { 01016 bool Changed = false; 01017 for (iterator I = begin(), E = end(); I != E; ++I) 01018 Changed |= (*I)->copyFrom(N); 01019 return Changed; 01020 } 01021 01022 01023 /// SolveConstraints - This stage iteratively processes the constraints list 01024 /// propagating constraints (adding edges to the Nodes in the points-to graph) 01025 /// until a fixed point is reached. 01026 /// 01027 void Andersens::SolveConstraints() { 01028 bool Changed = true; 01029 unsigned Iteration = 0; 01030 while (Changed) { 01031 Changed = false; 01032 ++NumIters; 01033 DEBUG(std::cerr << "Starting iteration #" << Iteration++ << "!\n"); 01034 01035 // Loop over all of the constraints, applying them in turn. 01036 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01037 Constraint &C = Constraints[i]; 01038 switch (C.Type) { 01039 case Constraint::Copy: 01040 Changed |= C.Dest->copyFrom(C.Src); 01041 break; 01042 case Constraint::Load: 01043 Changed |= C.Dest->loadFrom(C.Src); 01044 break; 01045 case Constraint::Store: 01046 Changed |= C.Dest->storeThrough(C.Src); 01047 break; 01048 default: 01049 assert(0 && "Unknown constraint!"); 01050 } 01051 } 01052 01053 if (Changed) { 01054 // Check to see if any internal function's addresses have been passed to 01055 // external functions. If so, we have to assume that their incoming 01056 // arguments could be anything. If there are any internal functions in 01057 // the universal node that we don't know about, we must iterate. 01058 for (Node::iterator I = GraphNodes[UniversalSet].begin(), 01059 E = GraphNodes[UniversalSet].end(); I != E; ++I) 01060 if (Function *F = dyn_cast_or_null<Function>((*I)->getValue())) 01061 if (F->hasInternalLinkage() && 01062 EscapingInternalFunctions.insert(F).second) { 01063 // We found a function that is just now escaping. Mark it as if it 01064 // didn't have internal linkage. 01065 AddConstraintsForNonInternalLinkage(F); 01066 DEBUG(std::cerr << "Found escaping internal function: " 01067 << F->getName() << "\n"); 01068 ++NumEscapingFunctions; 01069 } 01070 01071 // Check to see if we have discovered any new callees of the indirect call 01072 // sites. If so, add constraints to the analysis. 01073 for (unsigned i = 0, e = IndirectCalls.size(); i != e; ++i) { 01074 CallSite CS = IndirectCalls[i]; 01075 std::vector<Function*> &KnownCallees = IndirectCallees[CS]; 01076 Node *CN = getNode(CS.getCalledValue()); 01077 01078 for (Node::iterator NI = CN->begin(), E = CN->end(); NI != E; ++NI) 01079 if (Function *F = dyn_cast_or_null<Function>((*NI)->getValue())) { 01080 std::vector<Function*>::iterator IP = 01081 std::lower_bound(KnownCallees.begin(), KnownCallees.end(), F); 01082 if (IP == KnownCallees.end() || *IP != F) { 01083 // Add the constraints for the call now. 01084 AddConstraintsForCall(CS, F); 01085 DEBUG(std::cerr << "Found actual callee '" 01086 << F->getName() << "' for call: " 01087 << *CS.getInstruction() << "\n"); 01088 ++NumIndirectCallees; 01089 KnownCallees.insert(IP, F); 01090 } 01091 } 01092 } 01093 } 01094 } 01095 } 01096 01097 01098 01099 //===----------------------------------------------------------------------===// 01100 // Debugging Output 01101 //===----------------------------------------------------------------------===// 01102 01103 void Andersens::PrintNode(Node *N) { 01104 if (N == &GraphNodes[UniversalSet]) { 01105 std::cerr << "<universal>"; 01106 return; 01107 } else if (N == &GraphNodes[NullPtr]) { 01108 std::cerr << "<nullptr>"; 01109 return; 01110 } else if (N == &GraphNodes[NullObject]) { 01111 std::cerr << "<null>"; 01112 return; 01113 } 01114 01115 assert(N->getValue() != 0 && "Never set node label!"); 01116 Value *V = N->getValue(); 01117 if (Function *F = dyn_cast<Function>(V)) { 01118 if (isa<PointerType>(F->getFunctionType()->getReturnType()) && 01119 N == getReturnNode(F)) { 01120 std::cerr << F->getName() << ":retval"; 01121 return; 01122 } else if (F->getFunctionType()->isVarArg() && N == getVarargNode(F)) { 01123 std::cerr << F->getName() << ":vararg"; 01124 return; 01125 } 01126 } 01127 01128 if (Instruction *I = dyn_cast<Instruction>(V)) 01129 std::cerr << I->getParent()->getParent()->getName() << ":"; 01130 else if (Argument *Arg = dyn_cast<Argument>(V)) 01131 std::cerr << Arg->getParent()->getName() << ":"; 01132 01133 if (V->hasName()) 01134 std::cerr << V->getName(); 01135 else 01136 std::cerr << "(unnamed)"; 01137 01138 if (isa<GlobalValue>(V) || isa<AllocationInst>(V)) 01139 if (N == getObject(V)) 01140 std::cerr << "<mem>"; 01141 } 01142 01143 void Andersens::PrintConstraints() { 01144 std::cerr << "Constraints:\n"; 01145 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01146 std::cerr << " #" << i << ": "; 01147 Constraint &C = Constraints[i]; 01148 if (C.Type == Constraint::Store) 01149 std::cerr << "*"; 01150 PrintNode(C.Dest); 01151 std::cerr << " = "; 01152 if (C.Type == Constraint::Load) 01153 std::cerr << "*"; 01154 PrintNode(C.Src); 01155 std::cerr << "\n"; 01156 } 01157 } 01158 01159 void Andersens::PrintPointsToGraph() { 01160 std::cerr << "Points-to graph:\n"; 01161 for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) { 01162 Node *N = &GraphNodes[i]; 01163 std::cerr << "[" << (N->end() - N->begin()) << "] "; 01164 PrintNode(N); 01165 std::cerr << "\t--> "; 01166 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { 01167 if (I != N->begin()) std::cerr << ", "; 01168 PrintNode(*I); 01169 } 01170 std::cerr << "\n"; 01171 } 01172 }