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 V->dump(); 00264 assert(I != ValueNodes.end() && 00265 "Value does not have a node in the points-to graph!"); 00266 } 00267 return &GraphNodes[I->second]; 00268 } 00269 00270 /// getObject - Return the node corresponding to the memory object for the 00271 /// specified global or allocation instruction. 00272 Node *getObject(Value *V) { 00273 std::map<Value*, unsigned>::iterator I = ObjectNodes.find(V); 00274 assert(I != ObjectNodes.end() && 00275 "Value does not have an object in the points-to graph!"); 00276 return &GraphNodes[I->second]; 00277 } 00278 00279 /// getReturnNode - Return the node representing the return value for the 00280 /// specified function. 00281 Node *getReturnNode(Function *F) { 00282 std::map<Function*, unsigned>::iterator I = ReturnNodes.find(F); 00283 assert(I != ReturnNodes.end() && "Function does not return a value!"); 00284 return &GraphNodes[I->second]; 00285 } 00286 00287 /// getVarargNode - Return the node representing the variable arguments 00288 /// formal for the specified function. 00289 Node *getVarargNode(Function *F) { 00290 std::map<Function*, unsigned>::iterator I = VarargNodes.find(F); 00291 assert(I != VarargNodes.end() && "Function does not take var args!"); 00292 return &GraphNodes[I->second]; 00293 } 00294 00295 /// getNodeValue - Get the node for the specified LLVM value and set the 00296 /// value for it to be the specified value. 00297 Node *getNodeValue(Value &V) { 00298 return getNode(&V)->setValue(&V); 00299 } 00300 00301 void IdentifyObjects(Module &M); 00302 void CollectConstraints(Module &M); 00303 void SolveConstraints(); 00304 00305 Node *getNodeForConstantPointer(Constant *C); 00306 Node *getNodeForConstantPointerTarget(Constant *C); 00307 void AddGlobalInitializerConstraints(Node *N, Constant *C); 00308 00309 void AddConstraintsForNonInternalLinkage(Function *F); 00310 void AddConstraintsForCall(CallSite CS, Function *F); 00311 bool AddConstraintsForExternalCall(CallSite CS, Function *F); 00312 00313 00314 void PrintNode(Node *N); 00315 void PrintConstraints(); 00316 void PrintPointsToGraph(); 00317 00318 //===------------------------------------------------------------------===// 00319 // Instruction visitation methods for adding constraints 00320 // 00321 friend class InstVisitor<Andersens>; 00322 void visitReturnInst(ReturnInst &RI); 00323 void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); } 00324 void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); } 00325 void visitCallSite(CallSite CS); 00326 void visitAllocationInst(AllocationInst &AI); 00327 void visitLoadInst(LoadInst &LI); 00328 void visitStoreInst(StoreInst &SI); 00329 void visitGetElementPtrInst(GetElementPtrInst &GEP); 00330 void visitPHINode(PHINode &PN); 00331 void visitCastInst(CastInst &CI); 00332 void visitSetCondInst(SetCondInst &SCI) {} // NOOP! 00333 void visitSelectInst(SelectInst &SI); 00334 void visitVAArg(VAArgInst &I); 00335 void visitInstruction(Instruction &I); 00336 }; 00337 00338 RegisterOpt<Andersens> X("anders-aa", 00339 "Andersen's Interprocedural Alias Analysis"); 00340 RegisterAnalysisGroup<AliasAnalysis, Andersens> Y; 00341 } 00342 00343 ModulePass *llvm::createAndersensPass() { return new Andersens(); } 00344 00345 //===----------------------------------------------------------------------===// 00346 // AliasAnalysis Interface Implementation 00347 //===----------------------------------------------------------------------===// 00348 00349 AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size, 00350 const Value *V2, unsigned V2Size) { 00351 Node *N1 = getNode(const_cast<Value*>(V1)); 00352 Node *N2 = getNode(const_cast<Value*>(V2)); 00353 00354 // Check to see if the two pointers are known to not alias. They don't alias 00355 // if their points-to sets do not intersect. 00356 if (!N1->intersectsIgnoring(N2, &GraphNodes[NullObject])) 00357 return NoAlias; 00358 00359 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00360 } 00361 00362 AliasAnalysis::ModRefResult 00363 Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00364 // The only thing useful that we can contribute for mod/ref information is 00365 // when calling external function calls: if we know that memory never escapes 00366 // from the program, it cannot be modified by an external call. 00367 // 00368 // NOTE: This is not really safe, at least not when the entire program is not 00369 // available. The deal is that the external function could call back into the 00370 // program and modify stuff. We ignore this technical niggle for now. This 00371 // is, after all, a "research quality" implementation of Andersen's analysis. 00372 if (Function *F = CS.getCalledFunction()) 00373 if (F->isExternal()) { 00374 Node *N1 = getNode(P); 00375 bool PointsToUniversalSet = false; 00376 00377 if (N1->begin() == N1->end()) 00378 return NoModRef; // P doesn't point to anything. 00379 00380 // Get the first pointee. 00381 Node *FirstPointee = *N1->begin(); 00382 if (FirstPointee != &GraphNodes[UniversalSet]) 00383 return NoModRef; // P doesn't point to the universal set. 00384 } 00385 00386 return AliasAnalysis::getModRefInfo(CS, P, Size); 00387 } 00388 00389 /// getMustAlias - We can provide must alias information if we know that a 00390 /// pointer can only point to a specific function or the null pointer. 00391 /// Unfortunately we cannot determine must-alias information for global 00392 /// variables or any other memory memory objects because we do not track whether 00393 /// a pointer points to the beginning of an object or a field of it. 00394 void Andersens::getMustAliases(Value *P, std::vector<Value*> &RetVals) { 00395 Node *N = getNode(P); 00396 Node::iterator I = N->begin(); 00397 if (I != N->end()) { 00398 // If there is exactly one element in the points-to set for the object... 00399 ++I; 00400 if (I == N->end()) { 00401 Node *Pointee = *N->begin(); 00402 00403 // If a function is the only object in the points-to set, then it must be 00404 // the destination. Note that we can't handle global variables here, 00405 // because we don't know if the pointer is actually pointing to a field of 00406 // the global or to the beginning of it. 00407 if (Value *V = Pointee->getValue()) { 00408 if (Function *F = dyn_cast<Function>(V)) 00409 RetVals.push_back(F); 00410 } else { 00411 // If the object in the points-to set is the null object, then the null 00412 // pointer is a must alias. 00413 if (Pointee == &GraphNodes[NullObject]) 00414 RetVals.push_back(Constant::getNullValue(P->getType())); 00415 } 00416 } 00417 } 00418 00419 AliasAnalysis::getMustAliases(P, RetVals); 00420 } 00421 00422 /// pointsToConstantMemory - If we can determine that this pointer only points 00423 /// to constant memory, return true. In practice, this means that if the 00424 /// pointer can only point to constant globals, functions, or the null pointer, 00425 /// return true. 00426 /// 00427 bool Andersens::pointsToConstantMemory(const Value *P) { 00428 Node *N = getNode((Value*)P); 00429 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { 00430 if (Value *V = (*I)->getValue()) { 00431 if (!isa<GlobalValue>(V) || (isa<GlobalVariable>(V) && 00432 !cast<GlobalVariable>(V)->isConstant())) 00433 return AliasAnalysis::pointsToConstantMemory(P); 00434 } else { 00435 if (*I != &GraphNodes[NullObject]) 00436 return AliasAnalysis::pointsToConstantMemory(P); 00437 } 00438 } 00439 00440 return true; 00441 } 00442 00443 //===----------------------------------------------------------------------===// 00444 // Object Identification Phase 00445 //===----------------------------------------------------------------------===// 00446 00447 /// IdentifyObjects - This stage scans the program, adding an entry to the 00448 /// GraphNodes list for each memory object in the program (global stack or 00449 /// heap), and populates the ValueNodes and ObjectNodes maps for these objects. 00450 /// 00451 void Andersens::IdentifyObjects(Module &M) { 00452 unsigned NumObjects = 0; 00453 00454 // Object #0 is always the universal set: the object that we don't know 00455 // anything about. 00456 assert(NumObjects == UniversalSet && "Something changed!"); 00457 ++NumObjects; 00458 00459 // Object #1 always represents the null pointer. 00460 assert(NumObjects == NullPtr && "Something changed!"); 00461 ++NumObjects; 00462 00463 // Object #2 always represents the null object (the object pointed to by null) 00464 assert(NumObjects == NullObject && "Something changed!"); 00465 ++NumObjects; 00466 00467 // Add all the globals first. 00468 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 00469 I != E; ++I) { 00470 ObjectNodes[I] = NumObjects++; 00471 ValueNodes[I] = NumObjects++; 00472 } 00473 00474 // Add nodes for all of the functions and the instructions inside of them. 00475 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 00476 // The function itself is a memory object. 00477 ValueNodes[F] = NumObjects++; 00478 ObjectNodes[F] = NumObjects++; 00479 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00480 ReturnNodes[F] = NumObjects++; 00481 if (F->getFunctionType()->isVarArg()) 00482 VarargNodes[F] = NumObjects++; 00483 00484 // Add nodes for all of the incoming pointer arguments. 00485 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00486 I != E; ++I) 00487 if (isa<PointerType>(I->getType())) 00488 ValueNodes[I] = NumObjects++; 00489 00490 // Scan the function body, creating a memory object for each heap/stack 00491 // allocation in the body of the function and a node to represent all 00492 // pointer values defined by instructions and used as operands. 00493 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 00494 // If this is an heap or stack allocation, create a node for the memory 00495 // object. 00496 if (isa<PointerType>(II->getType())) { 00497 ValueNodes[&*II] = NumObjects++; 00498 if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II)) 00499 ObjectNodes[AI] = NumObjects++; 00500 } 00501 } 00502 } 00503 00504 // Now that we know how many objects to create, make them all now! 00505 GraphNodes.resize(NumObjects); 00506 NumNodes += NumObjects; 00507 } 00508 00509 //===----------------------------------------------------------------------===// 00510 // Constraint Identification Phase 00511 //===----------------------------------------------------------------------===// 00512 00513 /// getNodeForConstantPointer - Return the node corresponding to the constant 00514 /// pointer itself. 00515 Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) { 00516 assert(isa<PointerType>(C->getType()) && "Not a constant pointer!"); 00517 00518 if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C)) 00519 return &GraphNodes[NullPtr]; 00520 else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 00521 return getNode(GV); 00522 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00523 switch (CE->getOpcode()) { 00524 case Instruction::GetElementPtr: 00525 return getNodeForConstantPointer(CE->getOperand(0)); 00526 case Instruction::Cast: 00527 if (isa<PointerType>(CE->getOperand(0)->getType())) 00528 return getNodeForConstantPointer(CE->getOperand(0)); 00529 else 00530 return &GraphNodes[UniversalSet]; 00531 default: 00532 std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; 00533 assert(0); 00534 } 00535 } else { 00536 assert(0 && "Unknown constant pointer!"); 00537 } 00538 return 0; 00539 } 00540 00541 /// getNodeForConstantPointerTarget - Return the node POINTED TO by the 00542 /// specified constant pointer. 00543 Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) { 00544 assert(isa<PointerType>(C->getType()) && "Not a constant pointer!"); 00545 00546 if (isa<ConstantPointerNull>(C)) 00547 return &GraphNodes[NullObject]; 00548 else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 00549 return getObject(GV); 00550 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00551 switch (CE->getOpcode()) { 00552 case Instruction::GetElementPtr: 00553 return getNodeForConstantPointerTarget(CE->getOperand(0)); 00554 case Instruction::Cast: 00555 if (isa<PointerType>(CE->getOperand(0)->getType())) 00556 return getNodeForConstantPointerTarget(CE->getOperand(0)); 00557 else 00558 return &GraphNodes[UniversalSet]; 00559 default: 00560 std::cerr << "Constant Expr not yet handled: " << *CE << "\n"; 00561 assert(0); 00562 } 00563 } else { 00564 assert(0 && "Unknown constant pointer!"); 00565 } 00566 return 0; 00567 } 00568 00569 /// AddGlobalInitializerConstraints - Add inclusion constraints for the memory 00570 /// object N, which contains values indicated by C. 00571 void Andersens::AddGlobalInitializerConstraints(Node *N, Constant *C) { 00572 if (C->getType()->isFirstClassType()) { 00573 if (isa<PointerType>(C->getType())) 00574 N->copyFrom(getNodeForConstantPointer(C)); 00575 00576 } else if (C->isNullValue()) { 00577 N->addPointerTo(&GraphNodes[NullObject]); 00578 return; 00579 } else if (!isa<UndefValue>(C)) { 00580 // If this is an array or struct, include constraints for each element. 00581 assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C)); 00582 for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) 00583 AddGlobalInitializerConstraints(N, cast<Constant>(C->getOperand(i))); 00584 } 00585 } 00586 00587 /// AddConstraintsForNonInternalLinkage - If this function does not have 00588 /// internal linkage, realize that we can't trust anything passed into or 00589 /// returned by this function. 00590 void Andersens::AddConstraintsForNonInternalLinkage(Function *F) { 00591 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) 00592 if (isa<PointerType>(I->getType())) 00593 // If this is an argument of an externally accessible function, the 00594 // incoming pointer might point to anything. 00595 Constraints.push_back(Constraint(Constraint::Copy, getNode(I), 00596 &GraphNodes[UniversalSet])); 00597 } 00598 00599 /// AddConstraintsForCall - If this is a call to a "known" function, add the 00600 /// constraints and return true. If this is a call to an unknown function, 00601 /// return false. 00602 bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) { 00603 assert(F->isExternal() && "Not an external function!"); 00604 00605 // These functions don't induce any points-to constraints. 00606 if (F->getName() == "atoi" || F->getName() == "atof" || 00607 F->getName() == "atol" || F->getName() == "atoll" || 00608 F->getName() == "remove" || F->getName() == "unlink" || 00609 F->getName() == "rename" || F->getName() == "memcmp" || 00610 F->getName() == "llvm.memset.i32" || 00611 F->getName() == "llvm.memset.i64" || 00612 F->getName() == "strcmp" || F->getName() == "strncmp" || 00613 F->getName() == "execl" || F->getName() == "execlp" || 00614 F->getName() == "execle" || F->getName() == "execv" || 00615 F->getName() == "execvp" || F->getName() == "chmod" || 00616 F->getName() == "puts" || F->getName() == "write" || 00617 F->getName() == "open" || F->getName() == "create" || 00618 F->getName() == "truncate" || F->getName() == "chdir" || 00619 F->getName() == "mkdir" || F->getName() == "rmdir" || 00620 F->getName() == "read" || F->getName() == "pipe" || 00621 F->getName() == "wait" || F->getName() == "time" || 00622 F->getName() == "stat" || F->getName() == "fstat" || 00623 F->getName() == "lstat" || F->getName() == "strtod" || 00624 F->getName() == "strtof" || F->getName() == "strtold" || 00625 F->getName() == "fopen" || F->getName() == "fdopen" || 00626 F->getName() == "freopen" || 00627 F->getName() == "fflush" || F->getName() == "feof" || 00628 F->getName() == "fileno" || F->getName() == "clearerr" || 00629 F->getName() == "rewind" || F->getName() == "ftell" || 00630 F->getName() == "ferror" || F->getName() == "fgetc" || 00631 F->getName() == "fgetc" || F->getName() == "_IO_getc" || 00632 F->getName() == "fwrite" || F->getName() == "fread" || 00633 F->getName() == "fgets" || F->getName() == "ungetc" || 00634 F->getName() == "fputc" || 00635 F->getName() == "fputs" || F->getName() == "putc" || 00636 F->getName() == "ftell" || F->getName() == "rewind" || 00637 F->getName() == "_IO_putc" || F->getName() == "fseek" || 00638 F->getName() == "fgetpos" || F->getName() == "fsetpos" || 00639 F->getName() == "printf" || F->getName() == "fprintf" || 00640 F->getName() == "sprintf" || F->getName() == "vprintf" || 00641 F->getName() == "vfprintf" || F->getName() == "vsprintf" || 00642 F->getName() == "scanf" || F->getName() == "fscanf" || 00643 F->getName() == "sscanf" || F->getName() == "__assert_fail" || 00644 F->getName() == "modf") 00645 return true; 00646 00647 00648 // These functions do induce points-to edges. 00649 if (F->getName() == "llvm.memcpy.i32" || F->getName() == "llvm.memcpy.i64" || 00650 F->getName() == "llvm.memmove.i32" ||F->getName() == "llvm.memmove.i64" || 00651 F->getName() == "memmove") { 00652 // Note: this is a poor approximation, this says Dest = Src, instead of 00653 // *Dest = *Src. 00654 Constraints.push_back(Constraint(Constraint::Copy, 00655 getNode(CS.getArgument(0)), 00656 getNode(CS.getArgument(1)))); 00657 return true; 00658 } 00659 00660 // Result = Arg0 00661 if (F->getName() == "realloc" || F->getName() == "strchr" || 00662 F->getName() == "strrchr" || F->getName() == "strstr" || 00663 F->getName() == "strtok") { 00664 Constraints.push_back(Constraint(Constraint::Copy, 00665 getNode(CS.getInstruction()), 00666 getNode(CS.getArgument(0)))); 00667 return true; 00668 } 00669 00670 return false; 00671 } 00672 00673 00674 00675 /// CollectConstraints - This stage scans the program, adding a constraint to 00676 /// the Constraints list for each instruction in the program that induces a 00677 /// constraint, and setting up the initial points-to graph. 00678 /// 00679 void Andersens::CollectConstraints(Module &M) { 00680 // First, the universal set points to itself. 00681 GraphNodes[UniversalSet].addPointerTo(&GraphNodes[UniversalSet]); 00682 //Constraints.push_back(Constraint(Constraint::Load, &GraphNodes[UniversalSet], 00683 // &GraphNodes[UniversalSet])); 00684 Constraints.push_back(Constraint(Constraint::Store, &GraphNodes[UniversalSet], 00685 &GraphNodes[UniversalSet])); 00686 00687 // Next, the null pointer points to the null object. 00688 GraphNodes[NullPtr].addPointerTo(&GraphNodes[NullObject]); 00689 00690 // Next, add any constraints on global variables and their initializers. 00691 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 00692 I != E; ++I) { 00693 // Associate the address of the global object as pointing to the memory for 00694 // the global: &G = <G memory> 00695 Node *Object = getObject(I); 00696 Object->setValue(I); 00697 getNodeValue(*I)->addPointerTo(Object); 00698 00699 if (I->hasInitializer()) { 00700 AddGlobalInitializerConstraints(Object, I->getInitializer()); 00701 } else { 00702 // If it doesn't have an initializer (i.e. it's defined in another 00703 // translation unit), it points to the universal set. 00704 Constraints.push_back(Constraint(Constraint::Copy, Object, 00705 &GraphNodes[UniversalSet])); 00706 } 00707 } 00708 00709 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 00710 // Make the function address point to the function object. 00711 getNodeValue(*F)->addPointerTo(getObject(F)->setValue(F)); 00712 00713 // Set up the return value node. 00714 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00715 getReturnNode(F)->setValue(F); 00716 if (F->getFunctionType()->isVarArg()) 00717 getVarargNode(F)->setValue(F); 00718 00719 // Set up incoming argument nodes. 00720 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00721 I != E; ++I) 00722 if (isa<PointerType>(I->getType())) 00723 getNodeValue(*I); 00724 00725 if (!F->hasInternalLinkage()) 00726 AddConstraintsForNonInternalLinkage(F); 00727 00728 if (!F->isExternal()) { 00729 // Scan the function body, creating a memory object for each heap/stack 00730 // allocation in the body of the function and a node to represent all 00731 // pointer values defined by instructions and used as operands. 00732 visit(F); 00733 } else { 00734 // External functions that return pointers return the universal set. 00735 if (isa<PointerType>(F->getFunctionType()->getReturnType())) 00736 Constraints.push_back(Constraint(Constraint::Copy, 00737 getReturnNode(F), 00738 &GraphNodes[UniversalSet])); 00739 00740 // Any pointers that are passed into the function have the universal set 00741 // stored into them. 00742 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00743 I != E; ++I) 00744 if (isa<PointerType>(I->getType())) { 00745 // Pointers passed into external functions could have anything stored 00746 // through them. 00747 Constraints.push_back(Constraint(Constraint::Store, getNode(I), 00748 &GraphNodes[UniversalSet])); 00749 // Memory objects passed into external function calls can have the 00750 // universal set point to them. 00751 Constraints.push_back(Constraint(Constraint::Copy, 00752 &GraphNodes[UniversalSet], 00753 getNode(I))); 00754 } 00755 00756 // If this is an external varargs function, it can also store pointers 00757 // into any pointers passed through the varargs section. 00758 if (F->getFunctionType()->isVarArg()) 00759 Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F), 00760 &GraphNodes[UniversalSet])); 00761 } 00762 } 00763 NumConstraints += Constraints.size(); 00764 } 00765 00766 00767 void Andersens::visitInstruction(Instruction &I) { 00768 #ifdef NDEBUG 00769 return; // This function is just a big assert. 00770 #endif 00771 if (isa<BinaryOperator>(I)) 00772 return; 00773 // Most instructions don't have any effect on pointer values. 00774 switch (I.getOpcode()) { 00775 case Instruction::Br: 00776 case Instruction::Switch: 00777 case Instruction::Unwind: 00778 case Instruction::Unreachable: 00779 case Instruction::Free: 00780 case Instruction::Shl: 00781 case Instruction::Shr: 00782 return; 00783 default: 00784 // Is this something we aren't handling yet? 00785 std::cerr << "Unknown instruction: " << I; 00786 abort(); 00787 } 00788 } 00789 00790 void Andersens::visitAllocationInst(AllocationInst &AI) { 00791 getNodeValue(AI)->addPointerTo(getObject(&AI)->setValue(&AI)); 00792 } 00793 00794 void Andersens::visitReturnInst(ReturnInst &RI) { 00795 if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) 00796 // return V --> <Copy/retval{F}/v> 00797 Constraints.push_back(Constraint(Constraint::Copy, 00798 getReturnNode(RI.getParent()->getParent()), 00799 getNode(RI.getOperand(0)))); 00800 } 00801 00802 void Andersens::visitLoadInst(LoadInst &LI) { 00803 if (isa<PointerType>(LI.getType())) 00804 // P1 = load P2 --> <Load/P1/P2> 00805 Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI), 00806 getNode(LI.getOperand(0)))); 00807 } 00808 00809 void Andersens::visitStoreInst(StoreInst &SI) { 00810 if (isa<PointerType>(SI.getOperand(0)->getType())) 00811 // store P1, P2 --> <Store/P2/P1> 00812 Constraints.push_back(Constraint(Constraint::Store, 00813 getNode(SI.getOperand(1)), 00814 getNode(SI.getOperand(0)))); 00815 } 00816 00817 void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) { 00818 // P1 = getelementptr P2, ... --> <Copy/P1/P2> 00819 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP), 00820 getNode(GEP.getOperand(0)))); 00821 } 00822 00823 void Andersens::visitPHINode(PHINode &PN) { 00824 if (isa<PointerType>(PN.getType())) { 00825 Node *PNN = getNodeValue(PN); 00826 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 00827 // P1 = phi P2, P3 --> <Copy/P1/P2>, <Copy/P1/P3>, ... 00828 Constraints.push_back(Constraint(Constraint::Copy, PNN, 00829 getNode(PN.getIncomingValue(i)))); 00830 } 00831 } 00832 00833 void Andersens::visitCastInst(CastInst &CI) { 00834 Value *Op = CI.getOperand(0); 00835 if (isa<PointerType>(CI.getType())) { 00836 if (isa<PointerType>(Op->getType())) { 00837 // P1 = cast P2 --> <Copy/P1/P2> 00838 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), 00839 getNode(CI.getOperand(0)))); 00840 } else { 00841 // P1 = cast int --> <Copy/P1/Univ> 00842 #if 0 00843 Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI), 00844 &GraphNodes[UniversalSet])); 00845 #else 00846 getNodeValue(CI); 00847 #endif 00848 } 00849 } else if (isa<PointerType>(Op->getType())) { 00850 // int = cast P1 --> <Copy/Univ/P1> 00851 #if 0 00852 Constraints.push_back(Constraint(Constraint::Copy, 00853 &GraphNodes[UniversalSet], 00854 getNode(CI.getOperand(0)))); 00855 #else 00856 getNode(CI.getOperand(0)); 00857 #endif 00858 } 00859 } 00860 00861 void Andersens::visitSelectInst(SelectInst &SI) { 00862 if (isa<PointerType>(SI.getType())) { 00863 Node *SIN = getNodeValue(SI); 00864 // P1 = select C, P2, P3 ---> <Copy/P1/P2>, <Copy/P1/P3> 00865 Constraints.push_back(Constraint(Constraint::Copy, SIN, 00866 getNode(SI.getOperand(1)))); 00867 Constraints.push_back(Constraint(Constraint::Copy, SIN, 00868 getNode(SI.getOperand(2)))); 00869 } 00870 } 00871 00872 void Andersens::visitVAArg(VAArgInst &I) { 00873 assert(0 && "vaarg not handled yet!"); 00874 } 00875 00876 /// AddConstraintsForCall - Add constraints for a call with actual arguments 00877 /// specified by CS to the function specified by F. Note that the types of 00878 /// arguments might not match up in the case where this is an indirect call and 00879 /// the function pointer has been casted. If this is the case, do something 00880 /// reasonable. 00881 void Andersens::AddConstraintsForCall(CallSite CS, Function *F) { 00882 // If this is a call to an external function, handle it directly to get some 00883 // taste of context sensitivity. 00884 if (F->isExternal() && AddConstraintsForExternalCall(CS, F)) 00885 return; 00886 00887 if (isa<PointerType>(CS.getType())) { 00888 Node *CSN = getNode(CS.getInstruction()); 00889 if (isa<PointerType>(F->getFunctionType()->getReturnType())) { 00890 Constraints.push_back(Constraint(Constraint::Copy, CSN, 00891 getReturnNode(F))); 00892 } else { 00893 // If the function returns a non-pointer value, handle this just like we 00894 // treat a nonpointer cast to pointer. 00895 Constraints.push_back(Constraint(Constraint::Copy, CSN, 00896 &GraphNodes[UniversalSet])); 00897 } 00898 } else if (isa<PointerType>(F->getFunctionType()->getReturnType())) { 00899 Constraints.push_back(Constraint(Constraint::Copy, 00900 &GraphNodes[UniversalSet], 00901 getReturnNode(F))); 00902 } 00903 00904 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 00905 CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end(); 00906 for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI) 00907 if (isa<PointerType>(AI->getType())) { 00908 if (isa<PointerType>((*ArgI)->getType())) { 00909 // Copy the actual argument into the formal argument. 00910 Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), 00911 getNode(*ArgI))); 00912 } else { 00913 Constraints.push_back(Constraint(Constraint::Copy, getNode(AI), 00914 &GraphNodes[UniversalSet])); 00915 } 00916 } else if (isa<PointerType>((*ArgI)->getType())) { 00917 Constraints.push_back(Constraint(Constraint::Copy, 00918 &GraphNodes[UniversalSet], 00919 getNode(*ArgI))); 00920 } 00921 00922 // Copy all pointers passed through the varargs section to the varargs node. 00923 if (F->getFunctionType()->isVarArg()) 00924 for (; ArgI != ArgE; ++ArgI) 00925 if (isa<PointerType>((*ArgI)->getType())) 00926 Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F), 00927 getNode(*ArgI))); 00928 // If more arguments are passed in than we track, just drop them on the floor. 00929 } 00930 00931 void Andersens::visitCallSite(CallSite CS) { 00932 if (isa<PointerType>(CS.getType())) 00933 getNodeValue(*CS.getInstruction()); 00934 00935 if (Function *F = CS.getCalledFunction()) { 00936 AddConstraintsForCall(CS, F); 00937 } else { 00938 // We don't handle indirect call sites yet. Keep track of them for when we 00939 // discover the call graph incrementally. 00940 IndirectCalls.push_back(CS); 00941 } 00942 } 00943 00944 //===----------------------------------------------------------------------===// 00945 // Constraint Solving Phase 00946 //===----------------------------------------------------------------------===// 00947 00948 /// intersects - Return true if the points-to set of this node intersects 00949 /// with the points-to set of the specified node. 00950 bool Andersens::Node::intersects(Node *N) const { 00951 iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); 00952 while (I1 != E1 && I2 != E2) { 00953 if (*I1 == *I2) return true; 00954 if (*I1 < *I2) 00955 ++I1; 00956 else 00957 ++I2; 00958 } 00959 return false; 00960 } 00961 00962 /// intersectsIgnoring - Return true if the points-to set of this node 00963 /// intersects with the points-to set of the specified node on any nodes 00964 /// except for the specified node to ignore. 00965 bool Andersens::Node::intersectsIgnoring(Node *N, Node *Ignoring) const { 00966 iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end(); 00967 while (I1 != E1 && I2 != E2) { 00968 if (*I1 == *I2) { 00969 if (*I1 != Ignoring) return true; 00970 ++I1; ++I2; 00971 } else if (*I1 < *I2) 00972 ++I1; 00973 else 00974 ++I2; 00975 } 00976 return false; 00977 } 00978 00979 // Copy constraint: all edges out of the source node get copied to the 00980 // destination node. This returns true if a change is made. 00981 bool Andersens::Node::copyFrom(Node *N) { 00982 // Use a mostly linear-time merge since both of the lists are sorted. 00983 bool Changed = false; 00984 iterator I = N->begin(), E = N->end(); 00985 unsigned i = 0; 00986 while (I != E && i != Pointees.size()) { 00987 if (Pointees[i] < *I) { 00988 ++i; 00989 } else if (Pointees[i] == *I) { 00990 ++i; ++I; 00991 } else { 00992 // We found a new element to copy over. 00993 Changed = true; 00994 Pointees.insert(Pointees.begin()+i, *I); 00995 ++i; ++I; 00996 } 00997 } 00998 00999 if (I != E) { 01000 Pointees.insert(Pointees.end(), I, E); 01001 Changed = true; 01002 } 01003 01004 return Changed; 01005 } 01006 01007 bool Andersens::Node::loadFrom(Node *N) { 01008 bool Changed = false; 01009 for (iterator I = N->begin(), E = N->end(); I != E; ++I) 01010 Changed |= copyFrom(*I); 01011 return Changed; 01012 } 01013 01014 bool Andersens::Node::storeThrough(Node *N) { 01015 bool Changed = false; 01016 for (iterator I = begin(), E = end(); I != E; ++I) 01017 Changed |= (*I)->copyFrom(N); 01018 return Changed; 01019 } 01020 01021 01022 /// SolveConstraints - This stage iteratively processes the constraints list 01023 /// propagating constraints (adding edges to the Nodes in the points-to graph) 01024 /// until a fixed point is reached. 01025 /// 01026 void Andersens::SolveConstraints() { 01027 bool Changed = true; 01028 unsigned Iteration = 0; 01029 while (Changed) { 01030 Changed = false; 01031 ++NumIters; 01032 DEBUG(std::cerr << "Starting iteration #" << Iteration++ << "!\n"); 01033 01034 // Loop over all of the constraints, applying them in turn. 01035 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01036 Constraint &C = Constraints[i]; 01037 switch (C.Type) { 01038 case Constraint::Copy: 01039 Changed |= C.Dest->copyFrom(C.Src); 01040 break; 01041 case Constraint::Load: 01042 Changed |= C.Dest->loadFrom(C.Src); 01043 break; 01044 case Constraint::Store: 01045 Changed |= C.Dest->storeThrough(C.Src); 01046 break; 01047 default: 01048 assert(0 && "Unknown constraint!"); 01049 } 01050 } 01051 01052 if (Changed) { 01053 // Check to see if any internal function's addresses have been passed to 01054 // external functions. If so, we have to assume that their incoming 01055 // arguments could be anything. If there are any internal functions in 01056 // the universal node that we don't know about, we must iterate. 01057 for (Node::iterator I = GraphNodes[UniversalSet].begin(), 01058 E = GraphNodes[UniversalSet].end(); I != E; ++I) 01059 if (Function *F = dyn_cast_or_null<Function>((*I)->getValue())) 01060 if (F->hasInternalLinkage() && 01061 EscapingInternalFunctions.insert(F).second) { 01062 // We found a function that is just now escaping. Mark it as if it 01063 // didn't have internal linkage. 01064 AddConstraintsForNonInternalLinkage(F); 01065 DEBUG(std::cerr << "Found escaping internal function: " 01066 << F->getName() << "\n"); 01067 ++NumEscapingFunctions; 01068 } 01069 01070 // Check to see if we have discovered any new callees of the indirect call 01071 // sites. If so, add constraints to the analysis. 01072 for (unsigned i = 0, e = IndirectCalls.size(); i != e; ++i) { 01073 CallSite CS = IndirectCalls[i]; 01074 std::vector<Function*> &KnownCallees = IndirectCallees[CS]; 01075 Node *CN = getNode(CS.getCalledValue()); 01076 01077 for (Node::iterator NI = CN->begin(), E = CN->end(); NI != E; ++NI) 01078 if (Function *F = dyn_cast_or_null<Function>((*NI)->getValue())) { 01079 std::vector<Function*>::iterator IP = 01080 std::lower_bound(KnownCallees.begin(), KnownCallees.end(), F); 01081 if (IP == KnownCallees.end() || *IP != F) { 01082 // Add the constraints for the call now. 01083 AddConstraintsForCall(CS, F); 01084 DEBUG(std::cerr << "Found actual callee '" 01085 << F->getName() << "' for call: " 01086 << *CS.getInstruction() << "\n"); 01087 ++NumIndirectCallees; 01088 KnownCallees.insert(IP, F); 01089 } 01090 } 01091 } 01092 } 01093 } 01094 } 01095 01096 01097 01098 //===----------------------------------------------------------------------===// 01099 // Debugging Output 01100 //===----------------------------------------------------------------------===// 01101 01102 void Andersens::PrintNode(Node *N) { 01103 if (N == &GraphNodes[UniversalSet]) { 01104 std::cerr << "<universal>"; 01105 return; 01106 } else if (N == &GraphNodes[NullPtr]) { 01107 std::cerr << "<nullptr>"; 01108 return; 01109 } else if (N == &GraphNodes[NullObject]) { 01110 std::cerr << "<null>"; 01111 return; 01112 } 01113 01114 assert(N->getValue() != 0 && "Never set node label!"); 01115 Value *V = N->getValue(); 01116 if (Function *F = dyn_cast<Function>(V)) { 01117 if (isa<PointerType>(F->getFunctionType()->getReturnType()) && 01118 N == getReturnNode(F)) { 01119 std::cerr << F->getName() << ":retval"; 01120 return; 01121 } else if (F->getFunctionType()->isVarArg() && N == getVarargNode(F)) { 01122 std::cerr << F->getName() << ":vararg"; 01123 return; 01124 } 01125 } 01126 01127 if (Instruction *I = dyn_cast<Instruction>(V)) 01128 std::cerr << I->getParent()->getParent()->getName() << ":"; 01129 else if (Argument *Arg = dyn_cast<Argument>(V)) 01130 std::cerr << Arg->getParent()->getName() << ":"; 01131 01132 if (V->hasName()) 01133 std::cerr << V->getName(); 01134 else 01135 std::cerr << "(unnamed)"; 01136 01137 if (isa<GlobalValue>(V) || isa<AllocationInst>(V)) 01138 if (N == getObject(V)) 01139 std::cerr << "<mem>"; 01140 } 01141 01142 void Andersens::PrintConstraints() { 01143 std::cerr << "Constraints:\n"; 01144 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01145 std::cerr << " #" << i << ": "; 01146 Constraint &C = Constraints[i]; 01147 if (C.Type == Constraint::Store) 01148 std::cerr << "*"; 01149 PrintNode(C.Dest); 01150 std::cerr << " = "; 01151 if (C.Type == Constraint::Load) 01152 std::cerr << "*"; 01153 PrintNode(C.Src); 01154 std::cerr << "\n"; 01155 } 01156 } 01157 01158 void Andersens::PrintPointsToGraph() { 01159 std::cerr << "Points-to graph:\n"; 01160 for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) { 01161 Node *N = &GraphNodes[i]; 01162 std::cerr << "[" << (N->end() - N->begin()) << "] "; 01163 PrintNode(N); 01164 std::cerr << "\t--> "; 01165 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) { 01166 if (I != N->begin()) std::cerr << ", "; 01167 PrintNode(*I); 01168 } 01169 std::cerr << "\n"; 01170 } 01171 }