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 // Merge the first & second arguments, and mark the memory read and 00553 // modified. 00554 DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); 00555 RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); 00556 if (DSNode *N = RetNH.getNode()) 00557 N->setModifiedMarker()->setReadMarker(); 00558 return; 00559 } 00560 case Intrinsic::memset_i32: 00561 case Intrinsic::memset_i64: 00562 // Mark the memory modified. 00563 if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) 00564 N->setModifiedMarker(); 00565 return; 00566 default: 00567 // Determine if the called function is one of the specified heap 00568 // allocation functions 00569 for (cl::list<std::string>::iterator AllocFunc = AllocList.begin(), 00570 LastAllocFunc = AllocList.end(); 00571 AllocFunc != LastAllocFunc; 00572 ++AllocFunc) { 00573 if (F->getName() == *(AllocFunc)) { 00574 setDestTo(*CS.getInstruction(), 00575 createNode()->setHeapNodeMarker()->setModifiedMarker()); 00576 return; 00577 } 00578 } 00579 00580 // Determine if the called function is one of the specified heap 00581 // free functions 00582 for (cl::list<std::string>::iterator FreeFunc = FreeList.begin(), 00583 LastFreeFunc = FreeList.end(); 00584 FreeFunc != LastFreeFunc; 00585 ++FreeFunc) { 00586 if (F->getName() == *(FreeFunc)) { 00587 // Mark that the node is written to... 00588 if (DSNode *N = getValueDest(*(CS.getArgument(0))).getNode()) 00589 N->setModifiedMarker()->setHeapNodeMarker(); 00590 return; 00591 } 00592 } 00593 00594 //gets select localtime ioctl 00595 00596 if ((F->isExternal() && F->getName() == "calloc") 00597 || F->getName() == "posix_memalign" 00598 || F->getName() == "memalign" || F->getName() == "valloc") { 00599 setDestTo(*CS.getInstruction(), 00600 createNode()->setHeapNodeMarker()->setModifiedMarker()); 00601 return; 00602 } else if (F->getName() == "realloc") { 00603 DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); 00604 if (CS.arg_begin() != CS.arg_end()) 00605 RetNH.mergeWith(getValueDest(**CS.arg_begin())); 00606 if (DSNode *N = RetNH.getNode()) 00607 N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); 00608 return; 00609 } else if (F->getName() == "memmove") { 00610 // Merge the first & second arguments, and mark the memory read and 00611 // modified. 00612 DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); 00613 RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); 00614 if (DSNode *N = RetNH.getNode()) 00615 N->setModifiedMarker()->setReadMarker(); 00616 return; 00617 } else if (F->getName() == "free") { 00618 // Mark that the node is written to... 00619 if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) 00620 N->setModifiedMarker()->setHeapNodeMarker(); 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 F->getName() == "strlen") { 00634 // These functions read all of their pointer operands. 00635 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00636 AI != E; ++AI) { 00637 if (isPointerType((*AI)->getType())) 00638 if (DSNode *N = getValueDest(**AI).getNode()) 00639 N->setReadMarker(); 00640 } 00641 return; 00642 } else if (F->getName() == "memchr") { 00643 DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); 00644 DSNodeHandle Result = getValueDest(*CS.getInstruction()); 00645 RetNH.mergeWith(Result); 00646 if (DSNode *N = RetNH.getNode()) 00647 N->setReadMarker(); 00648 return; 00649 } else if (F->getName() == "read" || F->getName() == "pipe" || 00650 F->getName() == "wait" || F->getName() == "time" || 00651 F->getName() == "getrusage") { 00652 // These functions write all of their pointer operands. 00653 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00654 AI != E; ++AI) { 00655 if (isPointerType((*AI)->getType())) 00656 if (DSNode *N = getValueDest(**AI).getNode()) 00657 N->setModifiedMarker(); 00658 } 00659 return; 00660 } else if (F->getName() == "stat" || F->getName() == "fstat" || 00661 F->getName() == "lstat") { 00662 // These functions read their first operand if its a pointer. 00663 CallSite::arg_iterator AI = CS.arg_begin(); 00664 if (isPointerType((*AI)->getType())) { 00665 DSNodeHandle Path = getValueDest(**AI); 00666 if (DSNode *N = Path.getNode()) N->setReadMarker(); 00667 } 00668 00669 // Then they write into the stat buffer. 00670 DSNodeHandle StatBuf = getValueDest(**++AI); 00671 if (DSNode *N = StatBuf.getNode()) { 00672 N->setModifiedMarker(); 00673 const Type *StatTy = F->getFunctionType()->getParamType(1); 00674 if (const PointerType *PTy = dyn_cast<PointerType>(StatTy)) 00675 N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset()); 00676 } 00677 return; 00678 } else if (F->getName() == "strtod" || F->getName() == "strtof" || 00679 F->getName() == "strtold") { 00680 // These functions read the first pointer 00681 if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) { 00682 Str->setReadMarker(); 00683 // If the second parameter is passed, it will point to the first 00684 // argument node. 00685 const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1)); 00686 if (DSNode *End = EndPtrNH.getNode()) { 00687 End->mergeTypeInfo(PointerType::get(Type::SByteTy), 00688 EndPtrNH.getOffset(), false); 00689 End->setModifiedMarker(); 00690 DSNodeHandle &Link = getLink(EndPtrNH); 00691 Link.mergeWith(getValueDest(**CS.arg_begin())); 00692 } 00693 } 00694 return; 00695 } else if (F->getName() == "fopen" || F->getName() == "fdopen" || 00696 F->getName() == "freopen") { 00697 // These functions read all of their pointer operands. 00698 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00699 AI != E; ++AI) 00700 if (isPointerType((*AI)->getType())) 00701 if (DSNode *N = getValueDest(**AI).getNode()) 00702 N->setReadMarker(); 00703 00704 // fopen allocates in an unknown way and writes to the file 00705 // descriptor. Also, merge the allocated type into the node. 00706 DSNodeHandle Result = getValueDest(*CS.getInstruction()); 00707 if (DSNode *N = Result.getNode()) { 00708 N->setModifiedMarker()->setUnknownNodeMarker(); 00709 const Type *RetTy = F->getFunctionType()->getReturnType(); 00710 if (const PointerType *PTy = dyn_cast<PointerType>(RetTy)) 00711 N->mergeTypeInfo(PTy->getElementType(), Result.getOffset()); 00712 } 00713 00714 // If this is freopen, merge the file descriptor passed in with the 00715 // result. 00716 if (F->getName() == "freopen") { 00717 // ICC doesn't handle getting the iterator, decrementing and 00718 // dereferencing it in one operation without error. Do it in 2 steps 00719 CallSite::arg_iterator compit = CS.arg_end(); 00720 Result.mergeWith(getValueDest(**--compit)); 00721 } 00722 return; 00723 } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){ 00724 // fclose reads and deallocates the memory in an unknown way for the 00725 // file descriptor. It merges the FILE type into the descriptor. 00726 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00727 if (DSNode *N = H.getNode()) { 00728 N->setReadMarker()->setUnknownNodeMarker(); 00729 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00730 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00731 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00732 } 00733 return; 00734 } else if (CS.arg_end()-CS.arg_begin() == 1 && 00735 (F->getName() == "fflush" || F->getName() == "feof" || 00736 F->getName() == "fileno" || F->getName() == "clearerr" || 00737 F->getName() == "rewind" || F->getName() == "ftell" || 00738 F->getName() == "ferror" || F->getName() == "fgetc" || 00739 F->getName() == "fgetc" || F->getName() == "_IO_getc")) { 00740 // fflush reads and writes the memory for the file descriptor. It 00741 // merges the FILE type into the descriptor. 00742 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00743 if (DSNode *N = H.getNode()) { 00744 N->setReadMarker()->setModifiedMarker(); 00745 00746 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00747 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00748 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00749 } 00750 return; 00751 } else if (CS.arg_end()-CS.arg_begin() == 4 && 00752 (F->getName() == "fwrite" || F->getName() == "fread")) { 00753 // fread writes the first operand, fwrite reads it. They both 00754 // read/write the FILE descriptor, and merges the FILE type. 00755 CallSite::arg_iterator compit = CS.arg_end(); 00756 DSNodeHandle H = getValueDest(**--compit); 00757 if (DSNode *N = H.getNode()) { 00758 N->setReadMarker()->setModifiedMarker(); 00759 const Type *ArgTy = F->getFunctionType()->getParamType(3); 00760 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00761 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00762 } 00763 00764 H = getValueDest(**CS.arg_begin()); 00765 if (DSNode *N = H.getNode()) 00766 if (F->getName() == "fwrite") 00767 N->setReadMarker(); 00768 else 00769 N->setModifiedMarker(); 00770 return; 00771 } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){ 00772 // fgets reads and writes the memory for the file descriptor. It 00773 // merges the FILE type into the descriptor, and writes to the 00774 // argument. It returns the argument as well. 00775 CallSite::arg_iterator AI = CS.arg_begin(); 00776 DSNodeHandle H = getValueDest(**AI); 00777 if (DSNode *N = H.getNode()) 00778 N->setModifiedMarker(); // Writes buffer 00779 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00780 ++AI; ++AI; 00781 00782 // Reads and writes file descriptor, merge in FILE type. 00783 H = getValueDest(**AI); 00784 if (DSNode *N = H.getNode()) { 00785 N->setReadMarker()->setModifiedMarker(); 00786 const Type *ArgTy = F->getFunctionType()->getParamType(2); 00787 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00788 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00789 } 00790 return; 00791 } else if (F->getName() == "ungetc" || F->getName() == "fputc" || 00792 F->getName() == "fputs" || F->getName() == "putc" || 00793 F->getName() == "ftell" || F->getName() == "rewind" || 00794 F->getName() == "_IO_putc") { 00795 // These functions read and write the memory for the file descriptor, 00796 // which is passes as the last argument. 00797 CallSite::arg_iterator compit = CS.arg_end(); 00798 DSNodeHandle H = getValueDest(**--compit); 00799 if (DSNode *N = H.getNode()) { 00800 N->setReadMarker()->setModifiedMarker(); 00801 FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); 00802 const Type *ArgTy = *--compit2; 00803 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00804 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00805 } 00806 00807 // Any pointer arguments are read. 00808 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00809 AI != E; ++AI) 00810 if (isPointerType((*AI)->getType())) 00811 if (DSNode *N = getValueDest(**AI).getNode()) 00812 N->setReadMarker(); 00813 return; 00814 } else if (F->getName() == "fseek" || F->getName() == "fgetpos" || 00815 F->getName() == "fsetpos") { 00816 // These functions read and write the memory for the file descriptor, 00817 // and read/write all other arguments. 00818 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00819 if (DSNode *N = H.getNode()) { 00820 FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); 00821 const Type *ArgTy = *--compit2; 00822 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00823 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00824 } 00825 00826 // Any pointer arguments are read. 00827 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00828 AI != E; ++AI) 00829 if (isPointerType((*AI)->getType())) 00830 if (DSNode *N = getValueDest(**AI).getNode()) 00831 N->setReadMarker()->setModifiedMarker(); 00832 return; 00833 } else if (F->getName() == "printf" || F->getName() == "fprintf" || 00834 F->getName() == "sprintf") { 00835 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00836 00837 if (F->getName() == "fprintf") { 00838 // fprintf reads and writes the FILE argument, and applies the type 00839 // to it. 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 } else if (F->getName() == "sprintf") { 00848 // sprintf writes the first string argument. 00849 DSNodeHandle H = getValueDest(**AI++); 00850 if (DSNode *N = H.getNode()) { 00851 N->setModifiedMarker(); 00852 const Type *ArgTy = (*AI)->getType(); 00853 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00854 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00855 } 00856 } 00857 00858 for (; AI != E; ++AI) { 00859 // printf reads all pointer arguments. 00860 if (isPointerType((*AI)->getType())) 00861 if (DSNode *N = getValueDest(**AI).getNode()) 00862 N->setReadMarker(); 00863 } 00864 return; 00865 } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" || 00866 F->getName() == "vsprintf") { 00867 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00868 00869 if (F->getName() == "vfprintf") { 00870 // ffprintf reads and writes the FILE argument, and applies the type 00871 // to it. 00872 DSNodeHandle H = getValueDest(**AI); 00873 if (DSNode *N = H.getNode()) { 00874 N->setModifiedMarker()->setReadMarker(); 00875 const Type *ArgTy = (*AI)->getType(); 00876 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00877 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00878 } 00879 ++AI; 00880 } else if (F->getName() == "vsprintf") { 00881 // vsprintf writes the first string argument. 00882 DSNodeHandle H = getValueDest(**AI++); 00883 if (DSNode *N = H.getNode()) { 00884 N->setModifiedMarker(); 00885 const Type *ArgTy = (*AI)->getType(); 00886 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00887 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00888 } 00889 } 00890 00891 // Read the format 00892 if (AI != E) { 00893 if (isPointerType((*AI)->getType())) 00894 if (DSNode *N = getValueDest(**AI).getNode()) 00895 N->setReadMarker(); 00896 ++AI; 00897 } 00898 00899 // Read the valist, and the pointed-to objects. 00900 if (AI != E && isPointerType((*AI)->getType())) { 00901 const DSNodeHandle &VAList = getValueDest(**AI); 00902 if (DSNode *N = VAList.getNode()) { 00903 N->setReadMarker(); 00904 N->mergeTypeInfo(PointerType::get(Type::SByteTy), 00905 VAList.getOffset(), false); 00906 00907 DSNodeHandle &VAListObjs = getLink(VAList); 00908 VAListObjs.getNode()->setReadMarker(); 00909 } 00910 } 00911 00912 return; 00913 } else if (F->getName() == "scanf" || F->getName() == "fscanf" || 00914 F->getName() == "sscanf") { 00915 CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00916 00917 if (F->getName() == "fscanf") { 00918 // fscanf reads and writes the FILE argument, and applies the type 00919 // to it. 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 } else if (F->getName() == "sscanf") { 00928 // sscanf reads the first string argument. 00929 DSNodeHandle H = getValueDest(**AI++); 00930 if (DSNode *N = H.getNode()) { 00931 N->setReadMarker(); 00932 const Type *ArgTy = (*AI)->getType(); 00933 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00934 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00935 } 00936 } 00937 00938 for (; AI != E; ++AI) { 00939 // scanf writes all pointer arguments. 00940 if (isPointerType((*AI)->getType())) 00941 if (DSNode *N = getValueDest(**AI).getNode()) 00942 N->setModifiedMarker(); 00943 } 00944 return; 00945 } else if (F->getName() == "strtok") { 00946 // strtok reads and writes the first argument, returning it. It reads 00947 // its second arg. FIXME: strtok also modifies some hidden static 00948 // data. Someday this might matter. 00949 CallSite::arg_iterator AI = CS.arg_begin(); 00950 DSNodeHandle H = getValueDest(**AI++); 00951 if (DSNode *N = H.getNode()) { 00952 N->setReadMarker()->setModifiedMarker(); // Reads/Writes buffer 00953 const Type *ArgTy = F->getFunctionType()->getParamType(0); 00954 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00955 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00956 } 00957 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00958 00959 H = getValueDest(**AI); // Reads delimiter 00960 if (DSNode *N = H.getNode()) { 00961 N->setReadMarker(); 00962 const Type *ArgTy = F->getFunctionType()->getParamType(1); 00963 if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) 00964 N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); 00965 } 00966 return; 00967 } else if (F->getName() == "strchr" || F->getName() == "strrchr" || 00968 F->getName() == "strstr") { 00969 // These read their arguments, and return the first one 00970 DSNodeHandle H = getValueDest(**CS.arg_begin()); 00971 H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer 00972 00973 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00974 AI != E; ++AI) 00975 if (isPointerType((*AI)->getType())) 00976 if (DSNode *N = getValueDest(**AI).getNode()) 00977 N->setReadMarker(); 00978 00979 if (DSNode *N = H.getNode()) 00980 N->setReadMarker(); 00981 return; 00982 } else if (F->getName() == "__assert_fail") { 00983 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00984 AI != E; ++AI) 00985 if (isPointerType((*AI)->getType())) 00986 if (DSNode *N = getValueDest(**AI).getNode()) 00987 N->setReadMarker(); 00988 return; 00989 } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) { 00990 // This writes its second argument, and forces it to double. 00991 CallSite::arg_iterator compit = CS.arg_end(); 00992 DSNodeHandle H = getValueDest(**--compit); 00993 if (DSNode *N = H.getNode()) { 00994 N->setModifiedMarker(); 00995 N->mergeTypeInfo(Type::DoubleTy, H.getOffset()); 00996 } 00997 return; 00998 } else if (F->getName() == "strcat" || F->getName() == "strncat") { 00999 //This might be making unsafe assumptions about usage 01000 //Merge return and first arg 01001 DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); 01002 RetNH.mergeWith(getValueDest(**CS.arg_begin())); 01003 if (DSNode *N = RetNH.getNode()) 01004 N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); 01005 //and read second pointer 01006 if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) 01007 N->setReadMarker(); 01008 return; 01009 } else if (F->getName() == "strcpy" || F->getName() == "strncpy") { 01010 //This might be making unsafe assumptions about usage 01011 //Merge return and first arg 01012 DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); 01013 RetNH.mergeWith(getValueDest(**CS.arg_begin())); 01014 if (DSNode *N = RetNH.getNode()) 01015 N->setHeapNodeMarker()->setModifiedMarker(); 01016 //and read second pointer 01017 if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) 01018 N->setReadMarker(); 01019 return; 01020 } else { 01021 // Unknown function, warn if it returns a pointer type or takes a 01022 // pointer argument. 01023 bool Warn = isPointerType(CS.getInstruction()->getType()); 01024 if (!Warn) 01025 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 01026 I != E; ++I) 01027 if (isPointerType((*I)->getType())) { 01028 Warn = true; 01029 break; 01030 } 01031 if (Warn) 01032 std::cerr << "WARNING: Call to unknown external function '" 01033 << F->getName() << "' will cause pessimistic results!\n"; 01034 } 01035 } 01036 01037 01038 // Set up the return value... 01039 DSNodeHandle RetVal; 01040 Instruction *I = CS.getInstruction(); 01041 if (isPointerType(I->getType())) 01042 RetVal = getValueDest(*I); 01043 01044 DSNode *CalleeNode = 0; 01045 if (DisableDirectCallOpt || !isa<Function>(Callee)) { 01046 CalleeNode = getValueDest(*Callee).getNode(); 01047 if (CalleeNode == 0) { 01048 std::cerr << "WARNING: Program is calling through a null pointer?\n"<< *I; 01049 return; // Calling a null pointer? 01050 } 01051 } 01052 01053 std::vector<DSNodeHandle> Args; 01054 Args.reserve(CS.arg_end()-CS.arg_begin()); 01055 01056 // Calculate the arguments vector... 01057 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 01058 if (isPointerType((*I)->getType())) 01059 Args.push_back(getValueDest(**I)); 01060 01061 // Add a new function call entry... 01062 if (CalleeNode) 01063 FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args)); 01064 else 01065 FunctionCalls->push_back(DSCallSite(CS, RetVal, cast<Function>(Callee), 01066 Args)); 01067 } 01068 01069 void GraphBuilder::visitFreeInst(FreeInst &FI) { 01070 // Mark that the node is written to... 01071 if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode()) 01072 N->setModifiedMarker()->setHeapNodeMarker(); 01073 } 01074 01075 /// Handle casts... 01076 void GraphBuilder::visitCastInst(CastInst &CI) { 01077 if (isPointerType(CI.getType())) 01078 if (isPointerType(CI.getOperand(0)->getType())) { 01079 DSNodeHandle Ptr = getValueDest(*CI.getOperand(0)); 01080 if (Ptr.getNode() == 0) return; 01081 01082 // Cast one pointer to the other, just act like a copy instruction 01083 setDestTo(CI, Ptr); 01084 } else { 01085 // Cast something (floating point, small integer) to a pointer. We need 01086 // to track the fact that the node points to SOMETHING, just something we 01087 // don't know about. Make an "Unknown" node. 01088 // 01089 setDestTo(CI, createNode()->setUnknownNodeMarker()); 01090 } 01091 } 01092 01093 01094 // visitInstruction - For all other instruction types, if we have any arguments 01095 // that are of pointer type, make them have unknown composition bits, and merge 01096 // the nodes together. 01097 void GraphBuilder::visitInstruction(Instruction &Inst) { 01098 DSNodeHandle CurNode; 01099 if (isPointerType(Inst.getType())) 01100 CurNode = getValueDest(Inst); 01101 for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I) 01102 if (isPointerType((*I)->getType())) 01103 CurNode.mergeWith(getValueDest(**I)); 01104 01105 if (DSNode *N = CurNode.getNode()) 01106 N->setUnknownNodeMarker(); 01107 } 01108 01109 01110 01111 //===----------------------------------------------------------------------===// 01112 // LocalDataStructures Implementation 01113 //===----------------------------------------------------------------------===// 01114 01115 // MergeConstantInitIntoNode - Merge the specified constant into the node 01116 // pointed to by NH. 01117 void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) { 01118 // Ensure a type-record exists... 01119 DSNode *NHN = NH.getNode(); 01120 NHN->mergeTypeInfo(C->getType(), NH.getOffset()); 01121 01122 if (C->getType()->isFirstClassType()) { 01123 if (isPointerType(C->getType())) 01124 // Avoid adding edges from null, or processing non-"pointer" stores 01125 NH.addEdgeTo(getValueDest(*C)); 01126 return; 01127 } 01128 01129 const TargetData &TD = NH.getNode()->getTargetData(); 01130 01131 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) { 01132 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 01133 // We don't currently do any indexing for arrays... 01134 MergeConstantInitIntoNode(NH, cast<Constant>(CA->getOperand(i))); 01135 } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 01136 const StructLayout *SL = TD.getStructLayout(CS->getType()); 01137 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { 01138 DSNode *NHN = NH.getNode(); 01139 //Some programmers think ending a structure with a [0 x sbyte] is cute 01140 if (SL->MemberOffsets[i] < SL->StructSize) { 01141 DSNodeHandle NewNH(NHN, NH.getOffset()+(unsigned)SL->MemberOffsets[i]); 01142 MergeConstantInitIntoNode(NewNH, cast<Constant>(CS->getOperand(i))); 01143 } else if (SL->MemberOffsets[i] == SL->StructSize) { 01144 DEBUG(std::cerr << "Zero size element at end of struct\n"); 01145 NHN->foldNodeCompletely(); 01146 } else { 01147 assert(0 && "type was smaller than offsets of of struct layout indicate"); 01148 } 01149 } 01150 } else if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) { 01151 // Noop 01152 } else { 01153 assert(0 && "Unknown constant type!"); 01154 } 01155 } 01156 01157 void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) { 01158 assert(!GV->isExternal() && "Cannot merge in external global!"); 01159 // Get a node handle to the global node and merge the initializer into it. 01160 DSNodeHandle NH = getValueDest(*GV); 01161 MergeConstantInitIntoNode(NH, GV->getInitializer()); 01162 } 01163 01164 01165 /// BuildGlobalECs - Look at all of the nodes in the globals graph. If any node 01166 /// contains multiple globals, DSA will never, ever, be able to tell the globals 01167 /// apart. Instead of maintaining this information in all of the graphs 01168 /// throughout the entire program, store only a single global (the "leader") in 01169 /// the graphs, and build equivalence classes for the rest of the globals. 01170 static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) { 01171 DSScalarMap &SM = GG.getScalarMap(); 01172 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 01173 for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); 01174 I != E; ++I) { 01175 if (I->getGlobalsList().size() <= 1) continue; 01176 01177 // First, build up the equivalence set for this block of globals. 01178 const std::vector<GlobalValue*> &GVs = I->getGlobalsList(); 01179 GlobalValue *First = GVs[0]; 01180 for (unsigned i = 1, e = GVs.size(); i != e; ++i) 01181 GlobalECs.unionSets(First, GVs[i]); 01182 01183 // Next, get the leader element. 01184 assert(First == GlobalECs.getLeaderValue(First) && 01185 "First did not end up being the leader?"); 01186 01187 // Next, remove all globals from the scalar map that are not the leader. 01188 assert(GVs[0] == First && "First had to be at the front!"); 01189 for (unsigned i = 1, e = GVs.size(); i != e; ++i) { 01190 ECGlobals.insert(GVs[i]); 01191 SM.erase(SM.find(GVs[i])); 01192 } 01193 01194 // Finally, change the global node to only contain the leader. 01195 I->clearGlobals(); 01196 I->addGlobal(First); 01197 } 01198 01199 DEBUG(GG.AssertGraphOK()); 01200 } 01201 01202 /// EliminateUsesOfECGlobals - Once we have determined that some globals are in 01203 /// really just equivalent to some other globals, remove the globals from the 01204 /// specified DSGraph (if present), and merge any nodes with their leader nodes. 01205 static void EliminateUsesOfECGlobals(DSGraph &G, 01206 const std::set<GlobalValue*> &ECGlobals) { 01207 DSScalarMap &SM = G.getScalarMap(); 01208 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 01209 01210 bool MadeChange = false; 01211 for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); 01212 GI != E; ) { 01213 GlobalValue *GV = *GI++; 01214 if (!ECGlobals.count(GV)) continue; 01215 01216 const DSNodeHandle &GVNH = SM[GV]; 01217 assert(!GVNH.isNull() && "Global has null NH!?"); 01218 01219 // Okay, this global is in some equivalence class. Start by finding the 01220 // leader of the class. 01221 GlobalValue *Leader = GlobalECs.getLeaderValue(GV); 01222 01223 // If the leader isn't already in the graph, insert it into the node 01224 // corresponding to GV. 01225 if (!SM.global_count(Leader)) { 01226 GVNH.getNode()->addGlobal(Leader); 01227 SM[Leader] = GVNH; 01228 } else { 01229 // Otherwise, the leader is in the graph, make sure the nodes are the 01230 // merged in the specified graph. 01231 const DSNodeHandle &LNH = SM[Leader]; 01232 if (LNH.getNode() != GVNH.getNode()) 01233 LNH.mergeWith(GVNH); 01234 } 01235 01236 // Next step, remove the global from the DSNode. 01237 GVNH.getNode()->removeGlobal(GV); 01238 01239 // Finally, remove the global from the ScalarMap. 01240 SM.erase(GV); 01241 MadeChange = true; 01242 } 01243 01244 DEBUG(if(MadeChange) G.AssertGraphOK()); 01245 } 01246 01247 bool LocalDataStructures::runOnModule(Module &M) { 01248 const TargetData &TD = getAnalysis<TargetData>(); 01249 01250 // First step, build the globals graph. 01251 GlobalsGraph = new DSGraph(GlobalECs, TD); 01252 { 01253 GraphBuilder GGB(*GlobalsGraph); 01254 01255 // Add initializers for all of the globals to the globals graph. 01256 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 01257 I != E; ++I) 01258 if (!I->isExternal()) 01259 GGB.mergeInGlobalInitializer(I); 01260 } 01261 01262 // Next step, iterate through the nodes in the globals graph, unioning 01263 // together the globals into equivalence classes. 01264 std::set<GlobalValue*> ECGlobals; 01265 BuildGlobalECs(*GlobalsGraph, ECGlobals); 01266 DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n"); 01267 ECGlobals.clear(); 01268 01269 // Calculate all of the graphs... 01270 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 01271 if (!I->isExternal()) 01272 DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I, 01273 GlobalsGraph))); 01274 01275 GlobalsGraph->removeTriviallyDeadNodes(); 01276 GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs); 01277 01278 // Now that we've computed all of the graphs, and merged all of the info into 01279 // the globals graph, see if we have further constrained the globals in the 01280 // program if so, update GlobalECs and remove the extraneous globals from the 01281 // program. 01282 BuildGlobalECs(*GlobalsGraph, ECGlobals); 01283 if (!ECGlobals.empty()) { 01284 DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n"); 01285 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 01286 E = DSInfo.end(); I != E; ++I) 01287 EliminateUsesOfECGlobals(*I->second, ECGlobals); 01288 } 01289 01290 return false; 01291 } 01292 01293 // releaseMemory - If the pass pipeline is done with this pass, we can release 01294 // our memory... here... 01295 // 01296 void LocalDataStructures::releaseMemory() { 01297 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 01298 E = DSInfo.end(); I != E; ++I) { 01299 I->second->getReturnNodes().erase(I->first); 01300 if (I->second->getReturnNodes().empty()) 01301 delete I->second; 01302 } 01303 01304 // Empty map so next time memory is released, data structures are not 01305 // re-deleted. 01306 DSInfo.clear(); 01307 delete GlobalsGraph; 01308 GlobalsGraph = 0; 01309 } 01310