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