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
 190   DSNodeHandle &NH = ValueMap[&V];
 191   if (NH.getNode()) return NH;     // Already have a node?  Just return it...
 192
 193   // Otherwise we need to create a new scalar node...
 194   DSNode *N = createNode(DSNode::ScalarNode, V.getType());
 195
 196   // If this is a global value, create the global pointed to.
 197   if (GlobalValue *GV = dyn_cast<GlobalValue>(&V)) {
 198     N->addEdgeTo(0, getGlobalNode(*GV));
 199     return DSNodeHandle(N, 0);
 200   } else {
 201     NH.setOffset(0);
 202     NH.setNode(N);
 203   }
 204
 205   return NH;
 206 }
 207
 208 /// getValueDest - Return the DSNode that the actual value points to.  This
 209 /// is basically the same thing as: getLink(getValueNode(V), 0)
 210 ///
 211 DSNodeHandle &GraphBuilder::getValueDest(Value &V) {
 212   return getLink(getValueNode(V), 0, V.getType());
 213 }
 214
 215
 216 /// getLink - This method is used to return the specified link in the
 217 /// specified node if one exists.  If a link does not already exist (it's
 218 /// null), then we create a new node, link it, then return it.  We must
 219 /// specify the type of the Node field we are accessing so that we know what
 220 /// type should be linked to if we need to create a new node.
 221 ///
 222 DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node,
 223                                     unsigned LinkNo, const Type *FieldTy) {
 224   DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
 225
 226   DSNodeHandle *Link = Node.getLink(LinkNo);
 227   if (Link) return *Link;
 228
 229   // If the link hasn't been created yet, make and return a new shadow node of
 230   // the appropriate type for FieldTy...
 231   //
 232
 233   // If we are indexing with a typed pointer, then the thing we are pointing
 234   // to is of the pointed type.  If we are pointing to it with an integer
 235   // (because of cast to an integer), we represent it with a void type.
 236   //
 237   const Type *ReqTy;
 238   if (const PointerType *Ptr = dyn_cast<PointerType>(FieldTy))
 239     ReqTy = Ptr->getElementType();
 240   else
 241     ReqTy = Type::VoidTy;
 242
 243   DSNode *N = createNode(DSNode::ShadowNode, ReqTy);
 244   Node.setLink(LinkNo, N);
 245   return *Node.getLink(LinkNo);
 246 }
 247
 248
 249 //===----------------------------------------------------------------------===//
 250 // Specific instruction type handler implementations...
 251 //
 252
 253 /// Alloca & Malloc instruction implementation - Simply create a new memory
 254 /// object, pointing the scalar to it.
 255 ///
 256 void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
 257   //DSNode *New = createNode(NodeType, Type::VoidTy);
 258   DSNode *New = createNode(NodeType, AI.getAllocatedType());
 259
 260   // Make the scalar point to the new node...
 261   getValueNode(AI).addEdgeTo(New);
 262 }
 263
 264 // PHINode - Make the scalar for the PHI node point to all of the things the
 265 // incoming values point to... which effectively causes them to be merged.
 266 //
 267 void GraphBuilder::visitPHINode(PHINode &PN) {
 268   if (!isPointerType(PN.getType())) return; // Only pointer PHIs
 269
 270   DSNodeHandle &ScalarDest = getValueDest(PN);
 271   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 272     if (!isa<ConstantPointerNull>(PN.getIncomingValue(i)))
 273       ScalarDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
 274 }
 275
 276 void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 277   DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
 278
 279   unsigned Offset = 0;
 280   const Type *CurTy = GEP.getOperand(0)->getType();
 281
 282   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
 283     if (GEP.getOperand(i)->getType() == Type::LongTy) {
 284       // Get the type indexing into...
 285       const SequentialType *STy = cast<SequentialType>(CurTy);
 286       CurTy = STy->getElementType();
 287       if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
 288         if (isa<PointerType>(STy))
 289           std::cerr << "Pointer indexing not handled yet!\n";
 290         else
 291           Offset += CS->getValue()*TD.getTypeSize(CurTy);
 292       } else {
 293         // Variable index into a node.  We must merge all of the elements of the
 294         // sequential type here.
 295         if (isa<PointerType>(STy))
 296           std::cerr << "Pointer indexing not handled yet!\n";
 297         else {
 298           const ArrayType *ATy = cast<ArrayType>(STy);
 299           unsigned ElSize = TD.getTypeSize(CurTy);
 300           DSNode *N = Value.getNode();
 301           assert(N && "Value must have a node!");
 302           unsigned RawOffset = Offset+Value.getOffset();
 303
 304           // Loop over all of the elements of the array, merging them into the
 305           // zero'th element.
 306           for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
 307             // Merge all of the byte components of this array element
 308             for (unsigned j = 0; j != ElSize; ++j)
 309               N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
 310         }
 311       }
 312     } else if (GEP.getOperand(i)->getType() == Type::UByteTy) {
 313       unsigned FieldNo = cast<ConstantUInt>(GEP.getOperand(i))->getValue();
 314       const StructType *STy = cast<StructType>(CurTy);
 315       Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
 316       CurTy = STy->getContainedType(FieldNo);
 317     }
 318
 319   // Add in the offset calculated...
 320   Value.setOffset(Value.getOffset()+Offset);
 321
 322   // Value is now the pointer we want to GEP to be...
 323   getValueNode(GEP).addEdgeTo(Value);
 324 }
 325
 326 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 327   DSNodeHandle &Ptr = getValueDest(*LI.getOperand(0));
 328   Ptr.getNode()->NodeType |= DSNode::Read;
 329
 330   if (isPointerType(LI.getType()))
 331     getValueNode(LI).addEdgeTo(getLink(Ptr, 0, LI.getType()));
 332 }
 333
 334 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 335   DSNodeHandle &Dest = getValueDest(*SI.getOperand(1));
 336   Dest.getNode()->NodeType |= DSNode::Modified;
 337
 338   // Avoid adding edges from null, or processing non-"pointer" stores
 339   if (isPointerType(SI.getOperand(0)->getType()) &&
 340       !isa<ConstantPointerNull>(SI.getOperand(0))) {
 341     Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
 342   }
 343 }
 344
 345 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 346   if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()) &&
 347       !isa<ConstantPointerNull>(RI.getOperand(0))) {
 348     DSNodeHandle &Value = getValueDest(*RI.getOperand(0));
 349     Value.mergeWith(RetNode);
 350     RetNode = Value;
 351   }
 352 }
 353
 354 void GraphBuilder::visitCallInst(CallInst &CI) {
 355   // Set up the return value...
 356   DSNodeHandle RetVal;
 357   if (isPointerType(CI.getType()))
 358     RetVal = getLink(getValueNode(CI), 0, CI.getType());
 359
 360   DSNodeHandle Callee;
 361   // Special case for a direct call, avoid creating spurious scalar node...
 362   if (GlobalValue *GV = dyn_cast<GlobalValue>(CI.getOperand(0)))
 363     Callee = getGlobalNode(*GV);
 364   else
 365     Callee = getLink(getValueNode(*CI.getOperand(0)), 0,
 366                      CI.getOperand(0)->getType());
 367
 368   std::vector<DSNodeHandle> Args;
 369   Args.reserve(CI.getNumOperands()-1);
 370
 371   // Calculate the arguments vector...
 372   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 373     if (isPointerType(CI.getOperand(i)->getType()))
 374       Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0,
 375                              CI.getOperand(i)->getType()));
 376
 377   // Add a new function call entry...
 378   FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args));
 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 }