lib/Analysis/DataStructure/Local.cpp

   1 //===- ComputeLocal.cpp - Compute a local data structure graph for a fn ---===//
   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/Function.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/GlobalVariable.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/Support/InstVisitor.h"
  18 using std::map;
  19 using std::vector;
  20
  21 static RegisterAnalysis<LocalDataStructures>
  22 X("datastructure", "Local Data Structure Analysis");
  23 AnalysisID LocalDataStructures::ID = X;
  24
  25 //===----------------------------------------------------------------------===//
  26 //  GraphBuilder Class
  27 //===----------------------------------------------------------------------===//
  28 //
  29 // This class is the builder class that constructs the local data structure
  30 // graph by performing a single pass over the function in question.
  31 //
  32
  33 namespace {
  34   class GraphBuilder : InstVisitor<GraphBuilder> {
  35     DSGraph &G;
  36     vector<DSNode*> &Nodes;
  37     DSNodeHandle &RetNode;               // Node that gets returned...
  38     map<Value*, DSNodeHandle> &ValueMap;
  39     vector<vector<DSNodeHandle> > &FunctionCalls;
  40
  41   public:
  42     GraphBuilder(DSGraph &g, vector<DSNode*> &nodes, DSNodeHandle &retNode,
  43                  map<Value*, DSNodeHandle> &vm,
  44                  vector<vector<DSNodeHandle> > &fc)
  45       : G(g), Nodes(nodes), RetNode(retNode), ValueMap(vm), FunctionCalls(fc) {
  46
  47       // Create scalar nodes for all pointer arguments...
  48       for (Function::aiterator I = G.getFunction().abegin(),
  49              E = G.getFunction().aend(); I != E; ++I)
  50         if (isa<PointerType>(I->getType()))
  51           getValueNode(*I);
  52
  53       visit(G.getFunction());  // Single pass over the function
  54
  55       // Not inlining, only eliminate trivially dead nodes.
  56       G.removeTriviallyDeadNodes();
  57     }
  58
  59   private:
  60     // Visitor functions, used to handle each instruction type we encounter...
  61     friend class InstVisitor<GraphBuilder>;
  62     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, DSNode::NewNode); }
  63     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, DSNode::AllocaNode);}
  64     void handleAlloc(AllocationInst &AI, DSNode::NodeTy NT);
  65
  66     void visitPHINode(PHINode &PN);
  67
  68     void visitGetElementPtrInst(GetElementPtrInst &GEP);
  69     void visitReturnInst(ReturnInst &RI);
  70     void visitLoadInst(LoadInst &LI);
  71     void visitStoreInst(StoreInst &SI);
  72     void visitCallInst(CallInst &CI);
  73     void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
  74     void visitFreeInst(FreeInst &FI) {}         // Ignore free instructions
  75     void visitInstruction(Instruction &I);      // Visit unsafe ptr instruction
  76
  77   private:
  78     // Helper functions used to implement the visitation functions...
  79
  80     // createNode - Create a new DSNode, ensuring that it is properly added to
  81     // the graph.
  82     //
  83     DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty);
  84
  85     // getValueNode - Return a DSNode that corresponds the the specified LLVM
  86     // value.  This either returns the already existing node, or creates a new
  87     // one and adds it to the graph, if none exists.
  88     //
  89     DSNode *getValueNode(Value &V);
  90
  91     // getGlobalNode - Just like getValueNode, except the global node itself is
  92     // returned, not a scalar node pointing to a global.
  93     //
  94     DSNode *getGlobalNode(GlobalValue &V);
  95
  96     // getLink - This method is used to either return the specified link in the
  97     // specified node if one exists.  If a link does not already exist (it's
  98     // null), then we create a new node, link it, then return it.
  99     //
 100     DSNode *getLink(DSNode *Node, unsigned Link);
 101
 102     // getSubscriptedNode - Perform the basic getelementptr functionality that
 103     // must be factored out of gep, load and store while they are all MAI's.
 104     //
 105     DSNode *getSubscriptedNode(MemAccessInst &MAI, DSNode *Ptr);
 106   };
 107 }
 108
 109 //===----------------------------------------------------------------------===//
 110 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 111 // graph.
 112 DSGraph::DSGraph(Function &F) : Func(F), RetNode(0) {
 113   // Use the graph builder to construct the local version of the graph
 114   GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls);
 115   markIncompleteNodes();
 116 }
 117
 118
 119 //===----------------------------------------------------------------------===//
 120 // Helper method implementations...
 121 //
 122
 123
 124 // createNode - Create a new DSNode, ensuring that it is properly added to the
 125 // graph.
 126 //
 127 DSNode *GraphBuilder::createNode(DSNode::NodeTy NodeType, const Type *Ty) {
 128   DSNode *N = new DSNode(NodeType, Ty);
 129   Nodes.push_back(N);
 130   return N;
 131 }
 132
 133
 134 // getGlobalNode - Just like getValueNode, except the global node itself is
 135 // returned, not a scalar node pointing to a global.
 136 //
 137 DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) {
 138   DSNodeHandle &NH = ValueMap[&V];
 139   if (NH) return NH;             // Already have a node?  Just return it...
 140
 141   // Create a new global node for this global variable...
 142   DSNode *G = createNode(DSNode::GlobalNode, V.getType()->getElementType());
 143   G->addGlobal(&V);
 144
 145   // If this node has outgoing edges, make sure to recycle the same node for
 146   // each use.  For functions and other global variables, this is unneccesary,
 147   // so avoid excessive merging by cloning these nodes on demand.
 148   //
 149   NH = G;
 150   return G;
 151 }
 152
 153
 154 // getValueNode - Return a DSNode that corresponds the the specified LLVM value.
 155 // This either returns the already existing node, or creates a new one and adds
 156 // it to the graph, if none exists.
 157 //
 158 DSNode *GraphBuilder::getValueNode(Value &V) {
 159   assert(isa<PointerType>(V.getType()) && "Should only use pointer scalars!");
 160   if (!isa<GlobalValue>(V)) {
 161     DSNodeHandle &NH = ValueMap[&V];
 162     if (NH) return NH;             // Already have a node?  Just return it...
 163   }
 164
 165   // Otherwise we need to create a new scalar node...
 166   DSNode *N = createNode(DSNode::ScalarNode, V.getType());
 167
 168   // If this is a global value, create the global pointed to.
 169   if (GlobalValue *GV = dyn_cast<GlobalValue>(&V)) {
 170     DSNode *G = getGlobalNode(*GV);
 171     N->addEdgeTo(G);
 172   } else {
 173     ValueMap[&V] = N;
 174   }
 175
 176   return N;
 177 }
 178
 179
 180 // getLink - This method is used to either return the specified link in the
 181 // specified node if one exists.  If a link does not already exist (it's
 182 // null), then we create a new node, link it, then return it.
 183 //
 184 DSNode *GraphBuilder::getLink(DSNode *Node, unsigned Link) {
 185   assert(Link < Node->getNumLinks() && "Link accessed out of range!");
 186   if (Node->getLink(Link) == 0) {
 187     DSNode::NodeTy NT;
 188     const Type *Ty;
 189
 190     switch (Node->getType()->getPrimitiveID()) {
 191     case Type::PointerTyID:
 192       Ty = cast<PointerType>(Node->getType())->getElementType();
 193       NT = DSNode::ShadowNode;
 194       break;
 195     case Type::ArrayTyID:
 196       Ty = cast<ArrayType>(Node->getType())->getElementType();
 197       NT = DSNode::SubElement;
 198       break;
 199     case Type::StructTyID:
 200       Ty = cast<StructType>(Node->getType())->getContainedType(Link);
 201       NT = DSNode::SubElement;
 202       break;
 203     default:
 204       assert(0 && "Unexpected type to dereference!");
 205       abort();
 206     }
 207
 208     DSNode *New = createNode(NT, Ty);
 209     Node->addEdgeTo(Link, New);
 210   }
 211
 212   return Node->getLink(Link);
 213 }
 214
 215 // getSubscriptedNode - Perform the basic getelementptr functionality that must
 216 // be factored out of gep, load and store while they are all MAI's.
 217 //
 218 DSNode *GraphBuilder::getSubscriptedNode(MemAccessInst &MAI, DSNode *Ptr) {
 219   for (unsigned i = MAI.getFirstIndexOperandNumber(), e = MAI.getNumOperands();
 220        i != e; ++i)
 221     if (MAI.getOperand(i)->getType() == Type::UIntTy)
 222       Ptr = getLink(Ptr, 0);
 223     else if (MAI.getOperand(i)->getType() == Type::UByteTy)
 224       Ptr = getLink(Ptr, cast<ConstantUInt>(MAI.getOperand(i))->getValue());
 225
 226   if (MAI.getFirstIndexOperandNumber() == MAI.getNumOperands())
 227     Ptr = getLink(Ptr, 0);  // All MAI's have an implicit 0 if nothing else.
 228
 229   return Ptr;
 230 }
 231
 232 //===----------------------------------------------------------------------===//
 233 // Specific instruction type handler implementations...
 234 //
 235
 236 // Alloca & Malloc instruction implementation - Simply create a new memory
 237 // object, pointing the scalar to it.
 238 //
 239 void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
 240   DSNode *Scalar = getValueNode(AI);
 241   DSNode *New = createNode(NodeType, AI.getAllocatedType());
 242   Scalar->addEdgeTo(New);   // Make the scalar point to the new node...
 243 }
 244
 245 // PHINode - Make the scalar for the PHI node point to all of the things the
 246 // incoming values point to... which effectively causes them to be merged.
 247 //
 248 void GraphBuilder::visitPHINode(PHINode &PN) {
 249   if (!isa<PointerType>(PN.getType())) return; // Only pointer PHIs
 250
 251   DSNode *Scalar     = getValueNode(PN);
 252   DSNode *ScalarDest = getLink(Scalar, 0);
 253   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 254     ScalarDest->mergeWith(getLink(getValueNode(*PN.getIncomingValue(i)), 0));
 255 }
 256
 257 void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 258   DSNode *Ptr = getSubscriptedNode(GEP, getValueNode(*GEP.getOperand(0)));
 259   getValueNode(GEP)->addEdgeTo(Ptr);
 260 }
 261
 262 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 263   DSNode *Ptr = getSubscriptedNode(LI, getValueNode(*LI.getOperand(0)));
 264   if (!isa<PointerType>(LI.getType())) return; // Only pointer PHIs
 265   getValueNode(LI)->addEdgeTo(getLink(Ptr, 0));
 266 }
 267
 268 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 269   DSNode *DestPtr = getSubscriptedNode(SI, getValueNode(*SI.getOperand(1)));
 270   if (!isa<PointerType>(SI.getOperand(0)->getType())) return;
 271   DSNode *Value   = getValueNode(*SI.getOperand(0));
 272   DestPtr->addEdgeTo(getLink(Value, 0));
 273 }
 274
 275 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 276   if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) {
 277     DSNode *Value = getLink(getValueNode(*RI.getOperand(0)), 0);
 278     Value->mergeWith(RetNode);
 279     RetNode = Value;
 280   }
 281 }
 282
 283 void GraphBuilder::visitCallInst(CallInst &CI) {
 284   // Add a new function call entry...
 285   FunctionCalls.push_back(vector<DSNodeHandle>());
 286   vector<DSNodeHandle> &Args = FunctionCalls.back();
 287
 288   // Set up the return value...
 289   if (isa<PointerType>(CI.getType()))
 290     Args.push_back(getLink(getValueNode(CI), 0));
 291   else
 292     Args.push_back(0);
 293
 294   unsigned Start = 0;
 295   // Special case for direct call, avoid creating spurious scalar node...
 296   if (GlobalValue *GV = dyn_cast<GlobalValue>(CI.getOperand(0))) {
 297     Args.push_back(getGlobalNode(*GV));
 298     Start = 1;
 299   }
 300
 301   // Pass the arguments in...
 302   for (unsigned i = Start, e = CI.getNumOperands(); i != e; ++i)
 303     if (isa<PointerType>(CI.getOperand(i)->getType()))
 304       Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0));
 305 }
 306
 307 // visitInstruction - All safe instructions have been processed above, this case
 308 // is where unsafe ptr instructions land.
 309 //
 310 void GraphBuilder::visitInstruction(Instruction &I) {
 311   // If the return type is a pointer, mark the pointed node as being a cast node
 312   if (isa<PointerType>(I.getType()))
 313     getLink(getValueNode(I), 0)->NodeType |= DSNode::CastNode;
 314
 315   // If any operands are pointers, mark the pointed nodes as being a cast node
 316   for (Instruction::op_iterator i = I.op_begin(), E = I.op_end(); i!=E; ++i)
 317     if (isa<PointerType>(i->get()->getType()))
 318       getLink(getValueNode(*i->get()), 0)->NodeType |= DSNode::CastNode;
 319 }
 320