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