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