lib/Analysis/DataStructure/Local.cpp

   1 //===- Local.cpp - Compute a local data structure graph for a function ----===//
   2 //
   3 // Compute the local version of the data structure graph for a function.  The
   4 // external interface to this file is the DSGraph constructor.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/Analysis/DataStructure.h"
   9 #include "llvm/Analysis/DSGraph.h"
  10 #include "llvm/iMemory.h"
  11 #include "llvm/iTerminators.h"
  12 #include "llvm/iPHINode.h"
  13 #include "llvm/iOther.h"
  14 #include "llvm/Constants.h"
  15 #include "llvm/DerivedTypes.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/GlobalVariable.h"
  18 #include "llvm/Support/InstVisitor.h"
  19 #include "llvm/Target/TargetData.h"
  20 #include "Support/Statistic.h"
  21 #include "Support/Timer.h"
  22 #include "Support/CommandLine.h"
  23
  24 // FIXME: This should eventually be a FunctionPass that is automatically
  25 // aggregated into a Pass.
  26 //
  27 #include "llvm/Module.h"
  28
  29 static RegisterAnalysis<LocalDataStructures>
  30 X("datastructure", "Local Data Structure Analysis");
  31
  32 namespace DS {
  33   // FIXME: Do something smarter with target data!
  34   TargetData TD("temp-td");
  35
  36   // isPointerType - Return true if this type is big enough to hold a pointer.
  37   bool isPointerType(const Type *Ty) {
  38     if (isa<PointerType>(Ty))
  39       return true;
  40     else if (Ty->isPrimitiveType() && Ty->isInteger())
  41       return Ty->getPrimitiveSize() >= PointerSize;
  42     return false;
  43   }
  44 }
  45 using namespace DS;
  46
  47
  48 namespace {
  49   cl::opt<bool>
  50   DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden,
  51                        cl::desc("Disable direct call optimization in "
  52                                 "DSGraph construction"));
  53   cl::opt<bool>
  54   DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden,
  55                           cl::desc("Disable field sensitivity in DSGraphs"));
  56
  57   //===--------------------------------------------------------------------===//
  58   //  GraphBuilder Class
  59   //===--------------------------------------------------------------------===//
  60   //
  61   /// This class is the builder class that constructs the local data structure
  62   /// graph by performing a single pass over the function in question.
  63   ///
  64   class GraphBuilder : InstVisitor<GraphBuilder> {
  65     Function &F;
  66     DSGraph &G;
  67     std::vector<DSNode*> &Nodes;
  68     DSNodeHandle &RetNode;               // Node that gets returned...
  69     DSGraph::ScalarMapTy &ScalarMap;
  70     std::vector<DSCallSite> &FunctionCalls;
  71
  72   public:
  73     GraphBuilder(Function &f, DSGraph &g, std::vector<DSNode*> &nodes,
  74                  DSNodeHandle &retNode, DSGraph::ScalarMapTy &SM,
  75                  std::vector<DSCallSite> &fc)
  76       : F(f), G(g), Nodes(nodes), RetNode(retNode), ScalarMap(SM),
  77         FunctionCalls(fc) {
  78
  79       // Create scalar nodes for all pointer arguments...
  80       for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
  81         if (isPointerType(I->getType()))
  82           getValueDest(*I);
  83
  84       visit(F);  // Single pass over the function
  85     }
  86
  87   private:
  88     // Visitor functions, used to handle each instruction type we encounter...
  89     friend class InstVisitor<GraphBuilder>;
  90     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); }
  91     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); }
  92     void handleAlloc(AllocationInst &AI, bool isHeap);
  93
  94     void visitPHINode(PHINode &PN);
  95
  96     void visitGetElementPtrInst(User &GEP);
  97     void visitReturnInst(ReturnInst &RI);
  98     void visitLoadInst(LoadInst &LI);
  99     void visitStoreInst(StoreInst &SI);
 100     void visitCallInst(CallInst &CI);
 101     void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
 102     void visitFreeInst(FreeInst &FI);
 103     void visitCastInst(CastInst &CI);
 104     void visitInstruction(Instruction &I);
 105
 106   private:
 107     // Helper functions used to implement the visitation functions...
 108
 109     /// createNode - Create a new DSNode, ensuring that it is properly added to
 110     /// the graph.
 111     ///
 112     DSNode *createNode(const Type *Ty = 0) {
 113       DSNode *N = new DSNode(Ty, &G);   // Create the node
 114       if (DisableFieldSensitivity) {
 115         N->foldNodeCompletely();
 116         if (DSNode *FN = N->getForwardNode())
 117           N = FN;
 118       }
 119       return N;
 120     }
 121
 122     /// setDestTo - Set the ScalarMap entry for the specified value to point to
 123     /// the specified destination.  If the Value already points to a node, make
 124     /// sure to merge the two destinations together.
 125     ///
 126     void setDestTo(Value &V, const DSNodeHandle &NH);
 127
 128     /// getValueDest - Return the DSNode that the actual value points to.
 129     ///
 130     DSNodeHandle getValueDest(Value &V);
 131
 132     /// getLink - This method is used to return the specified link in the
 133     /// specified node if one exists.  If a link does not already exist (it's
 134     /// null), then we create a new node, link it, then return it.
 135     ///
 136     DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0);
 137   };
 138 }
 139
 140 //===----------------------------------------------------------------------===//
 141 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 142 // graph.
 143 DSGraph::DSGraph(Function &F, DSGraph *GG) : GlobalsGraph(GG) {
 144   PrintAuxCalls = false;
 145
 146   DEBUG(std::cerr << "  [Loc] Calculating graph for: " << F.getName() << "\n");
 147
 148   // Use the graph builder to construct the local version of the graph
 149   GraphBuilder B(F, *this, Nodes, ReturnNodes[&F], ScalarMap, FunctionCalls);
 150 #ifndef NDEBUG
 151   Timer::addPeakMemoryMeasurement();
 152 #endif
 153
 154   // Remove all integral constants from the scalarmap!
 155   for (ScalarMapTy::iterator I = ScalarMap.begin(); I != ScalarMap.end();)
 156     if (isa<ConstantIntegral>(I->first)) {
 157       ScalarMapTy::iterator J = I++;
 158       ScalarMap.erase(J);
 159     } else
 160       ++I;
 161
 162   markIncompleteNodes(DSGraph::MarkFormalArgs);
 163
 164   // Remove any nodes made dead due to merging...
 165   removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 166 }
 167
 168
 169 //===----------------------------------------------------------------------===//
 170 // Helper method implementations...
 171 //
 172
 173 /// getValueDest - Return the DSNode that the actual value points to.
 174 ///
 175 DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
 176   Value *V = &Val;
 177   if (V == Constant::getNullValue(V->getType()))
 178     return 0;  // Null doesn't point to anything, don't add to ScalarMap!
 179
 180   DSNodeHandle &NH = ScalarMap[V];
 181   if (NH.getNode())
 182     return NH;     // Already have a node?  Just return it...
 183
 184   // Otherwise we need to create a new node to point to.
 185   // Check first for constant expressions that must be traversed to
 186   // extract the actual value.
 187   if (Constant *C = dyn_cast<Constant>(V))
 188     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 189       return NH = getValueDest(*CPR->getValue());
 190     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 191       if (CE->getOpcode() == Instruction::Cast)
 192         NH = getValueDest(*CE->getOperand(0));
 193       else if (CE->getOpcode() == Instruction::GetElementPtr) {
 194         visitGetElementPtrInst(*CE);
 195         DSGraph::ScalarMapTy::iterator I = ScalarMap.find(CE);
 196         assert(I != ScalarMap.end() && "GEP didn't get processed right?");
 197         NH = I->second;
 198       } else {
 199         // This returns a conservative unknown node for any unhandled ConstExpr
 200         return NH = createNode()->setUnknownNodeMarker();
 201       }
 202       if (NH.getNode() == 0) {  // (getelementptr null, X) returns null
 203         ScalarMap.erase(V);
 204         return 0;
 205       }
 206       return NH;
 207
 208     } else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C)) {
 209       // Random constants are unknown mem
 210       return NH = createNode()->setUnknownNodeMarker();
 211     } else {
 212       assert(0 && "Unknown constant type!");
 213     }
 214
 215   // Otherwise we need to create a new node to point to...
 216   DSNode *N;
 217   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 218     // Create a new global node for this global variable...
 219     N = createNode(GV->getType()->getElementType());
 220     N->addGlobal(GV);
 221   } else {
 222     // Otherwise just create a shadow node
 223     N = createNode();
 224   }
 225
 226   NH.setNode(N);      // Remember that we are pointing to it...
 227   NH.setOffset(0);
 228   return NH;
 229 }
 230
 231
 232 /// getLink - This method is used to return the specified link in the
 233 /// specified node if one exists.  If a link does not already exist (it's
 234 /// null), then we create a new node, link it, then return it.  We must
 235 /// specify the type of the Node field we are accessing so that we know what
 236 /// type should be linked to if we need to create a new node.
 237 ///
 238 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) {
 239   DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
 240   DSNodeHandle &Link = Node.getLink(LinkNo);
 241   if (!Link.getNode()) {
 242     // If the link hasn't been created yet, make and return a new shadow node
 243     Link = createNode();
 244   }
 245   return Link;
 246 }
 247
 248
 249 /// setDestTo - Set the ScalarMap entry for the specified value to point to the
 250 /// specified destination.  If the Value already points to a node, make sure to
 251 /// merge the two destinations together.
 252 ///
 253 void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) {
 254   DSNodeHandle &AINH = ScalarMap[&V];
 255   if (AINH.getNode() == 0)   // Not pointing to anything yet?
 256     AINH = NH;               // Just point directly to NH
 257   else
 258     AINH.mergeWith(NH);
 259 }
 260
 261
 262 //===----------------------------------------------------------------------===//
 263 // Specific instruction type handler implementations...
 264 //
 265
 266 /// Alloca & Malloc instruction implementation - Simply create a new memory
 267 /// object, pointing the scalar to it.
 268 ///
 269 void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) {
 270   DSNode *N = createNode();
 271   if (isHeap)
 272     N->setHeapNodeMarker();
 273   else
 274     N->setAllocaNodeMarker();
 275   setDestTo(AI, N);
 276 }
 277
 278 // PHINode - Make the scalar for the PHI node point to all of the things the
 279 // incoming values point to... which effectively causes them to be merged.
 280 //
 281 void GraphBuilder::visitPHINode(PHINode &PN) {
 282   if (!isPointerType(PN.getType())) return; // Only pointer PHIs
 283
 284   DSNodeHandle &PNDest = ScalarMap[&PN];
 285   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 286     PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
 287 }
 288
 289 void GraphBuilder::visitGetElementPtrInst(User &GEP) {
 290   DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
 291   if (Value.getNode() == 0) return;
 292
 293   unsigned Offset = 0;
 294   const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType());
 295   const Type *CurTy = PTy->getElementType();
 296
 297   if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) {
 298     // If the node had to be folded... exit quickly
 299     setDestTo(GEP, Value);  // GEP result points to folded node
 300     return;
 301   }
 302
 303 #if 0
 304   // Handle the pointer index specially...
 305   if (GEP.getNumOperands() > 1 &&
 306       GEP.getOperand(1) != ConstantSInt::getNullValue(Type::LongTy)) {
 307
 308     // If we already know this is an array being accessed, don't do anything...
 309     if (!TopTypeRec.isArray) {
 310       TopTypeRec.isArray = true;
 311
 312       // If we are treating some inner field pointer as an array, fold the node
 313       // up because we cannot handle it right.  This can come because of
 314       // something like this:  &((&Pt->X)[1]) == &Pt->Y
 315       //
 316       if (Value.getOffset()) {
 317         // Value is now the pointer we want to GEP to be...
 318         Value.getNode()->foldNodeCompletely();
 319         setDestTo(GEP, Value);  // GEP result points to folded node
 320         return;
 321       } else {
 322         // This is a pointer to the first byte of the node.  Make sure that we
 323         // are pointing to the outter most type in the node.
 324         // FIXME: We need to check one more case here...
 325       }
 326     }
 327   }
 328 #endif
 329
 330   // All of these subscripts are indexing INTO the elements we have...
 331   for (unsigned i = 2, e = GEP.getNumOperands(); i < e; ++i)
 332     if (GEP.getOperand(i)->getType() == Type::LongTy) {
 333       // Get the type indexing into...
 334       const SequentialType *STy = cast<SequentialType>(CurTy);
 335       CurTy = STy->getElementType();
 336 #if 0
 337       if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
 338         Offset += CS->getValue()*TD.getTypeSize(CurTy);
 339       } else {
 340         // Variable index into a node.  We must merge all of the elements of the
 341         // sequential type here.
 342         if (isa<PointerType>(STy))
 343           std::cerr << "Pointer indexing not handled yet!\n";
 344         else {
 345           const ArrayType *ATy = cast<ArrayType>(STy);
 346           unsigned ElSize = TD.getTypeSize(CurTy);
 347           DSNode *N = Value.getNode();
 348           assert(N && "Value must have a node!");
 349           unsigned RawOffset = Offset+Value.getOffset();
 350
 351           // Loop over all of the elements of the array, merging them into the
 352           // zero'th element.
 353           for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
 354             // Merge all of the byte components of this array element
 355             for (unsigned j = 0; j != ElSize; ++j)
 356               N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
 357         }
 358       }
 359 #endif
 360     } else if (GEP.getOperand(i)->getType() == Type::UByteTy) {
 361       unsigned FieldNo = cast<ConstantUInt>(GEP.getOperand(i))->getValue();
 362       const StructType *STy = cast<StructType>(CurTy);
 363       Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
 364       CurTy = STy->getContainedType(FieldNo);
 365     }
 366
 367   // Add in the offset calculated...
 368   Value.setOffset(Value.getOffset()+Offset);
 369
 370   // Value is now the pointer we want to GEP to be...
 371   setDestTo(GEP, Value);
 372 }
 373
 374 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 375   DSNodeHandle Ptr = getValueDest(*LI.getOperand(0));
 376   if (Ptr.getNode() == 0) return;
 377
 378   // Make that the node is read from...
 379   Ptr.getNode()->setReadMarker();
 380
 381   // Ensure a typerecord exists...
 382   Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false);
 383
 384   if (isPointerType(LI.getType()))
 385     setDestTo(LI, getLink(Ptr));
 386 }
 387
 388 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 389   const Type *StoredTy = SI.getOperand(0)->getType();
 390   DSNodeHandle Dest = getValueDest(*SI.getOperand(1));
 391   if (Dest.getNode() == 0) return;
 392
 393   // Mark that the node is written to...
 394   Dest.getNode()->setModifiedMarker();
 395
 396   // Ensure a typerecord exists...
 397   Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset());
 398
 399   // Avoid adding edges from null, or processing non-"pointer" stores
 400   if (isPointerType(StoredTy))
 401     Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
 402 }
 403
 404 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 405   if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()))
 406     RetNode.mergeWith(getValueDest(*RI.getOperand(0)));
 407 }
 408
 409 void GraphBuilder::visitCallInst(CallInst &CI) {
 410   // Set up the return value...
 411   DSNodeHandle RetVal;
 412   if (isPointerType(CI.getType()))
 413     RetVal = getValueDest(CI);
 414
 415   DSNode *Callee = 0;
 416   if (DisableDirectCallOpt || !isa<Function>(CI.getOperand(0)))
 417     Callee = getValueDest(*CI.getOperand(0)).getNode();
 418
 419   std::vector<DSNodeHandle> Args;
 420   Args.reserve(CI.getNumOperands()-1);
 421
 422   // Calculate the arguments vector...
 423   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 424     if (isPointerType(CI.getOperand(i)->getType()))
 425       Args.push_back(getValueDest(*CI.getOperand(i)));
 426
 427   // Add a new function call entry...
 428   if (Callee)
 429     FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args));
 430   else
 431     FunctionCalls.push_back(DSCallSite(CI, RetVal,
 432                                        cast<Function>(CI.getOperand(0)), Args));
 433 }
 434
 435 void GraphBuilder::visitFreeInst(FreeInst &FI) {
 436   // Mark that the node is written to...
 437   DSNode *N = getValueDest(*FI.getOperand(0)).getNode();
 438   N->setModifiedMarker();
 439   N->setHeapNodeMarker();
 440 }
 441
 442 /// Handle casts...
 443 void GraphBuilder::visitCastInst(CastInst &CI) {
 444   if (isPointerType(CI.getType()))
 445     if (isPointerType(CI.getOperand(0)->getType())) {
 446       // Cast one pointer to the other, just act like a copy instruction
 447       setDestTo(CI, getValueDest(*CI.getOperand(0)));
 448     } else {
 449       // Cast something (floating point, small integer) to a pointer.  We need
 450       // to track the fact that the node points to SOMETHING, just something we
 451       // don't know about.  Make an "Unknown" node.
 452       //
 453       setDestTo(CI, createNode()->setUnknownNodeMarker());
 454     }
 455 }
 456
 457
 458 // visitInstruction - For all other instruction types, if we have any arguments
 459 // that are of pointer type, make them have unknown composition bits, and merge
 460 // the nodes together.
 461 void GraphBuilder::visitInstruction(Instruction &Inst) {
 462   DSNodeHandle CurNode;
 463   if (isPointerType(Inst.getType()))
 464     CurNode = getValueDest(Inst);
 465   for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I)
 466     if (isPointerType((*I)->getType()))
 467       CurNode.mergeWith(getValueDest(**I));
 468
 469   if (CurNode.getNode())
 470     CurNode.getNode()->setUnknownNodeMarker();
 471 }
 472
 473
 474
 475 //===----------------------------------------------------------------------===//
 476 // LocalDataStructures Implementation
 477 //===----------------------------------------------------------------------===//
 478
 479 bool LocalDataStructures::run(Module &M) {
 480   GlobalsGraph = new DSGraph();
 481
 482   // Calculate all of the graphs...
 483   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 484     if (!I->isExternal())
 485       DSInfo.insert(std::make_pair(I, new DSGraph(*I, GlobalsGraph)));
 486   return false;
 487 }
 488
 489 // releaseMemory - If the pass pipeline is done with this pass, we can release
 490 // our memory... here...
 491 //
 492 void LocalDataStructures::releaseMemory() {
 493   for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
 494          E = DSInfo.end(); I != E; ++I) {
 495     I->second->getReturnNodes().erase(I->first);
 496     if (I->second->getReturnNodes().empty())
 497       delete I->second;
 498   }
 499
 500   // Empty map so next time memory is released, data structures are not
 501   // re-deleted.
 502   DSInfo.clear();
 503   delete GlobalsGraph;
 504   GlobalsGraph = 0;
 505 }