LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Analysis/DataStructure/Local.cpp

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