lib/Analysis/DataStructure/Local.cpp

   1 //===- Local.cpp - Compute a local data structure graph for a function ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Compute the local version of the data structure graph for a function.  The
  11 // external interface to this file is the DSGraph constructor.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/DataStructure/DataStructure.h"
  16 #include "llvm/Analysis/DataStructure/DSGraph.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/Support/GetElementPtrTypeIterator.h"
  22 #include "llvm/Support/InstVisitor.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/Timer.h"
  27 #include <iostream>
  28
  29 // FIXME: This should eventually be a FunctionPass that is automatically
  30 // aggregated into a Pass.
  31 //
  32 #include "llvm/Module.h"
  33
  34 using namespace llvm;
  35
  36 static RegisterAnalysis<LocalDataStructures>
  37 X("datastructure", "Local Data Structure Analysis");
  38
  39 static cl::opt<bool>
  40 TrackIntegersAsPointers("dsa-track-integers", cl::Hidden,
  41          cl::desc("If this is set, track integers as potential pointers"));
  42
  43 static cl::list<std::string>
  44 AllocList("dsa-alloc-list",
  45           cl::value_desc("list"),
  46           cl::desc("List of functions that allocate memory from the heap"),
  47           cl::CommaSeparated, cl::Hidden);
  48
  49 static cl::list<std::string>
  50 FreeList("dsa-free-list",
  51           cl::value_desc("list"),
  52           cl::desc("List of functions that free memory from the heap"),
  53           cl::CommaSeparated, cl::Hidden);
  54
  55 namespace llvm {
  56 namespace DS {
  57   // isPointerType - Return true if this type is big enough to hold a pointer.
  58   bool isPointerType(const Type *Ty) {
  59     if (isa<PointerType>(Ty))
  60       return true;
  61     else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger())
  62       return Ty->getPrimitiveSize() >= PointerSize;
  63     return false;
  64   }
  65 }}
  66
  67 using namespace DS;
  68
  69 namespace {
  70   cl::opt<bool>
  71   DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden,
  72                        cl::desc("Disable direct call optimization in "
  73                                 "DSGraph construction"));
  74   cl::opt<bool>
  75   DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden,
  76                           cl::desc("Disable field sensitivity in DSGraphs"));
  77
  78   //===--------------------------------------------------------------------===//
  79   //  GraphBuilder Class
  80   //===--------------------------------------------------------------------===//
  81   //
  82   /// This class is the builder class that constructs the local data structure
  83   /// graph by performing a single pass over the function in question.
  84   ///
  85   class GraphBuilder : InstVisitor<GraphBuilder> {
  86     DSGraph &G;
  87     DSNodeHandle *RetNode;               // Node that gets returned...
  88     DSScalarMap &ScalarMap;
  89     std::list<DSCallSite> *FunctionCalls;
  90
  91   public:
  92     GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode,
  93                  std::list<DSCallSite> &fc)
  94       : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()),
  95         FunctionCalls(&fc) {
  96
  97       // Create scalar nodes for all pointer arguments...
  98       for (Function::arg_iterator I = f.arg_begin(), E = f.arg_end();
  99            I != E; ++I)
 100         if (isPointerType(I->getType()))
 101           getValueDest(*I);
 102
 103       visit(f);  // Single pass over the function
 104     }
 105
 106     // GraphBuilder ctor for working on the globals graph
 107     GraphBuilder(DSGraph &g)
 108       : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) {
 109     }
 110
 111     void mergeInGlobalInitializer(GlobalVariable *GV);
 112
 113   private:
 114     // Visitor functions, used to handle each instruction type we encounter...
 115     friend class InstVisitor<GraphBuilder>;
 116     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); }
 117     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); }
 118     void handleAlloc(AllocationInst &AI, bool isHeap);
 119
 120     void visitPHINode(PHINode &PN);
 121     void visitSelectInst(SelectInst &SI);
 122
 123     void visitGetElementPtrInst(User &GEP);
 124     void visitReturnInst(ReturnInst &RI);
 125     void visitLoadInst(LoadInst &LI);
 126     void visitStoreInst(StoreInst &SI);
 127     void visitCallInst(CallInst &CI);
 128     void visitInvokeInst(InvokeInst &II);
 129     void visitSetCondInst(SetCondInst &SCI);
 130     void visitFreeInst(FreeInst &FI);
 131     void visitCastInst(CastInst &CI);
 132     void visitInstruction(Instruction &I);
 133
 134     void visitCallSite(CallSite CS);
 135     void visitVAArgInst(VAArgInst   &I);
 136
 137     void MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C);
 138   private:
 139     // Helper functions used to implement the visitation functions...
 140
 141     /// createNode - Create a new DSNode, ensuring that it is properly added to
 142     /// the graph.
 143     ///
 144     DSNode *createNode(const Type *Ty = 0) {
 145       DSNode *N = new DSNode(Ty, &G);   // Create the node
 146       if (DisableFieldSensitivity) {
 147         // Create node handle referring to the old node so that it is
 148         // immediately removed from the graph when the node handle is destroyed.
 149         DSNodeHandle OldNNH = N;
 150         N->foldNodeCompletely();
 151         if (DSNode *FN = N->getForwardNode())
 152           N = FN;
 153       }
 154       return N;
 155     }
 156
 157     /// setDestTo - Set the ScalarMap entry for the specified value to point to
 158     /// the specified destination.  If the Value already points to a node, make
 159     /// sure to merge the two destinations together.
 160     ///
 161     void setDestTo(Value &V, const DSNodeHandle &NH);
 162
 163     /// getValueDest - Return the DSNode that the actual value points to.
 164     ///
 165     DSNodeHandle getValueDest(Value &V);
 166
 167     /// getLink - This method is used to return the specified link in the
 168     /// specified node if one exists.  If a link does not already exist (it's
 169     /// null), then we create a new node, link it, then return it.
 170     ///
 171     DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0);
 172   };
 173 }
 174
 175 using namespace DS;
 176
 177 //===----------------------------------------------------------------------===//
 178 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 179 // graph.
 180 DSGraph::DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td,
 181                  Function &F, DSGraph *GG)
 182   : GlobalsGraph(GG), ScalarMap(ECs), TD(td) {
 183   PrintAuxCalls = false;
 184
 185   DEBUG(std::cerr << "  [Loc] Calculating graph for: " << F.getName() << "\n");
 186
 187   // Use the graph builder to construct the local version of the graph
 188   GraphBuilder B(F, *this, ReturnNodes[&F], FunctionCalls);
 189 #ifndef NDEBUG
 190   Timer::addPeakMemoryMeasurement();
 191 #endif
 192
 193   // If there are any constant globals referenced in this function, merge their
 194   // initializers into the local graph from the globals graph.
 195   if (ScalarMap.global_begin() != ScalarMap.global_end()) {
 196     ReachabilityCloner RC(*this, *GG, 0);
 197
 198     for (DSScalarMap::global_iterator I = ScalarMap.global_begin();
 199          I != ScalarMap.global_end(); ++I)
 200       if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I))
 201         if (!GV->isExternal() && GV->isConstant())
 202           RC.merge(ScalarMap[GV], GG->ScalarMap[GV]);
 203   }
 204
 205   markIncompleteNodes(DSGraph::MarkFormalArgs);
 206
 207   // Remove any nodes made dead due to merging...
 208   removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 209 }
 210
 211
 212 //===----------------------------------------------------------------------===//
 213 // Helper method implementations...
 214 //
 215
 216 /// getValueDest - Return the DSNode that the actual value points to.
 217 ///
 218 DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
 219   Value *V = &Val;
 220   if (isa<Constant>(V) && cast<Constant>(V)->isNullValue())
 221     return 0;  // Null doesn't point to anything, don't add to ScalarMap!
 222
 223   DSNodeHandle &NH = ScalarMap[V];
 224   if (!NH.isNull())
 225     return NH;     // Already have a node?  Just return it...
 226
 227   // Otherwise we need to create a new node to point to.
 228   // Check first for constant expressions that must be traversed to
 229   // extract the actual value.
 230   DSNode* N;
 231   if (GlobalValue* GV = dyn_cast<GlobalValue>(V)) {
 232     // Create a new global node for this global variable.
 233     N = createNode(GV->getType()->getElementType());
 234     N->addGlobal(GV);
 235   } else if (Constant *C = dyn_cast<Constant>(V)) {
 236     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 237       if (CE->getOpcode() == Instruction::Cast) {
 238         if (isa<PointerType>(CE->getOperand(0)->getType()))
 239           NH = getValueDest(*CE->getOperand(0));
 240         else
 241           NH = createNode()->setUnknownNodeMarker();
 242       } else if (CE->getOpcode() == Instruction::GetElementPtr) {
 243         visitGetElementPtrInst(*CE);
 244         DSScalarMap::iterator I = ScalarMap.find(CE);
 245         assert(I != ScalarMap.end() && "GEP didn't get processed right?");
 246         NH = I->second;
 247       } else {
 248         // This returns a conservative unknown node for any unhandled ConstExpr
 249         return NH = createNode()->setUnknownNodeMarker();
 250       }
 251       if (NH.isNull()) {  // (getelementptr null, X) returns null
 252         ScalarMap.erase(V);
 253         return 0;
 254       }
 255       return NH;
 256     } else if (isa<UndefValue>(C)) {
 257       ScalarMap.erase(V);
 258       return 0;
 259     } else {
 260       assert(0 && "Unknown constant type!");
 261     }
 262     N = createNode(); // just create a shadow node
 263   } else {
 264     // Otherwise just create a shadow node
 265     N = createNode();
 266   }
 267
 268   NH.setTo(N, 0);      // Remember that we are pointing to it...
 269   return NH;
 270 }
 271
 272
 273 /// getLink - This method is used to return the specified link in the
 274 /// specified node if one exists.  If a link does not already exist (it's
 275 /// null), then we create a new node, link it, then return it.  We must
 276 /// specify the type of the Node field we are accessing so that we know what
 277 /// type should be linked to if we need to create a new node.
 278 ///
 279 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) {
 280   DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
 281   DSNodeHandle &Link = Node.getLink(LinkNo);
 282   if (Link.isNull()) {
 283     // If the link hasn't been created yet, make and return a new shadow node
 284     Link = createNode();
 285   }
 286   return Link;
 287 }
 288
 289
 290 /// setDestTo - Set the ScalarMap entry for the specified value to point to the
 291 /// specified destination.  If the Value already points to a node, make sure to
 292 /// merge the two destinations together.
 293 ///
 294 void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) {
 295   ScalarMap[&V].mergeWith(NH);
 296 }
 297
 298
 299 //===----------------------------------------------------------------------===//
 300 // Specific instruction type handler implementations...
 301 //
 302
 303 /// Alloca & Malloc instruction implementation - Simply create a new memory
 304 /// object, pointing the scalar to it.
 305 ///
 306 void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) {
 307   DSNode *N = createNode();
 308   if (isHeap)
 309     N->setHeapNodeMarker();
 310   else
 311     N->setAllocaNodeMarker();
 312   setDestTo(AI, N);
 313 }
 314
 315 // PHINode - Make the scalar for the PHI node point to all of the things the
 316 // incoming values point to... which effectively causes them to be merged.
 317 //
 318 void GraphBuilder::visitPHINode(PHINode &PN) {
 319   if (!isPointerType(PN.getType())) return; // Only pointer PHIs
 320
 321   DSNodeHandle &PNDest = ScalarMap[&PN];
 322   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 323     PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
 324 }
 325
 326 void GraphBuilder::visitSelectInst(SelectInst &SI) {
 327   if (!isPointerType(SI.getType())) return; // Only pointer Selects
 328
 329   DSNodeHandle &Dest = ScalarMap[&SI];
 330   Dest.mergeWith(getValueDest(*SI.getOperand(1)));
 331   Dest.mergeWith(getValueDest(*SI.getOperand(2)));
 332 }
 333
 334 void GraphBuilder::visitSetCondInst(SetCondInst &SCI) {
 335   if (!isPointerType(SCI.getOperand(0)->getType()) ||
 336       isa<ConstantPointerNull>(SCI.getOperand(1))) return; // Only pointers
 337   ScalarMap[SCI.getOperand(0)].mergeWith(getValueDest(*SCI.getOperand(1)));
 338 }
 339
 340
 341 void GraphBuilder::visitGetElementPtrInst(User &GEP) {
 342   DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
 343   if (Value.isNull())
 344     Value = createNode();
 345
 346   // As a special case, if all of the index operands of GEP are constant zeros,
 347   // handle this just like we handle casts (ie, don't do much).
 348   bool AllZeros = true;
 349   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
 350     if (GEP.getOperand(i) !=
 351            Constant::getNullValue(GEP.getOperand(i)->getType())) {
 352       AllZeros = false;
 353       break;
 354     }
 355
 356   // If all of the indices are zero, the result points to the operand without
 357   // applying the type.
 358   if (AllZeros || (!Value.isNull() &&
 359                    Value.getNode()->isNodeCompletelyFolded())) {
 360     setDestTo(GEP, Value);
 361     return;
 362   }
 363
 364
 365   const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType());
 366   const Type *CurTy = PTy->getElementType();
 367
 368   if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) {
 369     // If the node had to be folded... exit quickly
 370     setDestTo(GEP, Value);  // GEP result points to folded node
 371     return;
 372   }
 373
 374   const TargetData &TD = Value.getNode()->getTargetData();
 375
 376 #if 0
 377   // Handle the pointer index specially...
 378   if (GEP.getNumOperands() > 1 &&
 379       (!isa<Constant>(GEP.getOperand(1)) ||
 380        !cast<Constant>(GEP.getOperand(1))->isNullValue())) {
 381
 382     // If we already know this is an array being accessed, don't do anything...
 383     if (!TopTypeRec.isArray) {
 384       TopTypeRec.isArray = true;
 385
 386       // If we are treating some inner field pointer as an array, fold the node
 387       // up because we cannot handle it right.  This can come because of
 388       // something like this:  &((&Pt->X)[1]) == &Pt->Y
 389       //
 390       if (Value.getOffset()) {
 391         // Value is now the pointer we want to GEP to be...
 392         Value.getNode()->foldNodeCompletely();
 393         setDestTo(GEP, Value);  // GEP result points to folded node
 394         return;
 395       } else {
 396         // This is a pointer to the first byte of the node.  Make sure that we
 397         // are pointing to the outter most type in the node.
 398         // FIXME: We need to check one more case here...
 399       }
 400     }
 401   }
 402 #endif
 403
 404   // All of these subscripts are indexing INTO the elements we have...
 405   unsigned Offset = 0;
 406   for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
 407        I != E; ++I)
 408     if (const StructType *STy = dyn_cast<StructType>(*I)) {
 409       unsigned FieldNo =
 410            (unsigned)cast<ConstantUInt>(I.getOperand())->getValue();
 411       Offset += (unsigned)TD.getStructLayout(STy)->MemberOffsets[FieldNo];
 412     } else if (const PointerType *PTy = dyn_cast<PointerType>(*I)) {
 413       if (!isa<Constant>(I.getOperand()) ||
 414           !cast<Constant>(I.getOperand())->isNullValue())
 415         Value.getNode()->setArrayMarker();
 416     }
 417
 418
 419 #if 0
 420     if (const SequentialType *STy = cast<SequentialType>(*I)) {
 421       CurTy = STy->getElementType();
 422       if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
 423         Offset += CS->getValue()*TD.getTypeSize(CurTy);
 424       } else {
 425         // Variable index into a node.  We must merge all of the elements of the
 426         // sequential type here.
 427         if (isa<PointerType>(STy))
 428           std::cerr << "Pointer indexing not handled yet!\n";
 429         else {
 430           const ArrayType *ATy = cast<ArrayType>(STy);
 431           unsigned ElSize = TD.getTypeSize(CurTy);
 432           DSNode *N = Value.getNode();
 433           assert(N && "Value must have a node!");
 434           unsigned RawOffset = Offset+Value.getOffset();
 435
 436           // Loop over all of the elements of the array, merging them into the
 437           // zeroth element.
 438           for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
 439             // Merge all of the byte components of this array element
 440             for (unsigned j = 0; j != ElSize; ++j)
 441               N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
 442         }
 443       }
 444     }
 445 #endif
 446
 447   // Add in the offset calculated...
 448   Value.setOffset(Value.getOffset()+Offset);
 449
 450   // Check the offset
 451   DSNode *N = Value.getNode();
 452   if (N &&
 453       !N->isNodeCompletelyFolded() &&
 454       (N->getSize() != 0 || Offset != 0) &&
 455       !N->isForwarding()) {
 456     if ((Offset >= N->getSize()) || int(Offset) < 0) {
 457       // Accessing offsets out of node size range
 458       // This is seen in the "magic" struct in named (from bind), where the
 459       // fourth field is an array of length 0, presumably used to create struct
 460       // instances of different sizes
 461
 462       // Collapse the node since its size is now variable
 463       N->foldNodeCompletely();
 464     }
 465   }
 466
 467   // Value is now the pointer we want to GEP to be...
 468   setDestTo(GEP, Value);
 469 }
 470
 471 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 472   DSNodeHandle Ptr = getValueDest(*LI.getOperand(0));
 473   if (Ptr.isNull())
 474     Ptr = createNode();
 475
 476   // Make that the node is read from...
 477   Ptr.getNode()->setReadMarker();
 478
 479   // Ensure a typerecord exists...
 480   Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false);
 481
 482   if (isPointerType(LI.getType()))
 483     setDestTo(LI, getLink(Ptr));
 484 }
 485
 486 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 487   const Type *StoredTy = SI.getOperand(0)->getType();
 488   DSNodeHandle Dest = getValueDest(*SI.getOperand(1));
 489   if (Dest.isNull()) return;
 490
 491   // Mark that the node is written to...
 492   Dest.getNode()->setModifiedMarker();
 493
 494   // Ensure a type-record exists...
 495   Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset());
 496
 497   // Avoid adding edges from null, or processing non-"pointer" stores
 498   if (isPointerType(StoredTy))
 499     Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
 500 }
 501
 502 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 503   if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()))
 504     RetNode->mergeWith(getValueDest(*RI.getOperand(0)));
 505 }
 506
 507 void GraphBuilder::visitVAArgInst(VAArgInst &I) {
 508   //FIXME: also updates the argument
 509   DSNodeHandle Ptr = getValueDest(*I.getOperand(0));
 510   if (Ptr.isNull()) return;
 511
 512   // Make that the node is read from.
 513   Ptr.getNode()->setReadMarker();
 514
 515   // Ensure a type record exists.
 516   DSNode *PtrN = Ptr.getNode();
 517   PtrN->mergeTypeInfo(I.getType(), Ptr.getOffset(), false);
 518
 519   if (isPointerType(I.getType()))
 520     setDestTo(I, getLink(Ptr));
 521 }
 522
 523
 524 void GraphBuilder::visitCallInst(CallInst &CI) {
 525   visitCallSite(&CI);
 526 }
 527
 528 void GraphBuilder::visitInvokeInst(InvokeInst &II) {
 529   visitCallSite(&II);
 530 }
 531
 532 void GraphBuilder::visitCallSite(CallSite CS) {
 533   Value *Callee = CS.getCalledValue();
 534
 535   // Special case handling of certain libc allocation functions here.
 536   if (Function *F = dyn_cast<Function>(Callee))
 537     if (F->isExternal())
 538       switch (F->getIntrinsicID()) {
 539       case Intrinsic::vastart:
 540         getValueDest(*CS.getInstruction()).getNode()->setAllocaNodeMarker();
 541         return;
 542       case Intrinsic::vacopy:
 543         getValueDest(*CS.getInstruction()).
 544           mergeWith(getValueDest(**(CS.arg_begin())));
 545         return;
 546       case Intrinsic::vaend:
 547         return;  // noop
 548       case Intrinsic::memcpy_i32:
 549       case Intrinsic::memcpy_i64:
 550       case Intrinsic::memmove_i32:
 551       case Intrinsic::memmove_i64: {
 552         // Merge the first & second arguments, and mark the memory read and
 553         // modified.
 554         DSNodeHandle RetNH = getValueDest(**CS.arg_begin());
 555         RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1)));
 556         if (DSNode *N = RetNH.getNode())
 557           N->setModifiedMarker()->setReadMarker();
 558         return;
 559       }
 560       case Intrinsic::memset_i32:
 561       case Intrinsic::memset_i64:
 562         // Mark the memory modified.
 563         if (DSNode *N = getValueDest(**CS.arg_begin()).getNode())
 564           N->setModifiedMarker();
 565         return;
 566       default:
 567         // Determine if the called function is one of the specified heap
 568         // allocation functions
 569         for (cl::list<std::string>::iterator AllocFunc = AllocList.begin(),
 570              LastAllocFunc = AllocList.end();
 571              AllocFunc != LastAllocFunc;
 572              ++AllocFunc) {
 573           if (F->getName() == *(AllocFunc)) {
 574             setDestTo(*CS.getInstruction(),
 575                       createNode()->setHeapNodeMarker()->setModifiedMarker());
 576             return;
 577           }
 578         }
 579
 580         // Determine if the called function is one of the specified heap
 581         // free functions
 582         for (cl::list<std::string>::iterator FreeFunc = FreeList.begin(),
 583              LastFreeFunc = FreeList.end();
 584              FreeFunc != LastFreeFunc;
 585              ++FreeFunc) {
 586           if (F->getName() == *(FreeFunc)) {
 587             // Mark that the node is written to...
 588             if (DSNode *N = getValueDest(*(CS.getArgument(0))).getNode())
 589               N->setModifiedMarker()->setHeapNodeMarker();
 590             return;
 591           }
 592         }
 593
 594         if ((F->isExternal() && F->getName() == "calloc")
 595             || F->getName() == "posix_memalign"
 596             || F->getName() == "memalign" || F->getName() == "valloc") {
 597           setDestTo(*CS.getInstruction(),
 598                     createNode()->setHeapNodeMarker()->setModifiedMarker());
 599           return;
 600         } else if (F->getName() == "realloc") {
 601           DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
 602           if (CS.arg_begin() != CS.arg_end())
 603             RetNH.mergeWith(getValueDest(**CS.arg_begin()));
 604           if (DSNode *N = RetNH.getNode())
 605             N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
 606           return;
 607         } else if (F->getName() == "memmove") {
 608           // Merge the first & second arguments, and mark the memory read and
 609           // modified.
 610           DSNodeHandle RetNH = getValueDest(**CS.arg_begin());
 611           RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1)));
 612           if (DSNode *N = RetNH.getNode())
 613             N->setModifiedMarker()->setReadMarker();
 614           return;
 615         } else if (F->getName() == "free") {
 616           // Mark that the node is written to...
 617           if (DSNode *N = getValueDest(**CS.arg_begin()).getNode())
 618             N->setModifiedMarker()->setHeapNodeMarker();
 619         } else if (F->getName() == "atoi" || F->getName() == "atof" ||
 620                    F->getName() == "atol" || F->getName() == "atoll" ||
 621                    F->getName() == "remove" || F->getName() == "unlink" ||
 622                    F->getName() == "rename" || F->getName() == "memcmp" ||
 623                    F->getName() == "strcmp" || F->getName() == "strncmp" ||
 624                    F->getName() == "execl" || F->getName() == "execlp" ||
 625                    F->getName() == "execle" || F->getName() == "execv" ||
 626                    F->getName() == "execvp" || F->getName() == "chmod" ||
 627                    F->getName() == "puts" || F->getName() == "write" ||
 628                    F->getName() == "open" || F->getName() == "create" ||
 629                    F->getName() == "truncate" || F->getName() == "chdir" ||
 630                    F->getName() == "mkdir" || F->getName() == "rmdir") {
 631           // These functions read all of their pointer operands.
 632           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 633                AI != E; ++AI) {
 634             if (isPointerType((*AI)->getType()))
 635               if (DSNode *N = getValueDest(**AI).getNode())
 636                 N->setReadMarker();
 637           }
 638           return;
 639         } else if (F->getName() == "read" || F->getName() == "pipe" ||
 640                    F->getName() == "wait" || F->getName() == "time") {
 641           // These functions write all of their pointer operands.
 642           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 643                AI != E; ++AI) {
 644             if (isPointerType((*AI)->getType()))
 645               if (DSNode *N = getValueDest(**AI).getNode())
 646                 N->setModifiedMarker();
 647           }
 648           return;
 649         } else if (F->getName() == "stat" || F->getName() == "fstat" ||
 650                    F->getName() == "lstat") {
 651           // These functions read their first operand if its a pointer.
 652           CallSite::arg_iterator AI = CS.arg_begin();
 653           if (isPointerType((*AI)->getType())) {
 654             DSNodeHandle Path = getValueDest(**AI);
 655             if (DSNode *N = Path.getNode()) N->setReadMarker();
 656           }
 657
 658           // Then they write into the stat buffer.
 659           DSNodeHandle StatBuf = getValueDest(**++AI);
 660           if (DSNode *N = StatBuf.getNode()) {
 661             N->setModifiedMarker();
 662             const Type *StatTy = F->getFunctionType()->getParamType(1);
 663             if (const PointerType *PTy = dyn_cast<PointerType>(StatTy))
 664               N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset());
 665           }
 666           return;
 667         } else if (F->getName() == "strtod" || F->getName() == "strtof" ||
 668                    F->getName() == "strtold") {
 669           // These functions read the first pointer
 670           if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) {
 671             Str->setReadMarker();
 672             // If the second parameter is passed, it will point to the first
 673             // argument node.
 674             const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1));
 675             if (DSNode *End = EndPtrNH.getNode()) {
 676               End->mergeTypeInfo(PointerType::get(Type::SByteTy),
 677                                  EndPtrNH.getOffset(), false);
 678               End->setModifiedMarker();
 679               DSNodeHandle &Link = getLink(EndPtrNH);
 680               Link.mergeWith(getValueDest(**CS.arg_begin()));
 681             }
 682           }
 683           return;
 684         } else if (F->getName() == "fopen" || F->getName() == "fdopen" ||
 685                    F->getName() == "freopen") {
 686           // These functions read all of their pointer operands.
 687           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 688                AI != E; ++AI)
 689             if (isPointerType((*AI)->getType()))
 690               if (DSNode *N = getValueDest(**AI).getNode())
 691                 N->setReadMarker();
 692
 693           // fopen allocates in an unknown way and writes to the file
 694           // descriptor.  Also, merge the allocated type into the node.
 695           DSNodeHandle Result = getValueDest(*CS.getInstruction());
 696           if (DSNode *N = Result.getNode()) {
 697             N->setModifiedMarker()->setUnknownNodeMarker();
 698             const Type *RetTy = F->getFunctionType()->getReturnType();
 699             if (const PointerType *PTy = dyn_cast<PointerType>(RetTy))
 700               N->mergeTypeInfo(PTy->getElementType(), Result.getOffset());
 701           }
 702
 703           // If this is freopen, merge the file descriptor passed in with the
 704           // result.
 705           if (F->getName() == "freopen") {
 706             // ICC doesn't handle getting the iterator, decrementing and
 707             // dereferencing it in one operation without error. Do it in 2 steps
 708             CallSite::arg_iterator compit = CS.arg_end();
 709             Result.mergeWith(getValueDest(**--compit));
 710           }
 711           return;
 712         } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){
 713           // fclose reads and deallocates the memory in an unknown way for the
 714           // file descriptor.  It merges the FILE type into the descriptor.
 715           DSNodeHandle H = getValueDest(**CS.arg_begin());
 716           if (DSNode *N = H.getNode()) {
 717             N->setReadMarker()->setUnknownNodeMarker();
 718             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 719             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 720               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 721           }
 722           return;
 723         } else if (CS.arg_end()-CS.arg_begin() == 1 &&
 724                    (F->getName() == "fflush" || F->getName() == "feof" ||
 725                     F->getName() == "fileno" || F->getName() == "clearerr" ||
 726                     F->getName() == "rewind" || F->getName() == "ftell" ||
 727                     F->getName() == "ferror" || F->getName() == "fgetc" ||
 728                     F->getName() == "fgetc" || F->getName() == "_IO_getc")) {
 729           // fflush reads and writes the memory for the file descriptor.  It
 730           // merges the FILE type into the descriptor.
 731           DSNodeHandle H = getValueDest(**CS.arg_begin());
 732           if (DSNode *N = H.getNode()) {
 733             N->setReadMarker()->setModifiedMarker();
 734
 735             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 736             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 737               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 738           }
 739           return;
 740         } else if (CS.arg_end()-CS.arg_begin() == 4 &&
 741                    (F->getName() == "fwrite" || F->getName() == "fread")) {
 742           // fread writes the first operand, fwrite reads it.  They both
 743           // read/write the FILE descriptor, and merges the FILE type.
 744           CallSite::arg_iterator compit = CS.arg_end();
 745           DSNodeHandle H = getValueDest(**--compit);
 746           if (DSNode *N = H.getNode()) {
 747             N->setReadMarker()->setModifiedMarker();
 748             const Type *ArgTy = F->getFunctionType()->getParamType(3);
 749             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 750               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 751           }
 752
 753           H = getValueDest(**CS.arg_begin());
 754           if (DSNode *N = H.getNode())
 755             if (F->getName() == "fwrite")
 756               N->setReadMarker();
 757             else
 758               N->setModifiedMarker();
 759           return;
 760         } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){
 761           // fgets reads and writes the memory for the file descriptor.  It
 762           // merges the FILE type into the descriptor, and writes to the
 763           // argument.  It returns the argument as well.
 764           CallSite::arg_iterator AI = CS.arg_begin();
 765           DSNodeHandle H = getValueDest(**AI);
 766           if (DSNode *N = H.getNode())
 767             N->setModifiedMarker();                        // Writes buffer
 768           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 769           ++AI; ++AI;
 770
 771           // Reads and writes file descriptor, merge in FILE type.
 772           H = getValueDest(**AI);
 773           if (DSNode *N = H.getNode()) {
 774             N->setReadMarker()->setModifiedMarker();
 775             const Type *ArgTy = F->getFunctionType()->getParamType(2);
 776             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 777               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 778           }
 779           return;
 780         } else if (F->getName() == "ungetc" || F->getName() == "fputc" ||
 781                    F->getName() == "fputs" || F->getName() == "putc" ||
 782                    F->getName() == "ftell" || F->getName() == "rewind" ||
 783                    F->getName() == "_IO_putc") {
 784           // These functions read and write the memory for the file descriptor,
 785           // which is passes as the last argument.
 786           CallSite::arg_iterator compit = CS.arg_end();
 787           DSNodeHandle H = getValueDest(**--compit);
 788           if (DSNode *N = H.getNode()) {
 789             N->setReadMarker()->setModifiedMarker();
 790             FunctionType::param_iterator compit2 = F->getFunctionType()->param_end();
 791             const Type *ArgTy = *--compit2;
 792             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 793               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 794           }
 795
 796           // Any pointer arguments are read.
 797           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 798                AI != E; ++AI)
 799             if (isPointerType((*AI)->getType()))
 800               if (DSNode *N = getValueDest(**AI).getNode())
 801                 N->setReadMarker();
 802           return;
 803         } else if (F->getName() == "fseek" || F->getName() == "fgetpos" ||
 804                    F->getName() == "fsetpos") {
 805           // These functions read and write the memory for the file descriptor,
 806           // and read/write all other arguments.
 807           DSNodeHandle H = getValueDest(**CS.arg_begin());
 808           if (DSNode *N = H.getNode()) {
 809             FunctionType::param_iterator compit2 = F->getFunctionType()->param_end();
 810             const Type *ArgTy = *--compit2;
 811             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 812               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 813           }
 814
 815           // Any pointer arguments are read.
 816           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 817                AI != E; ++AI)
 818             if (isPointerType((*AI)->getType()))
 819               if (DSNode *N = getValueDest(**AI).getNode())
 820                 N->setReadMarker()->setModifiedMarker();
 821           return;
 822         } else if (F->getName() == "printf" || F->getName() == "fprintf" ||
 823                    F->getName() == "sprintf") {
 824           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 825
 826           if (F->getName() == "fprintf") {
 827             // fprintf reads and writes the FILE argument, and applies the type
 828             // to it.
 829             DSNodeHandle H = getValueDest(**AI);
 830             if (DSNode *N = H.getNode()) {
 831               N->setModifiedMarker();
 832               const Type *ArgTy = (*AI)->getType();
 833               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 834                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 835             }
 836           } else if (F->getName() == "sprintf") {
 837             // sprintf writes the first string argument.
 838             DSNodeHandle H = getValueDest(**AI++);
 839             if (DSNode *N = H.getNode()) {
 840               N->setModifiedMarker();
 841               const Type *ArgTy = (*AI)->getType();
 842               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 843                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 844             }
 845           }
 846
 847           for (; AI != E; ++AI) {
 848             // printf reads all pointer arguments.
 849             if (isPointerType((*AI)->getType()))
 850               if (DSNode *N = getValueDest(**AI).getNode())
 851                 N->setReadMarker();
 852           }
 853           return;
 854         } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" ||
 855                    F->getName() == "vsprintf") {
 856           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 857
 858           if (F->getName() == "vfprintf") {
 859             // ffprintf reads and writes the FILE argument, and applies the type
 860             // to it.
 861             DSNodeHandle H = getValueDest(**AI);
 862             if (DSNode *N = H.getNode()) {
 863               N->setModifiedMarker()->setReadMarker();
 864               const Type *ArgTy = (*AI)->getType();
 865               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 866                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 867             }
 868             ++AI;
 869           } else if (F->getName() == "vsprintf") {
 870             // vsprintf writes the first string argument.
 871             DSNodeHandle H = getValueDest(**AI++);
 872             if (DSNode *N = H.getNode()) {
 873               N->setModifiedMarker();
 874               const Type *ArgTy = (*AI)->getType();
 875               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 876                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 877             }
 878           }
 879
 880           // Read the format
 881           if (AI != E) {
 882             if (isPointerType((*AI)->getType()))
 883               if (DSNode *N = getValueDest(**AI).getNode())
 884                 N->setReadMarker();
 885             ++AI;
 886           }
 887
 888           // Read the valist, and the pointed-to objects.
 889           if (AI != E && isPointerType((*AI)->getType())) {
 890             const DSNodeHandle &VAList = getValueDest(**AI);
 891             if (DSNode *N = VAList.getNode()) {
 892               N->setReadMarker();
 893               N->mergeTypeInfo(PointerType::get(Type::SByteTy),
 894                                VAList.getOffset(), false);
 895
 896               DSNodeHandle &VAListObjs = getLink(VAList);
 897               VAListObjs.getNode()->setReadMarker();
 898             }
 899           }
 900
 901           return;
 902         } else if (F->getName() == "scanf" || F->getName() == "fscanf" ||
 903                    F->getName() == "sscanf") {
 904           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 905
 906           if (F->getName() == "fscanf") {
 907             // fscanf reads and writes the FILE argument, and applies the type
 908             // to it.
 909             DSNodeHandle H = getValueDest(**AI);
 910             if (DSNode *N = H.getNode()) {
 911               N->setReadMarker();
 912               const Type *ArgTy = (*AI)->getType();
 913               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 914                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 915             }
 916           } else if (F->getName() == "sscanf") {
 917             // sscanf reads the first string argument.
 918             DSNodeHandle H = getValueDest(**AI++);
 919             if (DSNode *N = H.getNode()) {
 920               N->setReadMarker();
 921               const Type *ArgTy = (*AI)->getType();
 922               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 923                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 924             }
 925           }
 926
 927           for (; AI != E; ++AI) {
 928             // scanf writes all pointer arguments.
 929             if (isPointerType((*AI)->getType()))
 930               if (DSNode *N = getValueDest(**AI).getNode())
 931                 N->setModifiedMarker();
 932           }
 933           return;
 934         } else if (F->getName() == "strtok") {
 935           // strtok reads and writes the first argument, returning it.  It reads
 936           // its second arg.  FIXME: strtok also modifies some hidden static
 937           // data.  Someday this might matter.
 938           CallSite::arg_iterator AI = CS.arg_begin();
 939           DSNodeHandle H = getValueDest(**AI++);
 940           if (DSNode *N = H.getNode()) {
 941             N->setReadMarker()->setModifiedMarker();      // Reads/Writes buffer
 942             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 943             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 944               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 945           }
 946           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 947
 948           H = getValueDest(**AI);       // Reads delimiter
 949           if (DSNode *N = H.getNode()) {
 950             N->setReadMarker();
 951             const Type *ArgTy = F->getFunctionType()->getParamType(1);
 952             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 953               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 954           }
 955           return;
 956         } else if (F->getName() == "strchr" || F->getName() == "strrchr" ||
 957                    F->getName() == "strstr") {
 958           // These read their arguments, and return the first one
 959           DSNodeHandle H = getValueDest(**CS.arg_begin());
 960           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 961
 962           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 963                AI != E; ++AI)
 964             if (isPointerType((*AI)->getType()))
 965               if (DSNode *N = getValueDest(**AI).getNode())
 966                 N->setReadMarker();
 967
 968           if (DSNode *N = H.getNode())
 969             N->setReadMarker();
 970           return;
 971         } else if (F->getName() == "__assert_fail") {
 972           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 973                AI != E; ++AI)
 974             if (isPointerType((*AI)->getType()))
 975               if (DSNode *N = getValueDest(**AI).getNode())
 976                 N->setReadMarker();
 977           return;
 978         } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) {
 979           // This writes its second argument, and forces it to double.
 980           CallSite::arg_iterator compit = CS.arg_end();
 981           DSNodeHandle H = getValueDest(**--compit);
 982           if (DSNode *N = H.getNode()) {
 983             N->setModifiedMarker();
 984             N->mergeTypeInfo(Type::DoubleTy, H.getOffset());
 985           }
 986           return;
 987         } else if (F->getName() == "strcat" || F->getName() == "strncat") {
 988           //This might be making unsafe assumptions about usage
 989           //Merge return and first arg
 990           DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
 991           RetNH.mergeWith(getValueDest(**CS.arg_begin()));
 992           if (DSNode *N = RetNH.getNode())
 993             N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
 994           //and read second pointer
 995           if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode())
 996             N->setReadMarker();
 997           return;
 998         } else {
 999           // Unknown function, warn if it returns a pointer type or takes a
1000           // pointer argument.
1001           bool Warn = isPointerType(CS.getInstruction()->getType());
1002           if (!Warn)
1003             for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
1004                  I != E; ++I)
1005               if (isPointerType((*I)->getType())) {
1006                 Warn = true;
1007                 break;
1008               }
1009           if (Warn)
1010             std::cerr << "WARNING: Call to unknown external function '"
1011                       << F->getName() << "' will cause pessimistic results!\n";
1012         }
1013       }
1014
1015
1016   // Set up the return value...
1017   DSNodeHandle RetVal;
1018   Instruction *I = CS.getInstruction();
1019   if (isPointerType(I->getType()))
1020     RetVal = getValueDest(*I);
1021
1022   DSNode *CalleeNode = 0;
1023   if (DisableDirectCallOpt || !isa<Function>(Callee)) {
1024     CalleeNode = getValueDest(*Callee).getNode();
1025     if (CalleeNode == 0) {
1026       std::cerr << "WARNING: Program is calling through a null pointer?\n"<< *I;
1027       return;  // Calling a null pointer?
1028     }
1029   }
1030
1031   std::vector<DSNodeHandle> Args;
1032   Args.reserve(CS.arg_end()-CS.arg_begin());
1033
1034   // Calculate the arguments vector...
1035   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
1036     if (isPointerType((*I)->getType()))
1037       Args.push_back(getValueDest(**I));
1038
1039   // Add a new function call entry...
1040   if (CalleeNode)
1041     FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args));
1042   else
1043     FunctionCalls->push_back(DSCallSite(CS, RetVal, cast<Function>(Callee),
1044                                         Args));
1045 }
1046
1047 void GraphBuilder::visitFreeInst(FreeInst &FI) {
1048   // Mark that the node is written to...
1049   if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode())
1050     N->setModifiedMarker()->setHeapNodeMarker();
1051 }
1052
1053 /// Handle casts...
1054 void GraphBuilder::visitCastInst(CastInst &CI) {
1055   if (isPointerType(CI.getType()))
1056     if (isPointerType(CI.getOperand(0)->getType())) {
1057       DSNodeHandle Ptr = getValueDest(*CI.getOperand(0));
1058       if (Ptr.getNode() == 0) return;
1059
1060       // Cast one pointer to the other, just act like a copy instruction
1061       setDestTo(CI, Ptr);
1062     } else {
1063       // Cast something (floating point, small integer) to a pointer.  We need
1064       // to track the fact that the node points to SOMETHING, just something we
1065       // don't know about.  Make an "Unknown" node.
1066       //
1067       setDestTo(CI, createNode()->setUnknownNodeMarker());
1068     }
1069 }
1070
1071
1072 // visitInstruction - For all other instruction types, if we have any arguments
1073 // that are of pointer type, make them have unknown composition bits, and merge
1074 // the nodes together.
1075 void GraphBuilder::visitInstruction(Instruction &Inst) {
1076   DSNodeHandle CurNode;
1077   if (isPointerType(Inst.getType()))
1078     CurNode = getValueDest(Inst);
1079   for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I)
1080     if (isPointerType((*I)->getType()))
1081       CurNode.mergeWith(getValueDest(**I));
1082
1083   if (DSNode *N = CurNode.getNode())
1084     N->setUnknownNodeMarker();
1085 }
1086
1087
1088
1089 //===----------------------------------------------------------------------===//
1090 // LocalDataStructures Implementation
1091 //===----------------------------------------------------------------------===//
1092
1093 // MergeConstantInitIntoNode - Merge the specified constant into the node
1094 // pointed to by NH.
1095 void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) {
1096   // Ensure a type-record exists...
1097   DSNode *NHN = NH.getNode();
1098   NHN->mergeTypeInfo(C->getType(), NH.getOffset());
1099
1100   if (C->getType()->isFirstClassType()) {
1101     if (isPointerType(C->getType()))
1102       // Avoid adding edges from null, or processing non-"pointer" stores
1103       NH.addEdgeTo(getValueDest(*C));
1104     return;
1105   }
1106
1107   const TargetData &TD = NH.getNode()->getTargetData();
1108
1109   if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
1110     for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
1111       // We don't currently do any indexing for arrays...
1112       MergeConstantInitIntoNode(NH, cast<Constant>(CA->getOperand(i)));
1113   } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
1114     const StructLayout *SL = TD.getStructLayout(CS->getType());
1115     for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
1116       DSNode *NHN = NH.getNode();
1117       //Some programmers think ending a structure with a [0 x sbyte] is cute
1118       //This should be ok as the allocation type should grow this type when
1119       //it is merged in if it is bigger.
1120       if (SL->MemberOffsets[i] < SL->StructSize) {
1121         DSNodeHandle NewNH(NHN, NH.getOffset()+(unsigned)SL->MemberOffsets[i]);
1122         MergeConstantInitIntoNode(NewNH, cast<Constant>(CS->getOperand(i)));
1123       } else if (SL->MemberOffsets[i] == SL->StructSize) {
1124         DEBUG(std::cerr << "Zero size element at end of struct\n");
1125       } else {
1126         assert(0 && "type was smaller than offsets of of struct layout indicate");
1127       }
1128     }
1129   } else if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) {
1130     // Noop
1131   } else {
1132     assert(0 && "Unknown constant type!");
1133   }
1134 }
1135
1136 void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) {
1137   assert(!GV->isExternal() && "Cannot merge in external global!");
1138   // Get a node handle to the global node and merge the initializer into it.
1139   DSNodeHandle NH = getValueDest(*GV);
1140   MergeConstantInitIntoNode(NH, GV->getInitializer());
1141 }
1142
1143
1144 /// BuildGlobalECs - Look at all of the nodes in the globals graph.  If any node
1145 /// contains multiple globals, DSA will never, ever, be able to tell the globals
1146 /// apart.  Instead of maintaining this information in all of the graphs
1147 /// throughout the entire program, store only a single global (the "leader") in
1148 /// the graphs, and build equivalence classes for the rest of the globals.
1149 static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) {
1150   DSScalarMap &SM = GG.getScalarMap();
1151   EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs();
1152   for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end();
1153        I != E; ++I) {
1154     if (I->getGlobalsList().size() <= 1) continue;
1155
1156     // First, build up the equivalence set for this block of globals.
1157     const std::vector<GlobalValue*> &GVs = I->getGlobalsList();
1158     GlobalValue *First = GVs[0];
1159     for (unsigned i = 1, e = GVs.size(); i != e; ++i)
1160       GlobalECs.unionSets(First, GVs[i]);
1161
1162     // Next, get the leader element.
1163     assert(First == GlobalECs.getLeaderValue(First) &&
1164            "First did not end up being the leader?");
1165
1166     // Next, remove all globals from the scalar map that are not the leader.
1167     assert(GVs[0] == First && "First had to be at the front!");
1168     for (unsigned i = 1, e = GVs.size(); i != e; ++i) {
1169       ECGlobals.insert(GVs[i]);
1170       SM.erase(SM.find(GVs[i]));
1171     }
1172
1173     // Finally, change the global node to only contain the leader.
1174     I->clearGlobals();
1175     I->addGlobal(First);
1176   }
1177
1178   DEBUG(GG.AssertGraphOK());
1179 }
1180
1181 /// EliminateUsesOfECGlobals - Once we have determined that some globals are in
1182 /// really just equivalent to some other globals, remove the globals from the
1183 /// specified DSGraph (if present), and merge any nodes with their leader nodes.
1184 static void EliminateUsesOfECGlobals(DSGraph &G,
1185                                      const std::set<GlobalValue*> &ECGlobals) {
1186   DSScalarMap &SM = G.getScalarMap();
1187   EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs();
1188
1189   bool MadeChange = false;
1190   for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end();
1191        GI != E; ) {
1192     GlobalValue *GV = *GI++;
1193     if (!ECGlobals.count(GV)) continue;
1194
1195     const DSNodeHandle &GVNH = SM[GV];
1196     assert(!GVNH.isNull() && "Global has null NH!?");
1197
1198     // Okay, this global is in some equivalence class.  Start by finding the
1199     // leader of the class.
1200     GlobalValue *Leader = GlobalECs.getLeaderValue(GV);
1201
1202     // If the leader isn't already in the graph, insert it into the node
1203     // corresponding to GV.
1204     if (!SM.global_count(Leader)) {
1205       GVNH.getNode()->addGlobal(Leader);
1206       SM[Leader] = GVNH;
1207     } else {
1208       // Otherwise, the leader is in the graph, make sure the nodes are the
1209       // merged in the specified graph.
1210       const DSNodeHandle &LNH = SM[Leader];
1211       if (LNH.getNode() != GVNH.getNode())
1212         LNH.mergeWith(GVNH);
1213     }
1214
1215     // Next step, remove the global from the DSNode.
1216     GVNH.getNode()->removeGlobal(GV);
1217
1218     // Finally, remove the global from the ScalarMap.
1219     SM.erase(GV);
1220     MadeChange = true;
1221   }
1222
1223   DEBUG(if(MadeChange) G.AssertGraphOK());
1224 }
1225
1226 bool LocalDataStructures::runOnModule(Module &M) {
1227   const TargetData &TD = getAnalysis<TargetData>();
1228
1229   // First step, build the globals graph.
1230   GlobalsGraph = new DSGraph(GlobalECs, TD);
1231   {
1232     GraphBuilder GGB(*GlobalsGraph);
1233
1234     // Add initializers for all of the globals to the globals graph.
1235     for (Module::global_iterator I = M.global_begin(), E = M.global_end();
1236          I != E; ++I)
1237       if (!I->isExternal())
1238         GGB.mergeInGlobalInitializer(I);
1239   }
1240
1241   // Next step, iterate through the nodes in the globals graph, unioning
1242   // together the globals into equivalence classes.
1243   std::set<GlobalValue*> ECGlobals;
1244   BuildGlobalECs(*GlobalsGraph, ECGlobals);
1245   DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n");
1246   ECGlobals.clear();
1247
1248   // Calculate all of the graphs...
1249   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1250     if (!I->isExternal())
1251       DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I,
1252                                                   GlobalsGraph)));
1253
1254   GlobalsGraph->removeTriviallyDeadNodes();
1255   GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs);
1256
1257   // Now that we've computed all of the graphs, and merged all of the info into
1258   // the globals graph, see if we have further constrained the globals in the
1259   // program if so, update GlobalECs and remove the extraneous globals from the
1260   // program.
1261   BuildGlobalECs(*GlobalsGraph, ECGlobals);
1262   if (!ECGlobals.empty()) {
1263     DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n");
1264     for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
1265            E = DSInfo.end(); I != E; ++I)
1266       EliminateUsesOfECGlobals(*I->second, ECGlobals);
1267   }
1268
1269   return false;
1270 }
1271
1272 // releaseMemory - If the pass pipeline is done with this pass, we can release
1273 // our memory... here...
1274 //
1275 void LocalDataStructures::releaseMemory() {
1276   for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
1277          E = DSInfo.end(); I != E; ++I) {
1278     I->second->getReturnNodes().erase(I->first);
1279     if (I->second->getReturnNodes().empty())
1280       delete I->second;
1281   }
1282
1283   // Empty map so next time memory is released, data structures are not
1284   // re-deleted.
1285   DSInfo.clear();
1286   delete GlobalsGraph;
1287   GlobalsGraph = 0;
1288 }
1289