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/DerivedTypes.h"
  16 #include "llvm/Support/InstVisitor.h"
  17 using std::map;
  18 using std::vector;
  19
  20 //===----------------------------------------------------------------------===//
  21 //  GraphBuilder Class
  22 //===----------------------------------------------------------------------===//
  23 //
  24 // This class is the builder class that constructs the local data structure
  25 // graph by performing a single pass over the function in question.
  26 //
  27
  28 namespace {
  29   class GraphBuilder : InstVisitor<GraphBuilder> {
  30     DSGraph &G;
  31     vector<DSNode*> &Nodes;
  32     DSNodeHandle &RetNode;               // Node that gets returned...
  33     map<Value*, DSNodeHandle> &ValueMap;
  34     vector<vector<DSNodeHandle> > &FunctionCalls;
  35
  36   public:
  37     GraphBuilder(DSGraph &g, vector<DSNode*> &nodes, DSNodeHandle &retNode,
  38                  map<Value*, DSNodeHandle> &vm,
  39                  vector<vector<DSNodeHandle> > &fc)
  40       : G(g), Nodes(nodes), RetNode(retNode), ValueMap(vm), FunctionCalls(fc) {
  41       visit(G.getFunction());  // Single pass over the function
  42       removeDeadNodes();
  43     }
  44
  45   private:
  46     // Visitor functions, used to handle each instruction type we encounter...
  47     friend class InstVisitor<GraphBuilder>;
  48     void visitMallocInst(MallocInst &MI) { handleAlloc(MI, DSNode::NewNode); }
  49     void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, DSNode::AllocaNode);}
  50     void handleAlloc(AllocationInst &AI, DSNode::NodeTy NT);
  51
  52     void visitPHINode(PHINode &PN);
  53
  54     void visitGetElementPtrInst(GetElementPtrInst &GEP);
  55     void visitReturnInst(ReturnInst &RI);
  56     void visitLoadInst(LoadInst &LI);
  57     void visitStoreInst(StoreInst &SI);
  58     void visitCallInst(CallInst &CI);
  59     void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
  60     void visitFreeInst(FreeInst &FI) {}         // Ignore free instructions
  61     void visitInstruction(Instruction &I) {
  62 #ifndef NDEBUG
  63       bool bad = isa<PointerType>(I.getType());
  64       for (Instruction::op_iterator i = I.op_begin(), E = I.op_end(); i!=E; ++i)
  65         bad |= isa<PointerType>(i->get()->getType());
  66       if (bad) {
  67         std::cerr << "\n\n\nUNKNOWN PTR INSTRUCTION type: " << I << "\n\n\n";
  68         assert(0 && "Cannot proceed");
  69       }
  70 #endif
  71     }
  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     // getLink - This method is used to either return the specified link in the
  88     // specified node if one exists.  If a link does not already exist (it's
  89     // null), then we create a new node, link it, then return it.
  90     //
  91     DSNode *getLink(DSNode *Node, unsigned Link);
  92
  93     // getSubscriptedNode - Perform the basic getelementptr functionality that
  94     // must be factored out of gep, load and store while they are all MAI's.
  95     //
  96     DSNode *getSubscriptedNode(MemAccessInst &MAI, DSNode *Ptr);
  97
  98     // removeDeadNodes - After the graph has been constructed, this method
  99     // removes all unreachable nodes that are created because they got merged
 100     // with other nodes in the graph.
 101     //
 102     void removeDeadNodes();
 103   };
 104 }
 105
 106 //===----------------------------------------------------------------------===//
 107 // DSGraph constructor - Simply use the GraphBuilder to construct the local
 108 // graph.
 109 DSGraph::DSGraph(Function &F) : Func(F), RetNode(0) {
 110   // Use the graph builder to construct the local version of the graph
 111   GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls);
 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 // getValueNode - Return a DSNode that corresponds the the specified LLVM value.
 131 // This either returns the already existing node, or creates a new one and adds
 132 // it to the graph, if none exists.
 133 //
 134 DSNode *GraphBuilder::getValueNode(Value &V) {
 135   assert(isa<PointerType>(V.getType()) && "Should only use pointer scalars!");
 136   DSNodeHandle &N = ValueMap[&V];
 137   if (N) return N;             // Already have a node?  Just return it...
 138
 139   // Otherwise we need to create a new scalar node...
 140   N = createNode(DSNode::ScalarNode, V.getType());
 141
 142   if (isa<GlobalValue>(V)) {
 143     // Traverse the global graph, adding nodes for them all, and marking them
 144     // all globals.  Be careful to mark functions global as well as the
 145     // potential graph of global variables.
 146     //
 147     DSNode *G = getLink(N, 0);
 148     G->NodeType |= DSNode::GlobalNode;
 149   }
 150
 151   return N;
 152 }
 153
 154 // getLink - This method is used to either return the specified link in the
 155 // specified node if one exists.  If a link does not already exist (it's
 156 // null), then we create a new node, link it, then return it.
 157 //
 158 DSNode *GraphBuilder::getLink(DSNode *Node, unsigned Link) {
 159   assert(Link < Node->getNumLinks() && "Link accessed out of range!");
 160   if (Node->getLink(Link) == 0) {
 161     DSNode::NodeTy NT;
 162     const Type *Ty;
 163
 164     switch (Node->getType()->getPrimitiveID()) {
 165     case Type::PointerTyID:
 166       Ty = cast<PointerType>(Node->getType())->getElementType();
 167       NT = DSNode::ShadowNode;
 168       break;
 169     case Type::ArrayTyID:
 170       Ty = cast<ArrayType>(Node->getType())->getElementType();
 171       NT = DSNode::SubElement;
 172       break;
 173     case Type::StructTyID:
 174       Ty = cast<StructType>(Node->getType())->getContainedType(Link);
 175       NT = DSNode::SubElement;
 176       break;
 177     default:
 178       assert(0 && "Unexpected type to dereference!");
 179       abort();
 180     }
 181
 182     DSNode *New = createNode(NT, Ty);
 183     Node->addEdgeTo(Link, New);
 184   }
 185
 186   return Node->getLink(Link);
 187 }
 188
 189 // getSubscriptedNode - Perform the basic getelementptr functionality that must
 190 // be factored out of gep, load and store while they are all MAI's.
 191 //
 192 DSNode *GraphBuilder::getSubscriptedNode(MemAccessInst &MAI, DSNode *Ptr) {
 193   for (unsigned i = MAI.getFirstIndexOperandNumber(), e = MAI.getNumOperands();
 194        i != e; ++i)
 195     if (MAI.getOperand(i)->getType() == Type::UIntTy)
 196       Ptr = getLink(Ptr, 0);
 197     else if (MAI.getOperand(i)->getType() == Type::UByteTy)
 198       Ptr = getLink(Ptr, cast<ConstantUInt>(MAI.getOperand(i))->getValue());
 199
 200   if (MAI.getFirstIndexOperandNumber() == MAI.getNumOperands())
 201     Ptr = getLink(Ptr, 0);  // All MAI's have an implicit 0 if nothing else.
 202
 203   return Ptr;
 204 }
 205
 206
 207 // removeDeadNodes - After the graph has been constructed, this method removes
 208 // all unreachable nodes that are created because they got merged with other
 209 // nodes in the graph.  These nodes will all be trivially unreachable, so we
 210 // don't have to perform any non-trivial analysis here.
 211 //
 212 void GraphBuilder::removeDeadNodes() {
 213   for (unsigned i = 0; i != Nodes.size(); )
 214     if (!Nodes[i]->getReferrers().empty())
 215       ++i;                                    // This node is alive!
 216     else {                                    // This node is dead!
 217       delete Nodes[i];                        // Free memory...
 218       Nodes.erase(Nodes.begin()+i);           // Remove from node list...
 219     }
 220 }
 221
 222
 223
 224
 225 //===----------------------------------------------------------------------===//
 226 // Specific instruction type handler implementations...
 227 //
 228
 229 // Alloca & Malloc instruction implementation - Simply create a new memory
 230 // object, pointing the scalar to it.
 231 //
 232 void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
 233   DSNode *Scalar = getValueNode(AI);
 234   DSNode *New = createNode(NodeType, AI.getAllocatedType());
 235   Scalar->addEdgeTo(New);   // Make the scalar point to the new node...
 236 }
 237
 238 // PHINode - Make the scalar for the PHI node point to all of the things the
 239 // incoming values point to... which effectively causes them to be merged.
 240 //
 241 void GraphBuilder::visitPHINode(PHINode &PN) {
 242   if (!isa<PointerType>(PN.getType())) return; // Only pointer PHIs
 243
 244   DSNode *Scalar = getValueNode(PN);
 245   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 246     Scalar->mergeWith(getValueNode(*PN.getIncomingValue(i)));
 247 }
 248
 249 void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 250   DSNode *Scalar = getValueNode(GEP);
 251   DSNode *Ptr    = getSubscriptedNode(GEP, getValueNode(*GEP.getOperand(0)));
 252   Scalar->addEdgeTo(Ptr);
 253 }
 254
 255 void GraphBuilder::visitLoadInst(LoadInst &LI) {
 256   if (!isa<PointerType>(LI.getType())) return; // Only pointer PHIs
 257   DSNode *Ptr    = getSubscriptedNode(LI, getValueNode(*LI.getOperand(0)));
 258   getValueNode(LI)->mergeWith(Ptr);
 259 }
 260
 261 void GraphBuilder::visitStoreInst(StoreInst &SI) {
 262   if (!isa<PointerType>(SI.getOperand(0)->getType())) return;
 263   DSNode *Value   = getValueNode(*SI.getOperand(0));
 264   DSNode *DestPtr = getValueNode(*SI.getOperand(1));
 265   Value->mergeWith(getSubscriptedNode(SI, DestPtr));
 266 }
 267
 268 void GraphBuilder::visitReturnInst(ReturnInst &RI) {
 269   if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) {
 270     DSNode *Value = getValueNode(*RI.getOperand(0));
 271     Value->mergeWith(RetNode);
 272     RetNode = Value;
 273   }
 274 }
 275
 276 void GraphBuilder::visitCallInst(CallInst &CI) {
 277   FunctionCalls.push_back(vector<DSNodeHandle>());
 278   vector<DSNodeHandle> &Args = FunctionCalls.back();
 279
 280   for (unsigned i = 0, e = CI.getNumOperands(); i != e; ++i)
 281     if (isa<PointerType>(CI.getOperand(i)->getType()))
 282       Args.push_back(getValueNode(*CI.getOperand(i)));
 283 }