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.h"
  16 #include "llvm/Analysis/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 "Support/CommandLine.h"
  25 #include "Support/Debug.h"
  26 #include "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",
  41          cl::desc("If this is set, track integers as potential pointers"));
  42
  43 namespace llvm {
  44 namespace DS {
  45   // isPointerType - Return true if this type is big enough to hold a pointer.
  46   bool isPointerType(const Type *Ty) {
  47     if (isa<PointerType>(Ty))
  48       return true;
  49     else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger())
  50       return Ty->getPrimitiveSize() >= PointerSize;
  51     return false;
  52   }
  53 }}
  54
  55 using namespace DS;
  56
  57 namespace {
  58   cl::opt<bool>
  59   DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden,
  60                        cl::desc("Disable direct call optimization in "
  61                                 "DSGraph construction"));
  62   cl::opt<bool>
  63   DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden,
  64                           cl::desc("Disable field sensitivity in DSGraphs"));
  65
  66   //===--------------------------------------------------------------------===//
  67   //  GraphBuilder Class
  68   //===--------------------------------------------------------------------===//
  69   //
  70   /// This class is the builder class that constructs the local data structure
  71   /// graph by performing a single pass over the function in question.
  72   ///
  73   class GraphBuilder : InstVisitor<GraphBuilder> {
  74     DSGraph &G;
  75     DSNodeHandle *RetNode;               // Node that gets returned...
  76     DSScalarMap &ScalarMap;
  77     std::vector<DSCallSite> *FunctionCalls;
  78
  79   public:
  80     GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode,
  81                  std::vector<DSCallSite> &fc)
  82       : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()),
  83         FunctionCalls(&fc) {
  84
  85       // Create scalar nodes for all pointer arguments...
  86       for (Function::aiterator I = f.abegin(), E = f.aend(); I != E; ++I)
  87         if (isPointerType(I->getType()))
  88           getValueDest(*I);
  89
  90       visit(f);  // Single pass over the function
  91     }
  92
  93     // GraphBuilder ctor for working on the globals graph
  94     GraphBuilder(DSGraph &g)
  95       : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) {
  96     }
  97
  98     void mergeInGlobalInitializer(GlobalVariable *GV);
  99
 100   private:
 101     // Visitor functions, used to handle each instruction type we encounter...
 102     friend class InstVisitor<GraphBuilder>;
 103     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); }
 104     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); }
 105     void handleAlloc(AllocationInst &AI, bool isHeap);
 106
 107     void visitPHINode(PHINode &PN);
 108
 109     void visitGetElementPtrInst(User &GEP);
 110     void visitReturnInst(ReturnInst &RI);
 111     void visitLoadInst(LoadInst &LI);
 112     void visitStoreInst(StoreInst &SI);
 113     void visitCallInst(CallInst &CI);
 114     void visitInvokeInst(InvokeInst &II);
 115     void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
 116     void visitFreeInst(FreeInst &FI);
 117     void visitCastInst(CastInst &CI);
 118     void visitInstruction(Instruction &I);
 119
 120     void visitCallSite(CallSite CS);
 121     void visitVANextInst(VANextInst &I);
 122     void visitVAArgInst(VAArgInst   &I);
 123
 124     void MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C);
 125   private:
 126     // Helper functions used to implement the visitation functions...
 127
 128     /// createNode - Create a new DSNode, ensuring that it is properly added to
 129     /// the graph.
 130     ///
 131     DSNode *createNode(const Type *Ty = 0) {
 132       DSNode *N = new DSNode(Ty, &G);   // Create the node
 133       if (DisableFieldSensitivity) {
 134         // Create node handle referring to the old node so that it is
 135         // immediately removed from the graph when the node handle is destroyed.
 136         DSNodeHandle OldNNH = N;
 137         N->foldNodeCompletely();
 138         if (DSNode *FN = N->getForwardNode())
 139           N = FN;
 140       }
 141       return N;
 142     }
 143
 144     /// setDestTo - Set the ScalarMap entry for the specified value to point to
 145     /// the specified destination.  If the Value already points to a node, make
 146     /// sure to merge the two destinations together.
 147     ///
 148     void setDestTo(Value &V, const DSNodeHandle &NH);
 149
 150     /// getValueDest - Return the DSNode that the actual value points to.
 151     ///
 152     DSNodeHandle getValueDest(Value &V);
 153
 154     /// getLink - This method is used to return the specified link in the
 155     /// specified node if one exists.  If a link does not already exist (it's
 156     /// null), then we create a new node, link it, then return it.
 157     ///
 158     DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0);
 159   };
 160 }
 161
 162 using namespace DS;
 163
 164 //===----------------------------------------------------------------------===//
 165 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 166 // graph.
 167 DSGraph::DSGraph(const TargetData &td, Function &F, DSGraph *GG)
 168   : GlobalsGraph(GG), TD(td) {
 169   PrintAuxCalls = false;
 170
 171   DEBUG(std::cerr << "  [Loc] Calculating graph for: " << F.getName() << "\n");
 172
 173   // Use the graph builder to construct the local version of the graph
 174   GraphBuilder B(F, *this, ReturnNodes[&F], FunctionCalls);
 175 #ifndef NDEBUG
 176   Timer::addPeakMemoryMeasurement();
 177 #endif
 178
 179   // Remove all integral constants from the scalarmap!
 180   for (DSScalarMap::iterator I = ScalarMap.begin(); I != ScalarMap.end();)
 181     if (isa<ConstantIntegral>(I->first))
 182       ScalarMap.erase(I++);
 183     else
 184       ++I;
 185
 186   // If there are any constant globals referenced in this function, merge their
 187   // initializers into the local graph from the globals graph.
 188   if (ScalarMap.global_begin() != ScalarMap.global_end()) {
 189     ReachabilityCloner RC(*this, *GG, 0);
 190
 191     for (DSScalarMap::global_iterator I = ScalarMap.global_begin();
 192          I != ScalarMap.global_end(); ++I)
 193       if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I))
 194         if (!GV->isExternal() && GV->isConstant())
 195           RC.merge(ScalarMap[GV], GG->ScalarMap[GV]);
 196   }
 197
 198   markIncompleteNodes(DSGraph::MarkFormalArgs);
 199
 200   // Remove any nodes made dead due to merging...
 201   removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 202 }
 203
 204
 205 //===----------------------------------------------------------------------===//
 206 // Helper method implementations...
 207 //
 208
 209 /// getValueDest - Return the DSNode that the actual value points to.
 210 ///
 211 DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
 212   Value *V = &Val;
 213   if (V == Constant::getNullValue(V->getType()))
 214     return 0;  // Null doesn't point to anything, don't add to ScalarMap!
 215
 216   DSNodeHandle &NH = ScalarMap[V];
 217   if (NH.getNode())
 218     return NH;     // Already have a node?  Just return it...
 219
 220   // Otherwise we need to create a new node to point to.
 221   // Check first for constant expressions that must be traversed to
 222   // extract the actual value.
 223   if (Constant *C = dyn_cast<Constant>(V))
 224     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 225       return NH = getValueDest(*CPR->getValue());
 226     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 227       if (CE->getOpcode() == Instruction::Cast)
 228         NH = getValueDest(*CE->getOperand(0));
 229       else if (CE->getOpcode() == Instruction::GetElementPtr) {
 230         visitGetElementPtrInst(*CE);
 231         DSScalarMap::iterator I = ScalarMap.find(CE);
 232         assert(I != ScalarMap.end() && "GEP didn't get processed right?");
 233         NH = I->second;
 234       } else {
 235         // This returns a conservative unknown node for any unhandled ConstExpr
 236         return NH = createNode()->setUnknownNodeMarker();
 237       }
 238       if (NH.getNode() == 0) {  // (getelementptr null, X) returns null
 239         ScalarMap.erase(V);
 240         return 0;
 241       }
 242       return NH;
 243
 244     } else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C)) {
 245       // Random constants are unknown mem
 246       return NH = createNode()->setUnknownNodeMarker();
 247     } else {
 248       assert(0 && "Unknown constant type!");
 249     }
 250
 251   // Otherwise we need to create a new node to point to...
 252   DSNode *N;
 253   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 254     // Create a new global node for this global variable...
 255     N = createNode(GV->getType()->getElementType());
 256     N->addGlobal(GV);
 257   } else {
 258     // Otherwise just create a shadow node
 259     N = createNode();
 260   }
 261
 262   NH.setNode(N);      // Remember that we are pointing to it...
 263   NH.setOffset(0);
 264   return NH;
 265 }
 266
 267
 268 /// getLink - This method is used to return the specified link in the
 269 /// specified node if one exists.  If a link does not already exist (it's
 270 /// null), then we create a new node, link it, then return it.  We must
 271 /// specify the type of the Node field we are accessing so that we know what
 272 /// type should be linked to if we need to create a new node.
 273 ///
 274 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) {
 275   DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
 276   DSNodeHandle &Link = Node.getLink(LinkNo);
 277   if (!Link.getNode()) {
 278     // If the link hasn't been created yet, make and return a new shadow node
 279     Link = createNode();
 280   }
 281   return Link;
 282 }
 283
 284
 285 /// setDestTo - Set the ScalarMap entry for the specified value to point to the
 286 /// specified destination.  If the Value already points to a node, make sure to
 287 /// merge the two destinations together.
 288 ///
 289 void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) {
 290   ScalarMap[&V].mergeWith(NH);
 291 }
 292
 293
 294 //===----------------------------------------------------------------------===//
 295 // Specific instruction type handler implementations...
 296 //
 297
 298 /// Alloca & Malloc instruction implementation - Simply create a new memory
 299 /// object, pointing the scalar to it.
 300 ///
 301 void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) {
 302   DSNode *N = createNode();
 303   if (isHeap)
 304     N->setHeapNodeMarker();
 305   else
 306     N->setAllocaNodeMarker();
 307   setDestTo(AI, N);
 308 }
 309
 310 // PHINode - Make the scalar for the PHI node point to all of the things the
 311 // incoming values point to... which effectively causes them to be merged.
 312 //
 313 void GraphBuilder::visitPHINode(PHINode &PN) {
 314   if (!isPointerType(PN.getType())) return; // Only pointer PHIs
 315
 316   DSNodeHandle &PNDest = ScalarMap[&PN];
 317   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 318     PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
 319 }
 320
 321 void GraphBuilder::visitGetElementPtrInst(User &GEP) {
 322   DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
 323   if (Value.getNode() == 0) return;
 324
 325   // As a special case, if all of the index operands of GEP are constant zeros,
 326   // handle this just like we handle casts (ie, don't do much).
 327   bool AllZeros = true;
 328   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
 329     if (GEP.getOperand(i) !=
 330            Constant::getNullValue(GEP.getOperand(i)->getType())) {
 331       AllZeros = false;
 332       break;
 333     }
 334
 335   // If all of the indices are zero, the result points to the operand without
 336   // applying the type.
 337   if (AllZeros) {
 338     setDestTo(GEP, Value);
 339     return;
 340   }
 341
 342
 343   const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType());
 344   const Type *CurTy = PTy->getElementType();
 345
 346   if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) {
 347     // If the node had to be folded... exit quickly
 348     setDestTo(GEP, Value);  // GEP result points to folded node
 349     return;
 350   }
 351
 352   const TargetData &TD = Value.getNode()->getTargetData();
 353
 354 #if 0
 355   // Handle the pointer index specially...
 356   if (GEP.getNumOperands() > 1 &&
 357       (!isa<Constant>(GEP.getOperand(1)) ||
 358        !cast<Constant>(GEP.getOperand(1))->isNullValue())) {
 359
 360     // If we already know this is an array being accessed, don't do anything...
 361     if (!TopTypeRec.isArray) {
 362       TopTypeRec.isArray = true;
 363
 364       // If we are treating some inner field pointer as an array, fold the node
 365       // up because we cannot handle it right.  This can come because of
 366       // something like this:  &((&Pt->X)[1]) == &Pt->Y
 367       //
 368       if (Value.getOffset()) {
 369         // Value is now the pointer we want to GEP to be...
 370         Value.getNode()->foldNodeCompletely();
 371         setDestTo(GEP, Value);  // GEP result points to folded node
 372         return;
 373       } else {
 374         // This is a pointer to the first byte of the node.  Make sure that we
 375         // are pointing to the outter most type in the node.
 376         // FIXME: We need to check one more case here...
 377       }
 378     }
 379   }
 380 #endif
 381
 382   // All of these subscripts are indexing INTO the elements we have...
 383   unsigned Offset = 0;
 384   for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
 385        I != E; ++I)
 386     if (const StructType *STy = dyn_cast<StructType>(*I)) {
 387       unsigned FieldNo = cast<ConstantUInt>(I.getOperand())->getValue();
 388       Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
 389     } else if (const PointerType *PTy = dyn_cast<PointerType>(*I)) {
 390       if (!isa<Constant>(I.getOperand()) ||
 391           !cast<Constant>(I.getOperand())->isNullValue())
 392         Value.getNode()->setArrayMarker();
 393     }
 394
 395
 396 #if 0
 397     if (const SequentialType *STy = cast<SequentialType>(*I)) {
 398       CurTy = STy->getElementType();
 399       if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
 400         Offset += CS->getValue()*TD.getTypeSize(CurTy);
 401       } else {
 402         // Variable index into a node.  We must merge all of the elements of the
 403         // sequential type here.
 404         if (isa<PointerType>(STy))
 405           std::cerr << "Pointer indexing not handled yet!\n";
 406         else {
 407           const ArrayType *ATy = cast<ArrayType>(STy);
 408           unsigned ElSize = TD.getTypeSize(CurTy);
 409           DSNode *N = Value.getNode();
 410           assert(N && "Value must have a node!");
 411           unsigned RawOffset = Offset+Value.getOffset();
 412
 413           // Loop over all of the elements of the array, merging them into the
 414           // zeroth element.
 415           for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
 416             // Merge all of the byte components of this array element
 417             for (unsigned j = 0; j != ElSize; ++j)
 418               N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
 419         }
 420       }
 421     }
 422 #endif
 423
 424   // Add in the offset calculated...
 425   Value.setOffset(Value.getOffset()+Offset);
 426
 427   // Value is now the pointer we want to GEP to be...
 428   setDestTo(GEP, Value);
 429 }
 430
 431 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 432   DSNodeHandle Ptr = getValueDest(*LI.getOperand(0));
 433   if (Ptr.getNode() == 0) return;
 434
 435   // Make that the node is read from...
 436   Ptr.getNode()->setReadMarker();
 437
 438   // Ensure a typerecord exists...
 439   Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false);
 440
 441   if (isPointerType(LI.getType()))
 442     setDestTo(LI, getLink(Ptr));
 443 }
 444
 445 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 446   const Type *StoredTy = SI.getOperand(0)->getType();
 447   DSNodeHandle Dest = getValueDest(*SI.getOperand(1));
 448   if (Dest.isNull()) return;
 449
 450   // Mark that the node is written to...
 451   Dest.getNode()->setModifiedMarker();
 452
 453   // Ensure a type-record exists...
 454   Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset());
 455
 456   // Avoid adding edges from null, or processing non-"pointer" stores
 457   if (isPointerType(StoredTy))
 458     Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
 459 }
 460
 461 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 462   if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()))
 463     RetNode->mergeWith(getValueDest(*RI.getOperand(0)));
 464 }
 465
 466 void GraphBuilder::visitVANextInst(VANextInst &I) {
 467   getValueDest(*I.getOperand(0)).mergeWith(getValueDest(I));
 468 }
 469
 470 void GraphBuilder::visitVAArgInst(VAArgInst &I) {
 471   DSNodeHandle Ptr = getValueDest(*I.getOperand(0));
 472   if (Ptr.isNull()) return;
 473
 474   // Make that the node is read from.
 475   Ptr.getNode()->setReadMarker();
 476
 477   // Ensure a typerecord exists...
 478   Ptr.getNode()->mergeTypeInfo(I.getType(), Ptr.getOffset(), false);
 479
 480   if (isPointerType(I.getType()))
 481     setDestTo(I, getLink(Ptr));
 482 }
 483
 484
 485 void GraphBuilder::visitCallInst(CallInst &CI) {
 486   visitCallSite(&CI);
 487 }
 488
 489 void GraphBuilder::visitInvokeInst(InvokeInst &II) {
 490   visitCallSite(&II);
 491 }
 492
 493 void GraphBuilder::visitCallSite(CallSite CS) {
 494   Value *Callee = CS.getCalledValue();
 495   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Callee))
 496     Callee = CPR->getValue();
 497
 498   // Special case handling of certain libc allocation functions here.
 499   if (Function *F = dyn_cast<Function>(Callee))
 500     if (F->isExternal())
 501       switch (F->getIntrinsicID()) {
 502       case Intrinsic::vastart:
 503         getValueDest(*CS.getInstruction()).getNode()->setAllocaNodeMarker();
 504         return;
 505       case Intrinsic::vacopy:
 506         getValueDest(*CS.getInstruction()).
 507           mergeWith(getValueDest(**(CS.arg_begin())));
 508         return;
 509       case Intrinsic::vaend:
 510         return;  // noop
 511       case Intrinsic::memmove:
 512       case Intrinsic::memcpy: {
 513         // Merge the first & second arguments, and mark the memory read and
 514         // modified.
 515         DSNodeHandle RetNH = getValueDest(**CS.arg_begin());
 516         RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1)));
 517         if (DSNode *N = RetNH.getNode())
 518           N->setModifiedMarker()->setReadMarker();
 519         return;
 520       }
 521       case Intrinsic::memset:
 522         // Mark the memory modified.
 523         if (DSNode *N = getValueDest(**CS.arg_begin()).getNode())
 524           N->setModifiedMarker();
 525         return;
 526       default:
 527         if (F->getName() == "calloc" || F->getName() == "posix_memalign" ||
 528             F->getName() == "memalign" || F->getName() == "valloc") {
 529           setDestTo(*CS.getInstruction(),
 530                     createNode()->setHeapNodeMarker()->setModifiedMarker());
 531           return;
 532         } else if (F->getName() == "realloc") {
 533           DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
 534           RetNH.mergeWith(getValueDest(**CS.arg_begin()));
 535           if (DSNode *N = RetNH.getNode())
 536             N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
 537           return;
 538         } else if (F->getName() == "memmove") {
 539           // Merge the first & second arguments, and mark the memory read and
 540           // modified.
 541           DSNodeHandle RetNH = getValueDest(**CS.arg_begin());
 542           RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1)));
 543           if (DSNode *N = RetNH.getNode())
 544             N->setModifiedMarker()->setReadMarker();
 545           return;
 546
 547         } else if (F->getName() == "atoi" || F->getName() == "atof" ||
 548                    F->getName() == "atol" || F->getName() == "atoll" ||
 549                    F->getName() == "remove" || F->getName() == "unlink" ||
 550                    F->getName() == "rename" || F->getName() == "memcmp" ||
 551                    F->getName() == "strcmp" || F->getName() == "strncmp" ||
 552                    F->getName() == "execl" || F->getName() == "execlp" ||
 553                    F->getName() == "execle" || F->getName() == "execv" ||
 554                    F->getName() == "execvp" || F->getName() == "chmod" ||
 555                    F->getName() == "puts" || F->getName() == "write" ||
 556                    F->getName() == "open" || F->getName() == "create" ||
 557                    F->getName() == "truncate" || F->getName() == "chdir" ||
 558                    F->getName() == "mkdir" || F->getName() == "rmdir") {
 559           // These functions read all of their pointer operands.
 560           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 561                AI != E; ++AI) {
 562             if (isPointerType((*AI)->getType()))
 563               if (DSNode *N = getValueDest(**AI).getNode())
 564                 N->setReadMarker();
 565           }
 566           return;
 567         } else if (F->getName() == "read" || F->getName() == "pipe" ||
 568                    F->getName() == "wait" || F->getName() == "time") {
 569           // These functions write all of their pointer operands.
 570           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 571                AI != E; ++AI) {
 572             if (isPointerType((*AI)->getType()))
 573               if (DSNode *N = getValueDest(**AI).getNode())
 574                 N->setModifiedMarker();
 575           }
 576           return;
 577         } else if (F->getName() == "stat" || F->getName() == "fstat" ||
 578                    F->getName() == "lstat") {
 579           // These functions read their first operand if its a pointer.
 580           CallSite::arg_iterator AI = CS.arg_begin();
 581           if (isPointerType((*AI)->getType())) {
 582             DSNodeHandle Path = getValueDest(**AI);
 583             if (DSNode *N = Path.getNode()) N->setReadMarker();
 584           }
 585
 586           // Then they write into the stat buffer.
 587           DSNodeHandle StatBuf = getValueDest(**++AI);
 588           if (DSNode *N = StatBuf.getNode()) {
 589             N->setModifiedMarker();
 590             const Type *StatTy = F->getFunctionType()->getParamType(1);
 591             if (const PointerType *PTy = dyn_cast<PointerType>(StatTy))
 592               N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset());
 593           }
 594           return;
 595         } else if (F->getName() == "strtod" || F->getName() == "strtof" ||
 596                    F->getName() == "strtold") {
 597           // These functions read the first pointer
 598           if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) {
 599             Str->setReadMarker();
 600             // If the second parameter is passed, it will point to the first
 601             // argument node.
 602             const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1));
 603             if (DSNode *End = EndPtrNH.getNode()) {
 604               End->mergeTypeInfo(PointerType::get(Type::SByteTy),
 605                                  EndPtrNH.getOffset(), false);
 606               End->setModifiedMarker();
 607               DSNodeHandle &Link = getLink(EndPtrNH);
 608               Link.mergeWith(getValueDest(**CS.arg_begin()));
 609             }
 610           }
 611
 612           return;
 613         } else if (F->getName() == "fopen" || F->getName() == "fdopen" ||
 614                    F->getName() == "freopen") {
 615           // These functions read all of their pointer operands.
 616           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 617                AI != E; ++AI)
 618             if (isPointerType((*AI)->getType()))
 619               if (DSNode *N = getValueDest(**AI).getNode())
 620                 N->setReadMarker();
 621
 622           // fopen allocates in an unknown way and writes to the file
 623           // descriptor.  Also, merge the allocated type into the node.
 624           DSNodeHandle Result = getValueDest(*CS.getInstruction());
 625           if (DSNode *N = Result.getNode()) {
 626             N->setModifiedMarker()->setUnknownNodeMarker();
 627             const Type *RetTy = F->getFunctionType()->getReturnType();
 628             if (const PointerType *PTy = dyn_cast<PointerType>(RetTy))
 629               N->mergeTypeInfo(PTy->getElementType(), Result.getOffset());
 630           }
 631
 632           // If this is freopen, merge the file descriptor passed in with the
 633           // result.
 634           if (F->getName() == "freopen")
 635             Result.mergeWith(getValueDest(**--CS.arg_end()));
 636
 637           return;
 638         } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){
 639           // fclose reads and deallocates the memory in an unknown way for the
 640           // file descriptor.  It merges the FILE type into the descriptor.
 641           DSNodeHandle H = getValueDest(**CS.arg_begin());
 642           if (DSNode *N = H.getNode()) {
 643             N->setReadMarker()->setUnknownNodeMarker();
 644             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 645             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 646               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 647           }
 648           return;
 649         } else if (CS.arg_end()-CS.arg_begin() == 1 &&
 650                    (F->getName() == "fflush" || F->getName() == "feof" ||
 651                     F->getName() == "fileno" || F->getName() == "clearerr" ||
 652                     F->getName() == "rewind" || F->getName() == "ftell" ||
 653                     F->getName() == "ferror" || F->getName() == "fgetc" ||
 654                     F->getName() == "fgetc" || F->getName() == "_IO_getc")) {
 655           // fflush reads and writes the memory for the file descriptor.  It
 656           // merges the FILE type into the descriptor.
 657           DSNodeHandle H = getValueDest(**CS.arg_begin());
 658           if (DSNode *N = H.getNode()) {
 659             N->setReadMarker()->setModifiedMarker();
 660
 661             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 662             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 663               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 664           }
 665           return;
 666         } else if (CS.arg_end()-CS.arg_begin() == 4 &&
 667                    (F->getName() == "fwrite" || F->getName() == "fread")) {
 668           // fread writes the first operand, fwrite reads it.  They both
 669           // read/write the FILE descriptor, and merges the FILE type.
 670           DSNodeHandle H = getValueDest(**--CS.arg_end());
 671           if (DSNode *N = H.getNode()) {
 672             N->setReadMarker()->setModifiedMarker();
 673             const Type *ArgTy = F->getFunctionType()->getParamType(3);
 674             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 675               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 676           }
 677
 678           H = getValueDest(**CS.arg_begin());
 679           if (DSNode *N = H.getNode())
 680             if (F->getName() == "fwrite")
 681               N->setReadMarker();
 682             else
 683               N->setModifiedMarker();
 684           return;
 685         } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){
 686           // fgets reads and writes the memory for the file descriptor.  It
 687           // merges the FILE type into the descriptor, and writes to the
 688           // argument.  It returns the argument as well.
 689           CallSite::arg_iterator AI = CS.arg_begin();
 690           DSNodeHandle H = getValueDest(**AI);
 691           if (DSNode *N = H.getNode())
 692             N->setModifiedMarker();                        // Writes buffer
 693           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 694           ++AI; ++AI;
 695
 696           // Reads and writes file descriptor, merge in FILE type.
 697           H = getValueDest(**AI);
 698           if (DSNode *N = H.getNode()) {
 699             N->setReadMarker()->setModifiedMarker();
 700             const Type *ArgTy = F->getFunctionType()->getParamType(2);
 701             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 702               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 703           }
 704           return;
 705         } else if (F->getName() == "ungetc" || F->getName() == "fputc" ||
 706                    F->getName() == "fputs" || F->getName() == "putc" ||
 707                    F->getName() == "ftell" || F->getName() == "rewind" ||
 708                    F->getName() == "_IO_putc") {
 709           // These functions read and write the memory for the file descriptor,
 710           // which is passes as the last argument.
 711           DSNodeHandle H = getValueDest(**--CS.arg_end());
 712           if (DSNode *N = H.getNode()) {
 713             N->setReadMarker()->setModifiedMarker();
 714             const Type *ArgTy = *--F->getFunctionType()->param_end();
 715             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 716               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 717           }
 718
 719           // Any pointer arguments are read.
 720           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 721                AI != E; ++AI)
 722             if (isPointerType((*AI)->getType()))
 723               if (DSNode *N = getValueDest(**AI).getNode())
 724                 N->setReadMarker();
 725           return;
 726         } else if (F->getName() == "fseek" || F->getName() == "fgetpos" ||
 727                    F->getName() == "fsetpos") {
 728           // These functions read and write the memory for the file descriptor,
 729           // and read/write all other arguments.
 730           DSNodeHandle H = getValueDest(**CS.arg_begin());
 731           if (DSNode *N = H.getNode()) {
 732             const Type *ArgTy = *--F->getFunctionType()->param_end();
 733             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 734               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 735           }
 736
 737           // Any pointer arguments are read.
 738           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 739                AI != E; ++AI)
 740             if (isPointerType((*AI)->getType()))
 741               if (DSNode *N = getValueDest(**AI).getNode())
 742                 N->setReadMarker()->setModifiedMarker();
 743           return;
 744         } else if (F->getName() == "printf" || F->getName() == "fprintf" ||
 745                    F->getName() == "sprintf") {
 746           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 747
 748           if (F->getName() == "fprintf") {
 749             // fprintf reads and writes the FILE argument, and applies the type
 750             // to it.
 751             DSNodeHandle H = getValueDest(**AI);
 752             if (DSNode *N = H.getNode()) {
 753               N->setModifiedMarker();
 754               const Type *ArgTy = (*AI)->getType();
 755               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 756                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 757             }
 758           } else if (F->getName() == "sprintf") {
 759             // sprintf writes the first string argument.
 760             DSNodeHandle H = getValueDest(**AI++);
 761             if (DSNode *N = H.getNode()) {
 762               N->setModifiedMarker();
 763               const Type *ArgTy = (*AI)->getType();
 764               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 765                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 766             }
 767           }
 768
 769           for (; AI != E; ++AI) {
 770             // printf reads all pointer arguments.
 771             if (isPointerType((*AI)->getType()))
 772               if (DSNode *N = getValueDest(**AI).getNode())
 773                 N->setReadMarker();
 774           }
 775           return;
 776         } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" ||
 777                    F->getName() == "vsprintf") {
 778           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 779
 780           if (F->getName() == "vfprintf") {
 781             // ffprintf reads and writes the FILE argument, and applies the type
 782             // to it.
 783             DSNodeHandle H = getValueDest(**AI);
 784             if (DSNode *N = H.getNode()) {
 785               N->setModifiedMarker()->setReadMarker();
 786               const Type *ArgTy = (*AI)->getType();
 787               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 788                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 789             }
 790             ++AI;
 791           } else if (F->getName() == "vsprintf") {
 792             // vsprintf writes the first string argument.
 793             DSNodeHandle H = getValueDest(**AI++);
 794             if (DSNode *N = H.getNode()) {
 795               N->setModifiedMarker();
 796               const Type *ArgTy = (*AI)->getType();
 797               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 798                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 799             }
 800           }
 801
 802           // Read the format
 803           if (AI != E) {
 804             if (isPointerType((*AI)->getType()))
 805               if (DSNode *N = getValueDest(**AI).getNode())
 806                 N->setReadMarker();
 807             ++AI;
 808           }
 809
 810           // Read the valist, and the pointed-to objects.
 811           if (AI != E && isPointerType((*AI)->getType())) {
 812             const DSNodeHandle &VAList = getValueDest(**AI);
 813             if (DSNode *N = VAList.getNode()) {
 814               N->setReadMarker();
 815               N->mergeTypeInfo(PointerType::get(Type::SByteTy),
 816                                VAList.getOffset(), false);
 817
 818               DSNodeHandle &VAListObjs = getLink(VAList);
 819               VAListObjs.getNode()->setReadMarker();
 820             }
 821           }
 822
 823           return;
 824         } else if (F->getName() == "scanf" || F->getName() == "fscanf" ||
 825                    F->getName() == "sscanf") {
 826           CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 827
 828           if (F->getName() == "fscanf") {
 829             // fscanf reads and writes the FILE argument, and applies the type
 830             // to it.
 831             DSNodeHandle H = getValueDest(**AI);
 832             if (DSNode *N = H.getNode()) {
 833               N->setReadMarker();
 834               const Type *ArgTy = (*AI)->getType();
 835               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 836                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 837             }
 838           } else if (F->getName() == "sscanf") {
 839             // sscanf reads the first string argument.
 840             DSNodeHandle H = getValueDest(**AI++);
 841             if (DSNode *N = H.getNode()) {
 842               N->setReadMarker();
 843               const Type *ArgTy = (*AI)->getType();
 844               if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 845                 N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 846             }
 847           }
 848
 849           for (; AI != E; ++AI) {
 850             // scanf writes all pointer arguments.
 851             if (isPointerType((*AI)->getType()))
 852               if (DSNode *N = getValueDest(**AI).getNode())
 853                 N->setModifiedMarker();
 854           }
 855           return;
 856         } else if (F->getName() == "strtok") {
 857           // strtok reads and writes the first argument, returning it.  It reads
 858           // its second arg.  FIXME: strtok also modifies some hidden static
 859           // data.  Someday this might matter.
 860           CallSite::arg_iterator AI = CS.arg_begin();
 861           DSNodeHandle H = getValueDest(**AI++);
 862           if (DSNode *N = H.getNode()) {
 863             N->setReadMarker()->setModifiedMarker();      // Reads/Writes buffer
 864             const Type *ArgTy = F->getFunctionType()->getParamType(0);
 865             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 866               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 867           }
 868           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 869
 870           H = getValueDest(**AI);       // Reads delimiter
 871           if (DSNode *N = H.getNode()) {
 872             N->setReadMarker();
 873             const Type *ArgTy = F->getFunctionType()->getParamType(1);
 874             if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy))
 875               N->mergeTypeInfo(PTy->getElementType(), H.getOffset());
 876           }
 877           return;
 878         } else if (F->getName() == "strchr" || F->getName() == "strrchr" ||
 879                    F->getName() == "strstr") {
 880           // These read their arguments, and return the first one
 881           DSNodeHandle H = getValueDest(**CS.arg_begin());
 882           H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer
 883
 884           for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 885                AI != E; ++AI)
 886             if (isPointerType((*AI)->getType()))
 887               if (DSNode *N = getValueDest(**AI).getNode())
 888                 N->setReadMarker();
 889
 890           if (DSNode *N = H.getNode())
 891             N->setReadMarker();
 892           return;
 893         } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) {
 894           // This writes its second argument, and forces it to double.
 895           DSNodeHandle H = getValueDest(**--CS.arg_end());
 896           if (DSNode *N = H.getNode()) {
 897             N->setModifiedMarker();
 898             N->mergeTypeInfo(Type::DoubleTy, H.getOffset());
 899           }
 900           return;
 901         } else {
 902           // Unknown function, warn if it returns a pointer type or takes a
 903           // pointer argument.
 904           bool Warn = isPointerType(CS.getInstruction()->getType());
 905           if (!Warn)
 906             for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
 907                  I != E; ++I)
 908               if (isPointerType((*I)->getType())) {
 909                 Warn = true;
 910                 break;
 911               }
 912           if (Warn)
 913             std::cerr << "WARNING: Call to unknown external function '"
 914                       << F->getName() << "' will cause pessimistic results!\n";
 915         }
 916       }
 917
 918
 919   // Set up the return value...
 920   DSNodeHandle RetVal;
 921   Instruction *I = CS.getInstruction();
 922   if (isPointerType(I->getType()))
 923     RetVal = getValueDest(*I);
 924
 925   DSNode *CalleeNode = 0;
 926   if (DisableDirectCallOpt || !isa<Function>(Callee)) {
 927     CalleeNode = getValueDest(*Callee).getNode();
 928     if (CalleeNode == 0) {
 929       std::cerr << "WARNING: Program is calling through a null pointer?\n"<< *I;
 930       return;  // Calling a null pointer?
 931     }
 932   }
 933
 934   std::vector<DSNodeHandle> Args;
 935   Args.reserve(CS.arg_end()-CS.arg_begin());
 936
 937   // Calculate the arguments vector...
 938   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
 939     if (isPointerType((*I)->getType()))
 940       Args.push_back(getValueDest(**I));
 941
 942   // Add a new function call entry...
 943   if (CalleeNode)
 944     FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args));
 945   else
 946     FunctionCalls->push_back(DSCallSite(CS, RetVal, cast<Function>(Callee),
 947                                         Args));
 948 }
 949
 950 void GraphBuilder::visitFreeInst(FreeInst &FI) {
 951   // Mark that the node is written to...
 952   if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode())
 953     N->setModifiedMarker()->setHeapNodeMarker();
 954 }
 955
 956 /// Handle casts...
 957 void GraphBuilder::visitCastInst(CastInst &CI) {
 958   if (isPointerType(CI.getType()))
 959     if (isPointerType(CI.getOperand(0)->getType())) {
 960       // Cast one pointer to the other, just act like a copy instruction
 961       setDestTo(CI, getValueDest(*CI.getOperand(0)));
 962     } else {
 963       // Cast something (floating point, small integer) to a pointer.  We need
 964       // to track the fact that the node points to SOMETHING, just something we
 965       // don't know about.  Make an "Unknown" node.
 966       //
 967       setDestTo(CI, createNode()->setUnknownNodeMarker());
 968     }
 969 }
 970
 971
 972 // visitInstruction - For all other instruction types, if we have any arguments
 973 // that are of pointer type, make them have unknown composition bits, and merge
 974 // the nodes together.
 975 void GraphBuilder::visitInstruction(Instruction &Inst) {
 976   DSNodeHandle CurNode;
 977   if (isPointerType(Inst.getType()))
 978     CurNode = getValueDest(Inst);
 979   for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I)
 980     if (isPointerType((*I)->getType()))
 981       CurNode.mergeWith(getValueDest(**I));
 982
 983   if (CurNode.getNode())
 984     CurNode.getNode()->setUnknownNodeMarker();
 985 }
 986
 987
 988
 989 //===----------------------------------------------------------------------===//
 990 // LocalDataStructures Implementation
 991 //===----------------------------------------------------------------------===//
 992
 993 // MergeConstantInitIntoNode - Merge the specified constant into the node
 994 // pointed to by NH.
 995 void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) {
 996   // Ensure a type-record exists...
 997   NH.getNode()->mergeTypeInfo(C->getType(), NH.getOffset());
 998
 999   if (C->getType()->isFirstClassType()) {
1000     if (isPointerType(C->getType()))
1001       // Avoid adding edges from null, or processing non-"pointer" stores
1002       NH.addEdgeTo(getValueDest(*C));
1003     return;
1004   }
1005
1006   const TargetData &TD = NH.getNode()->getTargetData();
1007
1008   if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
1009     for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
1010       // We don't currently do any indexing for arrays...
1011       MergeConstantInitIntoNode(NH, cast<Constant>(CA->getOperand(i)));
1012   } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
1013     const StructLayout *SL = TD.getStructLayout(CS->getType());
1014     for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
1015       DSNodeHandle NewNH(NH.getNode(), NH.getOffset()+SL->MemberOffsets[i]);
1016       MergeConstantInitIntoNode(NewNH, cast<Constant>(CS->getOperand(i)));
1017     }
1018   } else if (ConstantAggregateZero *CAZ = dyn_cast<ConstantAggregateZero>(C)) {
1019     // Noop
1020   } else {
1021     assert(0 && "Unknown constant type!");
1022   }
1023 }
1024
1025 void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) {
1026   assert(!GV->isExternal() && "Cannot merge in external global!");
1027   // Get a node handle to the global node and merge the initializer into it.
1028   DSNodeHandle NH = getValueDest(*GV);
1029   MergeConstantInitIntoNode(NH, GV->getInitializer());
1030 }
1031
1032
1033 bool LocalDataStructures::run(Module &M) {
1034   GlobalsGraph = new DSGraph(getAnalysis<TargetData>());
1035
1036   const TargetData &TD = getAnalysis<TargetData>();
1037
1038   {
1039     GraphBuilder GGB(*GlobalsGraph);
1040
1041     // Add initializers for all of the globals to the globals graph...
1042     for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
1043       if (!I->isExternal())
1044         GGB.mergeInGlobalInitializer(I);
1045   }
1046
1047   // Calculate all of the graphs...
1048   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1049     if (!I->isExternal())
1050       DSInfo.insert(std::make_pair(I, new DSGraph(TD, *I, GlobalsGraph)));
1051
1052   GlobalsGraph->removeTriviallyDeadNodes();
1053   GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs);
1054   return false;
1055 }
1056
1057 // releaseMemory - If the pass pipeline is done with this pass, we can release
1058 // our memory... here...
1059 //
1060 void LocalDataStructures::releaseMemory() {
1061   for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
1062          E = DSInfo.end(); I != E; ++I) {
1063     I->second->getReturnNodes().erase(I->first);
1064     if (I->second->getReturnNodes().empty())
1065       delete I->second;
1066   }
1067
1068   // Empty map so next time memory is released, data structures are not
1069   // re-deleted.
1070   DSInfo.clear();
1071   delete GlobalsGraph;
1072   GlobalsGraph = 0;
1073 }
1074