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/DSGraph.h"
   9 #include "llvm/Analysis/DataStructure.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
  22 // FIXME: This should eventually be a FunctionPass that is automatically
  23 // aggregated into a Pass.
  24 //
  25 #include "llvm/Module.h"
  26
  27 using std::map;
  28 using std::vector;
  29
  30 static RegisterAnalysis<LocalDataStructures>
  31 X("datastructure", "Local Data Structure Analysis");
  32
  33 using namespace DataStructureAnalysis;
  34
  35 namespace DataStructureAnalysis {
  36   // FIXME: Do something smarter with target data!
  37   TargetData TD("temp-td");
  38   unsigned PointerSize(TD.getPointerSize());
  39
  40   // isPointerType - Return true if this type is big enough to hold a pointer.
  41   bool isPointerType(const Type *Ty) {
  42     if (isa<PointerType>(Ty))
  43       return true;
  44     else if (Ty->isPrimitiveType() && Ty->isInteger())
  45       return Ty->getPrimitiveSize() >= PointerSize;
  46     return false;
  47   }
  48 }
  49
  50
  51 namespace {
  52   //===--------------------------------------------------------------------===//
  53   //  GraphBuilder Class
  54   //===--------------------------------------------------------------------===//
  55   //
  56   /// This class is the builder class that constructs the local data structure
  57   /// graph by performing a single pass over the function in question.
  58   ///
  59   class GraphBuilder : InstVisitor<GraphBuilder> {
  60     DSGraph &G;
  61     vector<DSNode*> &Nodes;
  62     DSNodeHandle &RetNode;               // Node that gets returned...
  63     map<Value*, DSNodeHandle> &ValueMap;
  64     vector<DSCallSite> &FunctionCalls;
  65
  66   public:
  67     GraphBuilder(DSGraph &g, vector<DSNode*> &nodes, DSNodeHandle &retNode,
  68                  map<Value*, DSNodeHandle> &vm,
  69                  vector<DSCallSite> &fc)
  70       : G(g), Nodes(nodes), RetNode(retNode), ValueMap(vm), FunctionCalls(fc) {
  71
  72       // Create scalar nodes for all pointer arguments...
  73       for (Function::aiterator I = G.getFunction().abegin(),
  74              E = G.getFunction().aend(); I != E; ++I)
  75         if (isPointerType(I->getType()))
  76           getValueDest(*I);
  77
  78       visit(G.getFunction());  // Single pass over the function
  79
  80       // Not inlining, only eliminate trivially dead nodes.
  81       G.removeTriviallyDeadNodes();
  82     }
  83
  84   private:
  85     // Visitor functions, used to handle each instruction type we encounter...
  86     friend class InstVisitor<GraphBuilder>;
  87     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, DSNode::NewNode); }
  88     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, DSNode::AllocaNode);}
  89     void handleAlloc(AllocationInst &AI, DSNode::NodeTy NT);
  90
  91     void visitPHINode(PHINode &PN);
  92
  93     void visitGetElementPtrInst(GetElementPtrInst &GEP);
  94     void visitReturnInst(ReturnInst &RI);
  95     void visitLoadInst(LoadInst &LI);
  96     void visitStoreInst(StoreInst &SI);
  97     void visitCallInst(CallInst &CI);
  98     void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
  99     void visitFreeInst(FreeInst &FI) {}         // Ignore free instructions
 100     void visitCastInst(CastInst &CI);
 101     void visitInstruction(Instruction &I) {}
 102
 103   private:
 104     // Helper functions used to implement the visitation functions...
 105
 106     /// createNode - Create a new DSNode, ensuring that it is properly added to
 107     /// the graph.
 108     ///
 109     DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty);
 110
 111     /// getValueNode - Return a DSNode that corresponds the the specified LLVM
 112     /// value.  This either returns the already existing node, or creates a new
 113     /// one and adds it to the graph, if none exists.
 114     ///
 115     DSNodeHandle getValueNode(Value &V);
 116
 117     /// getValueDest - Return the DSNode that the actual value points to.  This
 118     /// is basically the same thing as: getLink(getValueNode(V), 0)
 119     ///
 120     DSNodeHandle &getValueDest(Value &V);
 121
 122     /// getGlobalNode - Just like getValueNode, except the global node itself is
 123     /// returned, not a scalar node pointing to a global.
 124     ///
 125     DSNodeHandle &getGlobalNode(GlobalValue &V);
 126
 127     /// getLink - This method is used to return the specified link in the
 128     /// specified node if one exists.  If a link does not already exist (it's
 129     /// null), then we create a new node, link it, then return it.  We must
 130     /// specify the type of the Node field we are accessing so that we know what
 131     /// type should be linked to if we need to create a new node.
 132     ///
 133     DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link,
 134                           const Type *FieldTy);
 135   };
 136 }
 137
 138 //===----------------------------------------------------------------------===//
 139 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 140 // graph.
 141 DSGraph::DSGraph(Function &F) : Func(&F) {
 142   // Use the graph builder to construct the local version of the graph
 143   GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls);
 144   markIncompleteNodes();
 145 }
 146
 147
 148 //===----------------------------------------------------------------------===//
 149 // Helper method implementations...
 150 //
 151
 152
 153 // createNode - Create a new DSNode, ensuring that it is properly added to the
 154 // graph.
 155 //
 156 DSNode *GraphBuilder::createNode(DSNode::NodeTy NodeType, const Type *Ty) {
 157   DSNode *N = new DSNode(NodeType, Ty);
 158   Nodes.push_back(N);
 159   return N;
 160 }
 161
 162
 163 // getGlobalNode - Just like getValueNode, except the global node itself is
 164 // returned, not a scalar node pointing to a global.
 165 //
 166 DSNodeHandle &GraphBuilder::getGlobalNode(GlobalValue &V) {
 167   DSNodeHandle &NH = ValueMap[&V];
 168   if (NH.getNode()) return NH;       // Already have a node?  Just return it...
 169
 170   // Create a new global node for this global variable...
 171   DSNode *G = createNode(DSNode::GlobalNode, V.getType()->getElementType());
 172   G->addGlobal(&V);
 173
 174   // If this node has outgoing edges, make sure to recycle the same node for
 175   // each use.  For functions and other global variables, this is unneccesary,
 176   // so avoid excessive merging by cloning these nodes on demand.
 177   //
 178   NH.setNode(G);
 179   return NH;
 180 }
 181
 182
 183 // getValueNode - Return a DSNode that corresponds the the specified LLVM value.
 184 // This either returns the already existing node, or creates a new one and adds
 185 // it to the graph, if none exists.
 186 //
 187 DSNodeHandle GraphBuilder::getValueNode(Value &V) {
 188   assert(isPointerType(V.getType()) && "Should only use pointer scalars!");
 189   // Do not share the pointer value to globals... this would cause way too much
 190   // false merging.
 191   //
 192   DSNodeHandle &NH = ValueMap[&V];
 193   if (!isa<GlobalValue>(V) && NH.getNode())
 194     return NH;     // Already have a node?  Just return it...
 195
 196   // Otherwise we need to create a new scalar node...
 197   DSNode *N = createNode(DSNode::ScalarNode, V.getType());
 198
 199   // If this is a global value, create the global pointed to.
 200   if (GlobalValue *GV = dyn_cast<GlobalValue>(&V)) {
 201     N->addEdgeTo(0, getGlobalNode(*GV));
 202     return DSNodeHandle(N, 0);
 203   } else {
 204     NH.setOffset(0);
 205     NH.setNode(N);
 206   }
 207
 208   return NH;
 209 }
 210
 211 /// getValueDest - Return the DSNode that the actual value points to.  This
 212 /// is basically the same thing as: getLink(getValueNode(V), 0)
 213 ///
 214 DSNodeHandle &GraphBuilder::getValueDest(Value &V) {
 215   return getLink(getValueNode(V), 0, V.getType());
 216 }
 217
 218
 219 /// getLink - This method is used to return the specified link in the
 220 /// specified node if one exists.  If a link does not already exist (it's
 221 /// null), then we create a new node, link it, then return it.  We must
 222 /// specify the type of the Node field we are accessing so that we know what
 223 /// type should be linked to if we need to create a new node.
 224 ///
 225 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node,
 226                                     unsigned LinkNo, const Type *FieldTy) {
 227   DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
 228
 229   DSNodeHandle *Link = Node.getLink(LinkNo);
 230   if (Link) return *Link;
 231
 232   // If the link hasn't been created yet, make and return a new shadow node of
 233   // the appropriate type for FieldTy...
 234   //
 235
 236   // If we are indexing with a typed pointer, then the thing we are pointing
 237   // to is of the pointed type.  If we are pointing to it with an integer
 238   // (because of cast to an integer), we represent it with a void type.
 239   //
 240   const Type *ReqTy;
 241   if (const PointerType *Ptr = dyn_cast<PointerType>(FieldTy))
 242     ReqTy = Ptr->getElementType();
 243   else
 244     ReqTy = Type::VoidTy;
 245
 246   DSNode *N = createNode(DSNode::ShadowNode, ReqTy);
 247   Node.setLink(LinkNo, N);
 248   return *Node.getLink(LinkNo);
 249 }
 250
 251
 252 //===----------------------------------------------------------------------===//
 253 // Specific instruction type handler implementations...
 254 //
 255
 256 /// Alloca & Malloc instruction implementation - Simply create a new memory
 257 /// object, pointing the scalar to it.
 258 ///
 259 void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
 260   DSNode *New = createNode(NodeType, AI.getAllocatedType());
 261
 262   // Make the scalar point to the new node...
 263   getValueNode(AI).addEdgeTo(New);
 264 }
 265
 266 // PHINode - Make the scalar for the PHI node point to all of the things the
 267 // incoming values point to... which effectively causes them to be merged.
 268 //
 269 void GraphBuilder::visitPHINode(PHINode &PN) {
 270   if (!isPointerType(PN.getType())) return; // Only pointer PHIs
 271
 272   DSNodeHandle &ScalarDest = getValueDest(PN);
 273   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 274     if (!isa<ConstantPointerNull>(PN.getIncomingValue(i)))
 275       ScalarDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
 276 }
 277
 278 void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 279   DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
 280
 281   unsigned Offset = 0;
 282   const Type *CurTy = GEP.getOperand(0)->getType();
 283
 284   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
 285     if (GEP.getOperand(i)->getType() == Type::LongTy) {
 286       // Get the type indexing into...
 287       const SequentialType *STy = cast<SequentialType>(CurTy);
 288       CurTy = STy->getElementType();
 289       if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
 290         if (isa<PointerType>(STy))
 291           std::cerr << "Pointer indexing not handled yet!\n";
 292         else
 293           Offset += CS->getValue()*TD.getTypeSize(CurTy);
 294       } else {
 295         // Variable index into a node.  We must merge all of the elements of the
 296         // sequential type here.
 297         if (isa<PointerType>(STy))
 298           std::cerr << "Pointer indexing not handled yet!\n";
 299         else {
 300           const ArrayType *ATy = cast<ArrayType>(STy);
 301           unsigned ElSize = TD.getTypeSize(CurTy);
 302           DSNode *N = Value.getNode();
 303           assert(N && "Value must have a node!");
 304           unsigned RawOffset = Offset+Value.getOffset();
 305
 306           // Loop over all of the elements of the array, merging them into the
 307           // zero'th element.
 308           for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
 309             // Merge all of the byte components of this array element
 310             for (unsigned j = 0; j != ElSize; ++j)
 311               N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
 312         }
 313       }
 314     } else if (GEP.getOperand(i)->getType() == Type::UByteTy) {
 315       unsigned FieldNo = cast<ConstantUInt>(GEP.getOperand(i))->getValue();
 316       const StructType *STy = cast<StructType>(CurTy);
 317       Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
 318       CurTy = STy->getContainedType(FieldNo);
 319     }
 320
 321   // Add in the offset calculated...
 322   Value.setOffset(Value.getOffset()+Offset);
 323
 324   // Value is now the pointer we want to GEP to be...
 325   getValueNode(GEP).addEdgeTo(Value);
 326 }
 327
 328 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 329   DSNodeHandle &Ptr = getValueDest(*LI.getOperand(0));
 330   Ptr.getNode()->NodeType |= DSNode::Read;
 331
 332   if (isPointerType(LI.getType()))
 333     getValueNode(LI).addEdgeTo(getLink(Ptr, 0, LI.getType()));
 334 }
 335
 336 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 337   DSNodeHandle &Dest = getValueDest(*SI.getOperand(1));
 338   Dest.getNode()->NodeType |= DSNode::Modified;
 339
 340   // Avoid adding edges from null, or processing non-"pointer" stores
 341   if (isPointerType(SI.getOperand(0)->getType()) &&
 342       !isa<ConstantPointerNull>(SI.getOperand(0))) {
 343     Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
 344   }
 345 }
 346
 347 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 348   if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()) &&
 349       !isa<ConstantPointerNull>(RI.getOperand(0))) {
 350     DSNodeHandle &Value = getValueDest(*RI.getOperand(0));
 351     Value.mergeWith(RetNode);
 352     RetNode = Value;
 353   }
 354 }
 355
 356 void GraphBuilder::visitCallInst(CallInst &CI) {
 357   // Add a new function call entry...
 358   FunctionCalls.push_back(CI);
 359   DSCallSite &Args = FunctionCalls.back();
 360
 361   // Set up the return value...
 362   if (isPointerType(CI.getType()))
 363     Args.push_back(getLink(getValueNode(CI), 0, CI.getType()));
 364   else
 365     Args.push_back(DSNodeHandle());
 366
 367   unsigned Start = 0;
 368   // Special case for a direct call, avoid creating spurious scalar node...
 369   if (GlobalValue *GV = dyn_cast<GlobalValue>(CI.getOperand(0))) {
 370     Args.push_back(getGlobalNode(*GV));
 371     Start = 1;
 372   }
 373
 374   // Pass the arguments in...
 375   for (unsigned i = Start, e = CI.getNumOperands(); i != e; ++i)
 376     if (isPointerType(CI.getOperand(i)->getType()))
 377       Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0,
 378                              CI.getOperand(i)->getType()));
 379 }
 380
 381 /// Handle casts...
 382 void GraphBuilder::visitCastInst(CastInst &CI) {
 383   if (isPointerType(CI.getType()) && isPointerType(CI.getOperand(0)->getType()))
 384     getValueNode(CI).addEdgeTo(getLink(getValueNode(*CI.getOperand(0)), 0,
 385                                        CI.getOperand(0)->getType()));
 386 }
 387
 388
 389
 390
 391 //===----------------------------------------------------------------------===//
 392 // LocalDataStructures Implementation
 393 //===----------------------------------------------------------------------===//
 394
 395 // releaseMemory - If the pass pipeline is done with this pass, we can release
 396 // our memory... here...
 397 //
 398 void LocalDataStructures::releaseMemory() {
 399   for (std::map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
 400          E = DSInfo.end(); I != E; ++I)
 401     delete I->second;
 402
 403   // Empty map so next time memory is released, data structures are not
 404   // re-deleted.
 405   DSInfo.clear();
 406 }
 407
 408 bool LocalDataStructures::run(Module &M) {
 409   // Calculate all of the graphs...
 410   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 411     if (!I->isExternal())
 412       DSInfo.insert(std::make_pair(I, new DSGraph(*I)));
 413   return false;
 414 }