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 // addEdgeTo - Add an edge from the current node to the specified node.  This
  41 // can cause merging of nodes in the graph.
  42 //
  43 void DSNode::addEdgeTo(unsigned LinkNo, DSNode *N) {
  44   assert(LinkNo < Links.size() && "LinkNo out of range!");
  45   if (N == 0 || Links[LinkNo] == N) return;  // Nothing to do
  46   if (Links[LinkNo] == 0) {                  // No merging to perform
  47     Links[LinkNo] = N;
  48     return;
  49   }
  50
  51   // Merge the two nodes...
  52   Links[LinkNo]->mergeWith(N);
  53 }
  54
  55
  56 // mergeWith - Merge this node into the specified node, moving all links to and
  57 // from the argument node into the current node.  The specified node may be a
  58 // null pointer (in which case, nothing happens).
  59 //
  60 void DSNode::mergeWith(DSNode *N) {
  61   if (N == 0 || N == this) return;  // Noop
  62   assert(N->Ty == Ty && N->Links.size() == Links.size() &&
  63          "Cannot merge nodes of two different types!");
  64
  65   // Remove all edges pointing at N, causing them to point to 'this' instead.
  66   while (!N->Referrers.empty())
  67     *N->Referrers.back() = this;
  68
  69   // Make all of the outgoing links of N now be outgoing links of this.  This
  70   // can cause recursive merging!
  71   //
  72   for (unsigned i = 0, e = Links.size(); i != e; ++i) {
  73     addEdgeTo(i, N->Links[i]);
  74     N->Links[i] = 0;  // Reduce unneccesary edges in graph. N is dead
  75   }
  76
  77   NodeType |= N->NodeType;
  78   N->NodeType = 0;   // N is now a dead node.
  79 }
  80
  81 //===----------------------------------------------------------------------===//
  82 // DSGraph Implementation
  83 //===----------------------------------------------------------------------===//
  84
  85 DSGraph::~DSGraph() {
  86   FunctionCalls.clear();
  87   ValueMap.clear();
  88   RetNode = 0;
  89
  90 #ifndef NDEBUG
  91   // Drop all intra-node references, so that assertions don't fail...
  92   std::for_each(Nodes.begin(), Nodes.end(),
  93                 std::mem_fun(&DSNode::dropAllReferences));
  94 #endif
  95
  96   // Delete all of the nodes themselves...
  97   std::for_each(Nodes.begin(), Nodes.end(), deleter<DSNode>);
  98 }
  99
 100 //===----------------------------------------------------------------------===//
 101 // LocalDataStructures Implementation
 102 //===----------------------------------------------------------------------===//
 103
 104 // releaseMemory - If the pass pipeline is done with this pass, we can release
 105 // our memory... here...
 106 //
 107 void LocalDataStructures::releaseMemory() {
 108   for (std::map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
 109          E = DSInfo.end(); I != E; ++I)
 110     delete I->second;
 111
 112   // Empty map so next time memory is released, data structures are not
 113   // re-deleted.
 114   DSInfo.clear();
 115 }
 116
 117 bool LocalDataStructures::run(Module &M) {
 118   // Calculate all of the graphs...
 119   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 120     if (!I->isExternal()) {
 121       std::map<Function*, DSGraph*>::iterator DI = DSInfo.find(I);
 122       if (DI == DSInfo.end() || DI->second == 0)
 123         DSInfo.insert(std::make_pair(&*I, new DSGraph(*I)));
 124     }
 125
 126   return false;
 127 }