lib/Analysis/DataStructure/DataStructure.cpp

   1 //===- DataStructure.cpp - Implement the core data structure analysis -----===//
   2 //
   3 // This file implements the core data structure functionality.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/DataStructure.h"
   8 #include "llvm/Module.h"
   9 #include "llvm/DerivedTypes.h"
  10 #include <algorithm>
  11 #include "Support/STLExtras.h"
  12
  13 AnalysisID LocalDataStructures::ID(AnalysisID::create<LocalDataStructures>());
  14
  15 //===----------------------------------------------------------------------===//
  16 // DSNode Implementation
  17 //===----------------------------------------------------------------------===//
  18
  19 DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) {
  20   // If this node has any fields, allocate them now, but leave them null.
  21   switch (T->getPrimitiveID()) {
  22   case Type::PointerTyID: Links.resize(1); break;
  23   case Type::ArrayTyID:   Links.resize(1); break;
  24   case Type::StructTyID:
  25     Links.resize(cast<StructType>(T)->getNumContainedTypes());
  26     break;
  27   default: break;
  28   }
  29 }
  30
  31 void DSNode::removeReferrer(DSNodeHandle *H) {
  32   // Search backwards, because we depopulate the list from the back for
  33   // efficiency (because it's a vector).
  34   std::vector<DSNodeHandle*>::reverse_iterator I =
  35     std::find(Referrers.rbegin(), Referrers.rend(), H);
  36   assert(I != Referrers.rend() && "Referrer not pointing to node!");
  37   Referrers.erase(I.base()-1);
  38 }
  39
  40 // addGlobal - Add an entry for a global value to the Globals list.  This also
  41 // marks the node with the 'G' flag if it does not already have it.
  42 //
  43 void DSNode::addGlobal(GlobalValue *GV) {
  44   assert(GV->getType()->getElementType() == Ty);
  45   Globals.push_back(GV);
  46   NodeType |= GlobalNode;
  47 }
  48
  49
  50 // addEdgeTo - Add an edge from the current node to the specified node.  This
  51 // can cause merging of nodes in the graph.
  52 //
  53 void DSNode::addEdgeTo(unsigned LinkNo, DSNode *N) {
  54   assert(LinkNo < Links.size() && "LinkNo out of range!");
  55   if (N == 0 || Links[LinkNo] == N) return;  // Nothing to do
  56   if (Links[LinkNo] == 0) {                  // No merging to perform
  57     Links[LinkNo] = N;
  58     return;
  59   }
  60
  61   // Merge the two nodes...
  62   Links[LinkNo]->mergeWith(N);
  63 }
  64
  65
  66 // mergeWith - Merge this node into the specified node, moving all links to and
  67 // from the argument node into the current node.  The specified node may be a
  68 // null pointer (in which case, nothing happens).
  69 //
  70 void DSNode::mergeWith(DSNode *N) {
  71   if (N == 0 || N == this) return;  // Noop
  72   assert(N->Ty == Ty && N->Links.size() == Links.size() &&
  73          "Cannot merge nodes of two different types!");
  74
  75   // Remove all edges pointing at N, causing them to point to 'this' instead.
  76   while (!N->Referrers.empty())
  77     *N->Referrers.back() = this;
  78
  79   // Make all of the outgoing links of N now be outgoing links of this.  This
  80   // can cause recursive merging!
  81   //
  82   for (unsigned i = 0, e = Links.size(); i != e; ++i) {
  83     addEdgeTo(i, N->Links[i]);
  84     N->Links[i] = 0;  // Reduce unneccesary edges in graph. N is dead
  85   }
  86
  87   // Merge the node types
  88   NodeType |= N->NodeType;
  89   N->NodeType = 0;   // N is now a dead node.
  90
  91   // Merge the globals list...
  92   Globals.insert(Globals.end(), N->Globals.begin(), N->Globals.end());
  93   N->Globals.clear();
  94 }
  95
  96 //===----------------------------------------------------------------------===//
  97 // DSGraph Implementation
  98 //===----------------------------------------------------------------------===//
  99
 100 DSGraph::~DSGraph() {
 101   FunctionCalls.clear();
 102   ValueMap.clear();
 103   RetNode = 0;
 104
 105 #ifndef NDEBUG
 106   // Drop all intra-node references, so that assertions don't fail...
 107   std::for_each(Nodes.begin(), Nodes.end(),
 108                 std::mem_fun(&DSNode::dropAllReferences));
 109 #endif
 110
 111   // Delete all of the nodes themselves...
 112   std::for_each(Nodes.begin(), Nodes.end(), deleter<DSNode>);
 113 }
 114
 115 //===----------------------------------------------------------------------===//
 116 // LocalDataStructures Implementation
 117 //===----------------------------------------------------------------------===//
 118
 119 // releaseMemory - If the pass pipeline is done with this pass, we can release
 120 // our memory... here...
 121 //
 122 void LocalDataStructures::releaseMemory() {
 123   for (std::map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
 124          E = DSInfo.end(); I != E; ++I)
 125     delete I->second;
 126
 127   // Empty map so next time memory is released, data structures are not
 128   // re-deleted.
 129   DSInfo.clear();
 130 }
 131
 132 bool LocalDataStructures::run(Module &M) {
 133   // Calculate all of the graphs...
 134   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 135     if (!I->isExternal()) {
 136       std::map<Function*, DSGraph*>::iterator DI = DSInfo.find(I);
 137       if (DI == DSInfo.end() || DI->second == 0)
 138         DSInfo.insert(std::make_pair(&*I, new DSGraph(*I)));
 139     }
 140
 141   return false;
 142 }