LLVM API Documentation
00001 //===- Local.cpp - Compute a local data structure graph for a function ----===// 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 // Compute the local version of the data structure graph for a function. The 00011 // external interface to this file is the DSGraph constructor. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Analysis/DataStructure/DataStructure.h" 00016 #include "llvm/Analysis/DataStructure/DSGraph.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/DerivedTypes.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Intrinsics.h" 00021 #include "llvm/Support/GetElementPtrTypeIterator.h" 00022 #include "llvm/Support/InstVisitor.h" 00023 #include "llvm/Target/TargetData.h" 00024 #include "llvm/Support/CommandLine.h" 00025 #include "llvm/Support/Debug.h" 00026 #include "llvm/Support/Timer.h" 00027 #include <iostream> 00028 00029 // FIXME: This should eventually be a FunctionPass that is automatically 00030 // aggregated into a Pass. 00031 // 00032 #include "llvm/Module.h" 00033 00034 using namespace llvm; 00035 00036 static RegisterAnalysis<LocalDataStructures> 00037 X("datastructure", "Local Data Structure Analysis"); 00038 00039 static cl::opt<bool> 00040 TrackIntegersAsPointers("dsa-track-integers", cl::Hidden, 00041 cl::desc("If this is set, track integers as potential pointers")); 00042 00043 static cl::list<std::string> 00044 AllocList("dsa-alloc-list", 00045 cl::value_desc("list"), 00046 cl::desc("List of functions that allocate memory from the heap"), 00047 cl::CommaSeparated, cl::Hidden); 00048 00049 static cl::list<std::string> 00050 FreeList("dsa-free-list", 00051 cl::value_desc("list"), 00052 cl::desc("List of functions that free memory from the heap"), 00053 cl::CommaSeparated, cl::Hidden); 00054 00055 namespace llvm { 00056 namespace DS { 00057 // isPointerType - Return true if this type is big enough to hold a pointer. 00058 bool isPointerType(const Type *Ty) { 00059 if (isa<PointerType>(Ty)) 00060 return true; 00061 else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger()) 00062 return Ty->getPrimitiveSize() >= PointerSize; 00063 return false; 00064 } 00065 }} 00066 00067 using namespace DS; 00068 00069 namespace { 00070 cl::opt<bool> 00071 DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden, 00072 cl::desc("Disable direct call optimization in " 00073 "DSGraph construction")); 00074 cl::opt<bool> 00075 DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden, 00076 cl::desc("Disable field sensitivity in DSGraphs")); 00077 00078 //===--------------------------------------------------------------------===// 00079 // GraphBuilder Class 00080 //===--------------------------------------------------------------------===// 00081 // 00082 /// This class is the builder class that constructs the local data structure 00083 /// graph by performing a single pass over the function in question. 00084 /// 00085 class GraphBuilder : InstVisitor<GraphBuilder> { 00086 DSGraph &G; 00087 DSNodeHandle *RetNode; // Node that gets returned... 00088 DSScalarMap &ScalarMap; 00089 std::list<DSCallSite> *FunctionCalls; 00090 00091 public: 00092 GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode, 00093 std::list<DSCallSite> &fc) 00094 : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()), 00095 FunctionCalls(&fc) { 00096 00097 // Create scalar nodes for all pointer arguments... 00098 for (Function::arg_iterator I = f.arg_begin(), E = f.arg_end(); 00099 I != E; ++I) 00100 if (isPointerType(I->getType())) 00101 getValueDest(*I); 00102 00103 visit(f); // Single pass over the function 00104 } 00105 00106 // GraphBuilder ctor for working on the globals graph 00107 GraphBuilder(DSGraph &g) 00108 : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) { 00109 } 00110 00111 void mergeInGlobalInitializer(GlobalVariable *GV); 00112 00113 private: 00114 // Visitor functions, used to handle each instruction type we encounter... 00115 friend class InstVisitor<GraphBuilder>; 00116 void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); } 00117 void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); } 00118 void handleAlloc(AllocationInst &AI, bool isHeap); 00119 00120 void visitPHINode(PHINode &PN); 00121 void visitSelectInst(SelectInst &SI); 00122 00123 void visitGetElementPtrInst(User &GEP); 00124 void visitReturnInst(ReturnInst &RI); 00125 void visitLoadInst(LoadInst &LI); 00126 void visitStoreInst(StoreInst &SI); 00127 void visitCallInst(CallInst &CI); 00128 void visitInvokeInst(InvokeInst &II); 00129 void visitSetCondInst(SetCondInst &SCI); 00130 void visitFreeInst(FreeInst &FI); 00131 void visitCastInst(CastInst &CI); 00132 void visitInstruction(Instruction &I); 00133 00134 void visitCallSite(CallSite CS); 00135 void visitVAArgInst(VAArgInst &I); 00136 00137 void MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C); 00138 private: 00139 // Helper functions used to implement the visitation functions... 00140 00141 /// createNode - Create a new DSNode, ensuring that it is properly added to 00142 /// the graph. 00143 /// 00144 DSNode *createNode(const Type *Ty = 0) { 00145 DSNode *N = new DSNode(Ty, &G); // Create the node 00146 if (DisableFieldSensitivity) { 00147 // Create node handle referring to the old node so that it is 00148 // immediately removed from the graph when the node handle is destroyed. 00149 DSNodeHandle OldNNH = N; 00150 N->foldNodeCompletely(); 00151 if (DSNode *FN = N->getForwardNode()) 00152 N = FN; 00153 } 00154 return N; 00155 } 00156 00157 /// setDestTo - Set the ScalarMap entry for the specified value to point to 00158 /// the specified destination. If the Value already points to a node, make 00159 /// sure to merge the two destinations together. 00160 /// 00161 void setDestTo(Value &V, const DSNodeHandle &NH); 00162 00163 /// getValueDest - Return the DSNode that the actual value points to. 00164 /// 00165 DSNodeHandle getValueDest(Value &V); 00166 00167 /// getLink - This method is used to return the specified link in the 00168 /// specified node if one exists. If a link does not already exist (it's 00169 /// null), then we create a new node, link it, then return it. 00170 /// 00171 DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0); 00172 }; 00173 } 00174 00175 using namespace DS; 00176 00177 //===----------------------------------------------------------------------===// 00178 // DSGraph constructor - Simply use the GraphBuilder to construct the local 00179 // graph. 00180 DSGraph::DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td, 00181 Function &F, DSGraph *GG) 00182 : GlobalsGraph(GG), ScalarMap(ECs), TD(td) { 00183 PrintAuxCalls = false; 00184 00185 DEBUG(std::cerr << " [Loc] Calculating graph for: " << F.getName() << "\n"); 00186 00187 // Use the graph builder to construct the local version of the graph 00188 GraphBuilder B(F, *this, ReturnNodes[&F], FunctionCalls); 00189 #ifndef NDEBUG 00190 Timer::addPeakMemoryMeasurement(); 00191 #endif 00192 00193 // If there are any constant globals referenced in this function, merge their 00194 // initializers into the local graph from the globals graph. 00195 if (ScalarMap.global_begin() != ScalarMap.global_end()) { 00196 ReachabilityCloner RC(*this, *GG, 0); 00197 00198 for (DSScalarMap::global_iterator I = ScalarMap.global_begin(); 00199 I != ScalarMap.global_end(); ++I) 00200 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) 00201 if (!GV->isExternal() && GV->isConstant()) 00202 RC.merge(ScalarMap[GV], GG->ScalarMap[GV]); 00203 } 00204 00205 markIncompleteNodes(DSGraph::MarkFormalArgs); 00206 00207 // Remove any nodes made dead due to merging... 00208 removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00209 } 00210 00211 00212 //===----------------------------------------------------------------------===// 00213 // Helper method implementations... 00214 // 00215 00216 /// getValueDest - Return the DSNode that the actual value points to. 00217 /// 00218 DSNodeHandle GraphBuilder::getValueDest(Value &Val) { 00219 Value *V = &Val; 00220 if (isa<Constant>(V) && cast<Constant>(V)->isNullValue()) 00221 return 0; // Null doesn't point to anything, don't add to ScalarMap! 00222 00223 DSNodeHandle &NH = ScalarMap[V]; 00224 if (!NH.isNull()) 00225 return NH; // Already have a node? Just return it... 00226 00227 // Otherwise we need to create a new node to point to. 00228 // Check first for constant expressions that must be traversed to 00229 // extract the actual value. 00230 DSNode* N; 00231 if (GlobalValue* GV = dyn_cast<GlobalValue>(V)) { 00232 // Create a new global node for this global variable. 00233 N = createNode(GV->getType()->getElementType()); 00234 N->addGlobal(GV); 00235 } else if (Constant *C = dyn_cast<Constant>(V)) { 00236 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00237 if (CE->getOpcode() == Instruction::Cast) { 00238 if (isa<PointerType>(CE->getOperand(0)->getType())) 00239 NH = getValueDest(*CE->getOperand(0)); 00240 else 00241 NH = createNode()->setUnknownNodeMarker(); 00242 } else if (CE->getOpcode() == Instruction::GetElementPtr) { 00243 visitGetElementPtrInst(*CE); 00244 DSScalarMap::iterator I = ScalarMap.find(CE); 00245 assert(I != ScalarMap.end() && "GEP didn't get processed right?"); 00246 NH = I->second; 00247 } else { 00248 // This returns a conservative unknown node for any unhandled ConstExpr 00249 return NH = createNode()->setUnknownNodeMarker(); 00250 } 00251 if (NH.isNull()) { // (getelementptr null, X) returns null 00252 ScalarMap.erase(V); 00253 return 0; 00254 } 00255 return NH; 00256 } else if (isa<UndefValue>(C)) { 00257 ScalarMap.erase(V); 00258 return 0; 00259 } else { 00260 assert(0 && "Unknown constant type!"); 00261 } 00262 N = createNode(); // just create a shadow node 00263 } else { 00264 // Otherwise just create a shadow node 00265 N = createNode(); 00266 } 00267 00268 NH.setTo(N, 0); // Remember that we are pointing to it... 00269 return NH; 00270 } 00271 00272 00273 /// getLink - This method is used to return the specified link in the 00274 /// specified node if one exists. If a link does not already exist (it's 00275 /// null), then we create a new node, link it, then return it. We must 00276 /// specify the type of the Node field we are accessing so that we know what 00277 /// type should be linked to if we need to create a new node. 00278 /// 00279 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) { 00280 DSNodeHandle &Node = const_cast<DSNodeHandle&>(node); 00281 DSNodeHandle &Link = Node.getLink(LinkNo); 00282 if (Link.isNull()) { 00283 // If the link hasn't been created yet, make and return a new shadow node 00284 Link = createNode(); 00285 } 00286 return Link; 00287 } 00288 00289 00290 /// setDestTo - Set the ScalarMap entry for the specified value to point to the 00291 /// specified destination. If the Value already points to a node, make sure to 00292 /// merge the two destinations together. 00293 /// 00294 void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) { 00295 ScalarMap[&V].mergeWith(NH); 00296 } 00297 00298 00299 //===----------------------------------------------------------------------===// 00300 // Specific instruction type handler implementations... 00301 // 00302 00303 /// Alloca & Malloc instruction implementation - Simply create a new memory 00304 /// object, pointing the scalar to it. 00305 /// 00306 void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) { 00307 DSNode *N = createNode(); 00308 if (isHeap) 00309 N->setHeapNodeMarker(); 00310 else 00311 N->setAllocaNodeMarker(); 00312 setDestTo(AI, N); 00313 } 00314 00315 // PHINode - Make the scalar for the PHI node point to all of the things the 00316 // incoming values point to... which effectively causes them to be merged. 00317 // 00318 void GraphBuilder::visitPHINode(PHINode &PN) { 00319 if (!isPointerType(PN.getType())) return; // Only pointer PHIs 00320 00321 DSNodeHandle &PNDest = ScalarMap[&PN]; 00322 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 00323 PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i))); 00324 } 00325 00326 void GraphBuilder::visitSelectInst(SelectInst &SI) { 00327 if (!isPointerType(SI.getType())) return; // Only pointer Selects 00328 00329 DSNodeHandle &Dest = ScalarMap[&SI]; 00330 Dest.mergeWith(getValueDest(*SI.getOperand(1))); 00331 Dest.mergeWith(getValueDest(*SI.getOperand(2))); 00332 } 00333 00334 void GraphBuilder::visitSetCondInst(SetCondInst &SCI) { 00335 if (!isPointerType(SCI.getOperand(0)->getType()) || 00336 isa<ConstantPointerNull>(SCI.getOperand(1))) return; // Only pointers 00337 ScalarMap[SCI.getOperand(0)].mergeWith(getValueDest(*SCI.getOperand(1))); 00338 } 00339 00340 00341 void GraphBuilder::visitGetElementPtrInst(User &GEP) { 00342 DSNodeHandle Value = getValueDest(*GEP.getOperand(0)); 00343 if (Value.isNull()) 00344 Value = createNode(); 00345 00346 // As a special case, if all of the index operands of GEP are constant zeros, 00347 // handle this just like we handle casts (ie, don't do much). 00348 bool AllZeros = true; 00349 for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) 00350 if (GEP.getOperand(i) != 00351 Constant::getNullValue(GEP.getOperand(i)->getType())) { 00352 AllZeros = false; 00353 break; 00354 } 00355 00356 // If all of the indices are zero, the result points to the operand without 00357 // applying the type. 00358 if (AllZeros || (!Value.isNull() && 00359 Value.getNode()->isNodeCompletelyFolded())) { 00360 setDestTo(GEP, Value); 00361 return; 00362 } 00363 00364 00365 const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType()); 00366 const Type *CurTy = PTy->getElementType(); 00367 00368 if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) { 00369 // If the node had to be folded... exit quickly 00370 setDestTo(GEP, Value); // GEP result points to folded node 00371 return; 00372 } 00373 00374 const TargetData &TD = Value.getNode()->getTargetData(); 00375 00376 #if 0 00377 // Handle the pointer index specially... 00378 if (GEP.getNumOperands() > 1 && 00379 (!isa<Constant>(GEP.getOperand(1)) || 00380 !cast<Constant>(GEP.getOperand(1))->isNullValue())) { 00381 00382 // If we already know this is an array being accessed, don't do anything... 00383 if (!TopTypeRec.isArray) { 00384 TopTypeRec.isArray = true; 00385 00386 // If we are treating some inner field pointer as an array, fold the node 00387 // up because we cannot handle it right. This can come because of 00388 // something like this: &((&Pt->X)[1]) == &Pt->Y 00389 // 00390 if (Value.getOffset()) { 00391 // Value is now the pointer we want to GEP to be... 00392 Value.getNode()->foldNodeCompletely(); 00393 setDestTo(GEP, Value); // GEP result points to folded node 00394 return; 00395 } else { 00396 // This is a pointer to the first byte of the node. Make sure that we 00397 // are pointing to the outter most type in the node. 00398 // FIXME: We need to check one more case here... 00399 } 00400 } 00401 } 00402 #endif 00403 00404 // All of these subscripts are indexing INTO the elements we have... 00405 unsigned Offset = 0; 00406 for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP); 00407 I != E; ++I) 00408 if (const StructType *STy = dyn_cast<StructType>(*I)) { 00409 unsigned FieldNo = 00410 (unsigned)cast<ConstantUInt>(I.getOperand())->getValue(); 00411 Offset += (unsigned)TD.getStructLayout(STy)->MemberOffsets[FieldNo]; 00412 } else if (const PointerType *PTy = dyn_cast<PointerType>(*I)) { 00413 if (!isa<Constant>(I.getOperand()) || 00414 !cast<Constant>(I.getOperand())->isNullValue()) 00415 Value.getNode()->setArrayMarker(); 00416 } 00417 00418 00419 #if 0 00420 if (const SequentialType *STy = cast<SequentialType>(*I)) { 00421 CurTy = STy->getElementType(); 00422 if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) { 00423 Offset += CS->getValue()*TD.getTypeSize(CurTy); 00424 } else { 00425 // Variable index into a node. We must merge all of the elements of the 00426 // sequential type here. 00427 if (isa<PointerType>(STy)) 00428 std::cerr << "Pointer indexing not handled yet!\n"; 00429 else { 00430 const ArrayType *ATy = cast<ArrayType>(STy); 00431 unsigned ElSize = TD.getTypeSize(CurTy); 00432 DSNode *N = Value.getNode(); 00433 assert(N && "Value must have a node!"); 00434 unsigned RawOffset = Offset+Value.getOffset(); 00435 00436 // Loop over all of the elements of the array, merging them into the 00437 // zeroth element. 00438 for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i) 00439 // Merge all of the byte components of this array element 00440 for (unsigned j = 0; j != ElSize; ++j) 00441 N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j); 00442 } 00443 } 00444 } 00445 #endif 00446 00447 // Add in the offset calculated... 00448 Value.setOffset(Value.getOffset()+Offset); 00449 00450 // Check the offset 00451 DSNode *N = Value.getNode(); 00452 if (N && 00453 !N->isNodeCompletelyFolded() && 00454 (N->getSize() != 0 || Offset != 0) && 00455 !N->isForwarding()) { 00456 if ((Offset >= N->getSize()) || int(Offset) < 0) { 00457 // Accessing offsets out of node size range 00458 // This is seen in the "magic" struct in named (from bind), where the 00459 // fourth field is an array of length 0, presumably used to create struct 00460 // instances of different sizes 00461 00462 // Collapse the node since its size is now variable 00463 N->foldNodeCompletely(); 00464 } 00465 } 00466 00467 // Value is now the pointer we want to GEP to be... 00468 setDestTo(GEP, Value); 00469 } 00470 00471 void GraphBuilder::visitLoadInst(LoadInst &LI) { 00472 DSNodeHandle Ptr = getValueDest(*LI.getOperand(0)); 00473 if (Ptr.isNull()) 00474 Ptr = createNode(); 00475 00476 // Make that the node is read from... 00477 Ptr.getNode()->setReadMarker(); 00478 00479 // Ensure a typerecord exists... 00480 Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false); 00481 00482 if (isPointerType(LI.getType())) 00483 setDestTo(LI, getLink(Ptr)); 00484 } 00485 00486 void GraphBuilder::visitStoreInst(StoreInst &SI) { 00487 const Type *StoredTy = SI.getOperand(0)->getType(); 00488 DSNodeHandle Dest = getValueDest(*SI.getOperand(1)); 00489 if (Dest.isNull()) return; 00490 00491 // Mark that the node is written to... 00492 Dest.getNode()->setModifiedMarker(); 00493 00494 // Ensure a type-record exists... 00495 Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset()); 00496 00497 // Avoid adding edges from null, or processing non-"pointer" stores 00498 if (isPointerType(StoredTy)) 00499 Dest.addEdgeTo(getValueDest(*SI.getOperand(0))); 00500 } 00501 00502 void GraphBuilder::visitReturnInst(ReturnInst &RI) { 00503 if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType())) 00504 RetNode->mergeWith(getValueDest(*RI.getOperand(0))); 00505 } 00506 00507 void GraphBuilder::visitVAArgInst(VAArgInst &I) { 00508 //FIXME: also updates the argument 00509 DSNodeHandle Ptr = getValueDest(*I.getOperand(0)); 00510 if (Ptr.isNull()) return; 00511 00512 // Make that the node is read from. 00513 Ptr.getNode()->setReadMarker(); 00514 00515 // Ensure a type record exists. 00516 DSNode *PtrN = Ptr.getNode(); 00517 PtrN->mergeTypeInfo(I.getType(), Ptr.getOffset(), false); 00518 00519 if (isPointerType(I.getType())) 00520 setDestTo(I, getLink(Ptr)); 00521 } 00522 00523 00524 void GraphBuilder::visitCallInst(CallInst &CI) { 00525 visitCallSite(&CI); 00526 } 00527 00528 void GraphBuilder::visitInvokeInst(InvokeInst &II) { 00529 visitCallSite(&II); 00530 } 00531 00532 void GraphBuilder::visitCallSite(CallSite CS) { 00533 Value *Callee = CS.getCalledValue(); 00534 00535 // Special case handling of certain libc allocation functions here. 00536 if (Function *F = dyn_cast<Function>(Callee)) 00537 if (F->isExternal()) 00538 switch (F->getIntrinsicID()) { 00539 case Intrinsic::vastart: 00540 getValueDest(*CS.getInstruction()).getNode()->setAllocaNodeMarker(); 00541 return; 00542 case Intrinsic::vacopy: 00543 getValueDest(*CS.getInstruction()). 00544 mergeWith(getValueDest(**(CS.arg_begin()))); 00545 return; 00546 case Intrinsic::vaend: 00547 return; // noop 00548 case Intrinsic::memcpy_i32: 00549 case Intrinsic::memcpy_i64: 00550 case Intrinsic::memmove_i32: 00551 case Intrinsic::memmove_i64: { 00552 //This is over aggressive. What these functions do is not make the 00553 // targets pointers alias, but rather merge the out edges of the graphs 00554 // for the pointers according to the type merging of the graphs. 00555 //Simply merging the two graphs is a crude approximation to this. 00556 //I might be wrong though. 00557 00558 // Merge the first & second arguments, and mark the memory read and 00559 // modified. 00560 DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); 00561 RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); 00562 if (DSNode *N = RetNH.getNode()) 00563 N->setModifiedMarker()->setReadMarker(); 00564 return; 00565 } 00566 case Intrinsic::memset_i32: 00567 case Intrinsic::memset_i64: 00568 // Mark the memory modified. 00569 if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) 00570 N->setModifiedMarker(); 00571 return; 00572 default: 00573 // Determine if the called function is one of the specified heap 00574 // allocation functions 00575 for (cl::list<std::string>::iterator AllocFunc = AllocList.begin(), 00576 LastAllocFunc = AllocList.end(); 00577 AllocFunc != LastAllocFunc; 00578 ++AllocFunc) { 00579 if (F->getName() == *(AllocFunc)) { 00580 setDestTo(*CS.getInstruction(), 00581 createNode()->setHeapNodeMarker()->setModifiedMarker()); 00582 return; 00583 } 00584 } 00585 00586 // Determine if the called function is one of the specified heap 00587 // free functions 00588 for (cl::list<std::string>::iterator FreeFunc = FreeList.begin(), 00589 LastFreeFunc = FreeList.end(); 00590 FreeFunc != LastFreeFunc; 00591 ++FreeFunc) { 00592 if (F->getName() == *(FreeFunc)) { 00593 // Mark that the node is written to... 00594 if (DSNode *N = getValueDest(*(CS.getArgument(0))).getNode()) 00595 N->setModifiedMarker()->setHeapNodeMarker(); 00596 return; 00597 } 00598 } 00599 00600 if (F->getName() == "calloc" || F->getName() == "posix_memalign" || 00601 F->getName() == "memalign" || F->getName() == "valloc") { 00602 setDestTo(*CS.getInstruction(), 00603 createNode()->setHeapNodeMarker()->setModifiedMarker()); 00604 return; 00605 } else if (F->getName() == "realloc") { 00606 DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); 00607 if (CS.arg_begin() != CS.arg_end()) 00608 RetNH.mergeWith(getValueDest(**CS.arg_begin())); 00609 if (DSNode *N = RetNH.getNode()) 00610 N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); 00611 return; 00612 } else if (F->getName() == "memmove") { 00613 // Merge the first & second arguments, and mark the memory read and 00614 // modified. 00615 DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); 00616 RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); 00617 if (DSNode *N = RetNH.getNode()) 00618 N->setModifiedMarker()->setReadMarker(); 00619 return; 00620 00621 } else if (F->getName() == "atoi" || F->getName() == "atof" || 00622 F->getName() == "atol" || F->getName() == "atoll" || 00623 F->getName() == "remove" || F->getName() == "unlink" || 00624 F->getName() == "rename" || F->getName() == "memcmp" || 00625 F->getName() == "strcmp" || F->getName() == "strncmp" || 00626 F->getName() == "execl" || F->getName() == "execlp" || 00627 F->getName() == "execle" || F->getName() == "execv" || 00628 F->getName() == "execvp" || F->getName() == "chmod" || 00629 F->getName() == "puts" || F->getName() == "write" || 00630 F->getName() == "open" || F->getName() == "create" || 00631 F->getName() == "truncate" || F->getName() == "chdir" || 00632 F->getName() == "mkdir" || F->getName() == "rmdir") { 00633 // These functions read all of their pointer operands. 00634 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00635 AI != E; ++AI) { 00636 if (isPointerType((*AI)->getType())) 00637 if (DSNode *N = getValueDest(**AI).getNode()) 00638 N->setReadMarker(); 00639 } 00640 return; 00641 } else if (F->getName() == "read" || F->getName() == "pipe" || 00642 F->getName() == "wait" || F->getName() == "time") { 00643 // These functions write all of their pointer operands. 00644 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00645 AI != E; ++AI) { 00646 if (isPointerType((*AI)->getType())) 00647 if (DSNode *N = getValueDest(**AI).getNode()) 00648 N->setModifiedMarker(); 00649 } 00650 return; 00651 } else if (F->getName() == "stat" || F->getName() == "fstat" || 00652 F->getName() == "lstat") { 00653 // These functions read their first operand if its a pointer. 00654 CallSite::arg_iterator AI = CS.arg_begin(); 00655 if (isPointerType((*AI)->getType())) { 00656 DSNodeHandle Path = getValueDest(**AI); 00657 if (DSNode *N = Path.getNode()) N->setReadMarker(); 00658 } 00659 00660 // Then they write into the stat buffer. 00661 DSNodeHandle StatBuf = getValueDest(**++AI); 00662 if (DSNode *N = StatBuf.getNode()) { 00663 N->setModifiedMarker(); 00664 const Type *StatTy = F->getFunctionType()->getParamType(1); 00665 if (const PointerType *PTy = dyn_cast<PointerType>(StatTy)) 00666 N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset()); 00667 } 00668 return; 00669 } else if (F->getName() == "strtod" || F->getName() == "strtof" || 00670 F->getName() == "strtold") { 00671 // These functions read the first pointer 00672 if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) { 00673 Str->setReadMarker(); 00674 // If the second parameter is passed, it will point to the first 00675 // argument node. 00676 const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1)); 00677 if (DSNode *End = EndPtrNH.getNode()) { 00678 End->mergeTypeInfo(PointerType::get(Type::SByteTy), 00679 EndPtrNH.getOffset(), false); 00680 End->setModifiedMarker(); 00681 DSNodeHandle &Link = getLink(EndPtrNH); 00682 Link.mergeWith(getValueDest(**CS.arg_begin())); 00683 } 00684 } 00685 return; 00686 } else if (F->getName() == "fopen" || F->getName() == "fdopen" || 00687 F->getName() == "freopen") { 00688 // These functions read all of their pointer operands. 00689 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00690 AI != E; ++AI) 00691 if (isPointerType((*AI)->getType())) 00692 if (DSNode *N = getValueDest(**AI).getNode()) 00693 N->setReadMarker(); 00694 00695 // fopen allocates in an unknown way and writes to the file 00696 // descriptor. Also, merge the allocated type into the node. 00697 DSNodeHandle Result = getValueDest(*CS.getInstruction()); 00698 if (DSNode *N = Result.getNode()) { 00699 N->setModifiedMarker()->setUnknownNodeMarker(); 00700 const Type *RetTy = F->getFunctionType()->getReturnType(); 00701 if (const PointerType *PTy = dyn_cast<PointerType>(RetTy)) 00702 N->mergeTypeInfo(PTy->getElementType(), Result.getOffset()); 00703 } 00704 00705 // If this is freopen, merge the file descriptor passed in with the 00706 // result. 00707 if (F->getName() == "freopen") { 00708 // ICC doesn't handle getting the iterator, decrementing and 00709 // dereferencing it in one operation without error. Do it in 2 steps 00710 CallSite::arg_iterator compit = CS.arg_end(); 00711 Result.mergeWith(getValueDest(**--compit)); 00712 } 00713 return; 00714 } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){ 00715 // fclose reads and deallocates the memory in an unknown way for the 00716 // file descriptor. It merges the FILE type into the descriptor. 00717 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00718 if (DSNode *N = H.getNode()) { 00719 N->setReadMarker()->setUnknownNodeMarker(); 00720 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00721 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00722 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00723 } 00724 return; 00725 } else if (CS.arg_end()-CS.arg_begin() == 1 && 00726 (F->getName() == "fflush" || F->getName() == "feof" || 00727 F->getName() == "fileno" || F->getName() == "clearerr" || 00728 F->getName() == "rewind" || F->getName() == "ftell" || 00729 F->getName() == "ferror" || F->getName() == "fgetc" || 00730 F->getName() == "fgetc" || F->getName() == "_IO_getc")) { 00731 // fflush reads and writes the memory for the file descriptor. It 00732 // merges the FILE type into the descriptor. 00733 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00734 if (DSNode *N = H.getNode()) { 00735 N->setReadMarker()->setModifiedMarker(); 00736 00737 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00738 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00739 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00740 } 00741 return; 00742 } else if (CS.arg_end()-CS.arg_begin() == 4 && 00743 (F->getName() == "fwrite" || F->getName() == "fread")) { 00744 // fread writes the first operand, fwrite reads it. They both 00745 // read/write the FILE descriptor, and merges the FILE type. 00746 CallSite::arg_iterator compit = CS.arg_end(); 00747 DSNodeHandle H = getValueDest(**--compit); 00748 if (DSNode *N = H.getNode()) { 00749 N->setReadMarker()->setModifiedMarker(); 00750 const Type *ArgTy = F->getFunctionType()->getParamType(3); 00751 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00752 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00753 } 00754 00755 H = getValueDest(**CS.arg_begin()); 00756 if (DSNode *N = H.getNode()) 00757 if (F->getName() == "fwrite") 00758 N->setReadMarker(); 00759 else 00760 N->setModifiedMarker(); 00761 return; 00762 } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){ 00763 // fgets reads and writes the memory for the file descriptor. It 00764 // merges the FILE type into the descriptor, and writes to the 00765 // argument. It returns the argument as well. 00766 CallSite::arg_iterator AI = CS.arg_begin(); 00767 DSNodeHandle H = getValueDest(**AI); 00768 if (DSNode *N = H.getNode()) 00769 N->setModifiedMarker(); // Writes buffer 00770 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00771 ++AI; ++AI; 00772 00773 // Reads and writes file descriptor, merge in FILE type. 00774 H = getValueDest(**AI); 00775 if (DSNode *N = H.getNode()) { 00776 N->setReadMarker()->setModifiedMarker(); 00777 const Type *ArgTy = F->getFunctionType()->getParamType(2); 00778 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00779 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00780 } 00781 return; 00782 } else if (F->getName() == "ungetc" || F->getName() == "fputc" || 00783 F->getName() == "fputs" || F->getName() == "putc" || 00784 F->getName() == "ftell" || F->getName() == "rewind" || 00785 F->getName() == "_IO_putc") { 00786 // These functions read and write the memory for the file descriptor, 00787 // which is passes as the last argument. 00788 CallSite::arg_iterator compit = CS.arg_end(); 00789 DSNodeHandle H = getValueDest(**--compit); 00790 if (DSNode *N = H.getNode()) { 00791 N->setReadMarker()->setModifiedMarker(); 00792 FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); 00793 const Type *ArgTy = *--compit2; 00794 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00795 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00796 } 00797 00798 // Any pointer arguments are read. 00799 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00800 AI != E; ++AI) 00801 if (isPointerType((*AI)->getType())) 00802 if (DSNode *N = getValueDest(**AI).getNode()) 00803 N->setReadMarker(); 00804 return; 00805 } else if (F->getName() == "fseek" || F->getName() == "fgetpos" || 00806 F->getName() == "fsetpos") { 00807 // These functions read and write the memory for the file descriptor, 00808 // and read/write all other arguments. 00809 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00810 if (DSNode *N = H.getNode()) { 00811 FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); 00812 const Type *ArgTy = *--compit2; 00813 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00814 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00815 } 00816 00817 // Any pointer arguments are read. 00818 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00819 AI != E; ++AI) 00820 if (isPointerType((*AI)->getType())) 00821 if (DSNode *N = getValueDest(**AI).getNode()) 00822 N->setReadMarker()->setModifiedMarker(); 00823 return; 00824 } else if (F->getName() == "printf" || F->getName() == "fprintf" || 00825 F->getName() == "sprintf") { 00826 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00827 00828 if (F->getName() == "fprintf") { 00829 // fprintf reads and writes the FILE argument, and applies the type 00830 // to it. 00831 DSNodeHandle H = getValueDest(**AI); 00832 if (DSNode *N = H.getNode()) { 00833 N->setModifiedMarker(); 00834 const Type *ArgTy = (*AI)->getType(); 00835 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00836 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00837 } 00838 } else if (F->getName() == "sprintf") { 00839 // sprintf writes the first string argument. 00840 DSNodeHandle H = getValueDest(**AI++); 00841 if (DSNode *N = H.getNode()) { 00842 N->setModifiedMarker(); 00843 const Type *ArgTy = (*AI)->getType(); 00844 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00845 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00846 } 00847 } 00848 00849 for (; AI != E; ++AI) { 00850 // printf reads all pointer arguments. 00851 if (isPointerType((*AI)->getType())) 00852 if (DSNode *N = getValueDest(**AI).getNode()) 00853 N->setReadMarker(); 00854 } 00855 return; 00856 } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" || 00857 F->getName() == "vsprintf") { 00858 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00859 00860 if (F->getName() == "vfprintf") { 00861 // ffprintf reads and writes the FILE argument, and applies the type 00862 // to it. 00863 DSNodeHandle H = getValueDest(**AI); 00864 if (DSNode *N = H.getNode()) { 00865 N->setModifiedMarker()->setReadMarker(); 00866 const Type *ArgTy = (*AI)->getType(); 00867 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00868 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00869 } 00870 ++AI; 00871 } else if (F->getName() == "vsprintf") { 00872 // vsprintf writes the first string argument. 00873 DSNodeHandle H = getValueDest(**AI++); 00874 if (DSNode *N = H.getNode()) { 00875 N->setModifiedMarker(); 00876 const Type *ArgTy = (*AI)->getType(); 00877 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00878 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00879 } 00880 } 00881 00882 // Read the format 00883 if (AI != E) { 00884 if (isPointerType((*AI)->getType())) 00885 if (DSNode *N = getValueDest(**AI).getNode()) 00886 N->setReadMarker(); 00887 ++AI; 00888 } 00889 00890 // Read the valist, and the pointed-to objects. 00891 if (AI != E && isPointerType((*AI)->getType())) { 00892 const DSNodeHandle &VAList = getValueDest(**AI); 00893 if (DSNode *N = VAList.getNode()) { 00894 N->setReadMarker(); 00895 N->mergeTypeInfo(PointerType::get(Type::SByteTy), 00896 VAList.getOffset(), false); 00897 00898 DSNodeHandle &VAListObjs = getLink(VAList); 00899 VAListObjs.getNode()->setReadMarker(); 00900 } 00901 } 00902 00903 return; 00904 } else if (F->getName() == "scanf" || F->getName() == "fscanf" || 00905 F->getName() == "sscanf") { 00906 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00907 00908 if (F->getName() == "fscanf") { 00909 // fscanf reads and writes the FILE argument, and applies the type 00910 // to it. 00911 DSNodeHandle H = getValueDest(**AI); 00912 if (DSNode *N = H.getNode()) { 00913 N->setReadMarker(); 00914 const Type *ArgTy = (*AI)->getType(); 00915 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00916 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00917 } 00918 } else if (F->getName() == "sscanf") { 00919 // sscanf reads the first string argument. 00920 DSNodeHandle H = getValueDest(**AI++); 00921 if (DSNode *N = H.getNode()) { 00922 N->setReadMarker(); 00923 const Type *ArgTy = (*AI)->getType(); 00924 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00925 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00926 } 00927 } 00928 00929 for (; AI != E; ++AI) { 00930 // scanf writes all pointer arguments. 00931 if (isPointerType((*AI)->getType())) 00932 if (DSNode *N = getValueDest(**AI).getNode()) 00933 N->setModifiedMarker(); 00934 } 00935 return; 00936 } else if (F->getName() == "strtok") { 00937 // strtok reads and writes the first argument, returning it. It reads 00938 // its second arg. FIXME: strtok also modifies some hidden static 00939 // data. Someday this might matter. 00940 CallSite::arg_iterator AI = CS.arg_begin(); 00941 DSNodeHandle H = getValueDest(**AI++); 00942 if (DSNode *N = H.getNode()) { 00943 N->setReadMarker()->setModifiedMarker(); // Reads/Writes buffer 00944 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00945 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00946 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00947 } 00948 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00949 00950 H = getValueDest(**AI); // Reads delimiter 00951 if (DSNode *N = H.getNode()) { 00952 N->setReadMarker(); 00953 const Type *ArgTy = F->getFunctionType()->getParamType(1); 00954 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00955 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00956 } 00957 return; 00958 } else if (F->getName() == "strchr" || F->getName() == "strrchr" || 00959 F->getName() == "strstr") { 00960 // These read their arguments, and return the first one 00961 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00962 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00963 00964 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00965 AI != E; ++AI) 00966 if (isPointerType((*AI)->getType())) 00967 if (DSNode *N = getValueDest(**AI).getNode()) 00968 N->setReadMarker(); 00969 00970 if (DSNode *N = H.getNode()) 00971 N->setReadMarker(); 00972 return; 00973 } else if (F->getName() == "__assert_fail") { 00974 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00975 AI != E; ++AI) 00976 if (isPointerType((*AI)->getType())) 00977 if (DSNode *N = getValueDest(**AI).getNode()) 00978 N->setReadMarker(); 00979 return; 00980 } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) { 00981 // This writes its second argument, and forces it to double. 00982 CallSite::arg_iterator compit = CS.arg_end(); 00983 DSNodeHandle H = getValueDest(**--compit); 00984 if (DSNode *N = H.getNode()) { 00985 N->setModifiedMarker(); 00986 N->mergeTypeInfo(Type::DoubleTy, H.getOffset()); 00987 } 00988 return; 00989 } else if (F->getName() == "strcat" || F->getName() == "strncat") { 00990 //This might be making unsafe assumptions about usage 00991 //Merge return and first arg 00992 DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); 00993 RetNH.mergeWith(getValueDest(**CS.arg_begin())); 00994 if (DSNode *N = RetNH.getNode()) 00995 N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); 00996 //and read second pointer 00997 if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) 00998 N->setReadMarker(); 00999 return; 01000 } else { 01001 // Unknown function, warn if it returns a pointer type or takes a 01002 // pointer argument. 01003 bool Warn = isPointerType(CS.getInstruction()->getType()); 01004 if (!Warn) 01005 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 01006 I != E; ++I) 01007 if (isPointerType((*I)->getType())) { 01008 Warn = true; 01009 break; 01010 } 01011 if (Warn) 01012 std::cerr << "WARNING: Call to unknown external function '" 01013 << F->getName() << "' will cause pessimistic results!\n"; 01014 } 01015 } 01016 01017 01018 // Set up the return value... 01019 DSNodeHandle RetVal; 01020 Instruction *I = CS.getInstruction(); 01021 if (isPointerType(I->getType())) 01022 RetVal = getValueDest(*I); 01023 01024 DSNode *CalleeNode = 0; 01025 if (DisableDirectCallOpt || !isa<Function>(Callee)) { 01026 CalleeNode = getValueDest(*Callee).getNode(); 01027 if (CalleeNode == 0) { 01028 std::cerr << "WARNING: Program is calling through a null pointer?\n"<< *I; 01029 return; // Calling a null pointer? 01030 } 01031 } 01032 01033 std::vector<DSNodeHandle> Args; 01034 Args.reserve(CS.arg_end()-CS.arg_begin()); 01035 01036 // Calculate the arguments vector... 01037 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 01038 if (isPointerType((*I)->getType())) 01039 Args.push_back(getValueDest(**I)); 01040 01041 // Add a new function call entry... 01042 if (CalleeNode) 01043 FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args)); 01044 else 01045 FunctionCalls->push_back(DSCallSite(CS, RetVal, cast<Function>(Callee), 01046 Args)); 01047 } 01048 01049 void GraphBuilder::visitFreeInst(FreeInst &FI) { 01050 // Mark that the node is written to... 01051 if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode()) 01052 N->setModifiedMarker()->setHeapNodeMarker(); 01053 } 01054 01055 /// Handle casts... 01056 void GraphBuilder::visitCastInst(CastInst &CI) { 01057 if (isPointerType(CI.getType())) 01058 if (isPointerType(CI.getOperand(0)->getType())) { 01059 DSNodeHandle Ptr = getValueDest(*CI.getOperand(0)); 01060 if (Ptr.getNode() == 0) return; 01061 01062 // Cast one pointer to the other, just act like a copy instruction 01063 setDestTo(CI, Ptr); 01064 } else { 01065 // Cast something (floating point, small integer) to a pointer. We need 01066 // to track the fact that the node points to SOMETHING, just something we 01067 // don't know about. Make an "Unknown" node. 01068 // 01069 setDestTo(CI, createNode()->setUnknownNodeMarker()); 01070 } 01071 } 01072 01073 01074 // visitInstruction - For all other instruction types, if we have any arguments 01075 // that are of pointer type, make them have unknown composition bits, and merge 01076 // the nodes together. 01077 void GraphBuilder::visitInstruction(Instruction &Inst) { 01078 DSNodeHandle CurNode; 01079 if (isPointerType(Inst.getType())) 01080 CurNode = getValueDest(Inst); 01081 for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I) 01082 if (isPointerType((*I)->getType())) 01083 CurNode.mergeWith(getValueDest(**I)); 01084 01085 if (DSNode *N = CurNode.getNode()) 01086 N->setUnknownNodeMarker(); 01087 } 01088 01089 01090 01091 //===----------------------------------------------------------------------===// 01092 // LocalDataStructures Implementation 01093 //===----------------------------------------------------------------------===// 01094 01095 // MergeConstantInitIntoNode - Merge the specified constant into the node 01096 // pointed to by NH. 01097 void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) { 01098 // Ensure a type-record exists... 01099 DSNode *NHN = NH.getNode(); 01100 NHN->mergeTypeInfo(C->getType(), NH.getOffset()); 01101 01102 if (C->getType()->isFirstClassType()) { 01103 if (isPointerType(C->getType())) 01104 // Avoid adding edges from null, or processing non-"pointer" stores 01105 NH.addEdgeTo(getValueDest(*C)); 01106 return; 01107 } 01108 01109 const TargetData &TD = NH.getNode()->getTargetData(); 01110 01111 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) { 01112 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 01113 // We don't currently do any indexing for arrays... 01114 MergeConstantInitIntoNode(NH, cast<Constant>(CA->getOperand(i))); 01115 } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 01116 const StructLayout *SL = TD.getStructLayout(CS->getType()); 01117 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { 01118 DSNode *NHN = NH.getNode(); 01119 //Some programmers think ending a structure with a [0 x sbyte] is cute 01120 //This should be ok as the allocation type should grow this type when 01121 //it is merged in if it is bigger. 01122 if (SL->MemberOffsets[i] < SL->StructSize) { 01123 DSNodeHandle NewNH(NHN, NH.getOffset()+(unsigned)SL->MemberOffsets[i]); 01124 MergeConstantInitIntoNode(NewNH, cast<Constant>(CS->getOperand(i))); 01125 } else if (SL->MemberOffsets[i] == SL->StructSize) { 01126 DEBUG(std::cerr << "Zero size element at end of struct\n"); 01127 } else { 01128 assert(0 && "type was smaller than offsets of of struct layout indicate"); 01129 } 01130 } 01131 } else if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) { 01132 // Noop 01133 } else { 01134 assert(0 && "Unknown constant type!"); 01135 } 01136 } 01137 01138 void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) { 01139 assert(!GV->isExternal() && "Cannot merge in external global!"); 01140 // Get a node handle to the global node and merge the initializer into it. 01141 DSNodeHandle NH = getValueDest(*GV); 01142 MergeConstantInitIntoNode(NH, GV->getInitializer()); 01143 } 01144 01145 01146 /// BuildGlobalECs - Look at all of the nodes in the globals graph. If any node 01147 /// contains multiple globals, DSA will never, ever, be able to tell the globals 01148 /// apart. Instead of maintaining this information in all of the graphs 01149 /// throughout the entire program, store only a single global (the "leader") in 01150 /// the graphs, and build equivalence classes for the rest of the globals. 01151 static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) { 01152 DSScalarMap &SM = GG.getScalarMap(); 01153 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 01154 for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); 01155 I != E; ++I) { 01156 if (I->getGlobalsList().size() <= 1) continue; 01157 01158 // First, build up the equivalence set for this block of globals. 01159 const std::vector<GlobalValue*> &GVs = I->getGlobalsList(); 01160 GlobalValue *First = GVs[0]; 01161 for (unsigned i = 1, e = GVs.size(); i != e; ++i) 01162 GlobalECs.unionSets(First, GVs[i]); 01163 01164 // Next, get the leader element. 01165 assert(First == GlobalECs.getLeaderValue(First) && 01166 "First did not end up being the leader?"); 01167 01168 // Next, remove all globals from the scalar map that are not the leader. 01169 assert(GVs[0] == First && "First had to be at the front!"); 01170 for (unsigned i = 1, e = GVs.size(); i != e; ++i) { 01171 ECGlobals.insert(GVs[i]); 01172 SM.erase(SM.find(GVs[i])); 01173 } 01174 01175 // Finally, change the global node to only contain the leader. 01176 I->clearGlobals(); 01177 I->addGlobal(First); 01178 } 01179 01180 DEBUG(GG.AssertGraphOK()); 01181 } 01182 01183 /// EliminateUsesOfECGlobals - Once we have determined that some globals are in 01184 /// really just equivalent to some other globals, remove the globals from the 01185 /// specified DSGraph (if present), and merge any nodes with their leader nodes. 01186 static void EliminateUsesOfECGlobals(DSGraph &G, 01187 const std::set<GlobalValue*> &ECGlobals) { 01188 DSScalarMap &SM = G.getScalarMap(); 01189 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 01190 01191 bool MadeChange = false; 01192 for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); 01193 GI != E; ) { 01194 GlobalValue *GV = *GI++; 01195 if (!ECGlobals.count(GV)) continue; 01196 01197 const DSNodeHandle &GVNH = SM[GV]; 01198 assert(!GVNH.isNull() && "Global has null NH!?"); 01199 01200 // Okay, this global is in some equivalence class. Start by finding the 01201 // leader of the class. 01202 GlobalValue *Leader = GlobalECs.getLeaderValue(GV); 01203 01204 // If the leader isn't already in the graph, insert it into the node 01205 // corresponding to GV. 01206 if (!SM.global_count(Leader)) { 01207 GVNH.getNode()->addGlobal(Leader); 01208 SM[Leader] = GVNH; 01209 } else { 01210 // Otherwise, the leader is in the graph, make sure the nodes are the 01211 // merged in the specified graph. 01212 const DSNodeHandle &LNH = SM[Leader]; 01213 if (LNH.getNode() != GVNH.getNode()) 01214 LNH.mergeWith(GVNH); 01215 } 01216 01217 // Next step, remove the global from the DSNode. 01218 GVNH.getNode()->removeGlobal(GV); 01219 01220 // Finally, remove the global from the ScalarMap. 01221 SM.erase(GV); 01222 MadeChange = true; 01223 } 01224 01225 DEBUG(if(MadeChange) G.AssertGraphOK()); 01226 } 01227 01228 bool LocalDataStructures::runOnModule(Module &M) { 01229 const TargetData &TD = getAnalysis<TargetData>(); 01230 01231 // First step, build the globals graph. 01232 GlobalsGraph = new DSGraph(GlobalECs, TD); 01233 { 01234 GraphBuilder GGB(*GlobalsGraph); 01235 01236 // Add initializers for all of the globals to the globals graph. 01237 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 01238 I != E; ++I) 01239 if (!I->isExternal()) 01240 GGB.mergeInGlobalInitializer(I); 01241 } 01242 01243 // Next step, iterate through the nodes in the globals graph, unioning 01244 // together the globals into equivalence classes. 01245 std::set<GlobalValue*> ECGlobals; 01246 BuildGlobalECs(*GlobalsGraph, ECGlobals); 01247 DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n"); 01248 ECGlobals.clear(); 01249 01250 // Calculate all of the graphs... 01251 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 01252 if (!I->isExternal()) 01253 DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I, 01254 GlobalsGraph))); 01255 01256 GlobalsGraph->removeTriviallyDeadNodes(); 01257 GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs); 01258 01259 // Now that we've computed all of the graphs, and merged all of the info into 01260 // the globals graph, see if we have further constrained the globals in the 01261 // program if so, update GlobalECs and remove the extraneous globals from the 01262 // program. 01263 BuildGlobalECs(*GlobalsGraph, ECGlobals); 01264 if (!ECGlobals.empty()) { 01265 DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n"); 01266 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 01267 E = DSInfo.end(); I != E; ++I) 01268 EliminateUsesOfECGlobals(*I->second, ECGlobals); 01269 } 01270 01271 return false; 01272 } 01273 01274 // releaseMemory - If the pass pipeline is done with this pass, we can release 01275 // our memory... here... 01276 // 01277 void LocalDataStructures::releaseMemory() { 01278 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 01279 E = DSInfo.end(); I != E; ++I) { 01280 I->second->getReturnNodes().erase(I->first); 01281 if (I->second->getReturnNodes().empty()) 01282 delete I->second; 01283 } 01284 01285 // Empty map so next time memory is released, data structures are not 01286 // re-deleted. 01287 DSInfo.clear(); 01288 delete GlobalsGraph; 01289 GlobalsGraph = 0; 01290 } 01291