path: root/lib/Analysis/DataStructure/DataStructure.cpp

//===- DataStructure.cpp - Implement the core data structure analysis -----===//
//
// This file implements the core data structure functionality.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DSGraph.h"
#include "llvm/Function.h"
#include "llvm/iOther.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
#include "Support/STLExtras.h"
#include "Support/Statistic.h"
#include <algorithm>
#include <set>

using std::vector;

// TODO: FIXME
namespace DataStructureAnalysis {
  // isPointerType - Return true if this first class type is big enough to hold
  // a pointer.
  //
  bool isPointerType(const Type *Ty);
  extern TargetData TD;
}
using namespace DataStructureAnalysis;

//===----------------------------------------------------------------------===//
// DSNode Implementation
//===----------------------------------------------------------------------===//

DSNode::DSNode(enum NodeTy NT, const Type *T) : NodeType(NT) {
  // If this node is big enough to have pointer fields, add space for them now.
  if (T != Type::VoidTy && !isa<FunctionType>(T)) { // Avoid TargetData assert's
    MergeMap.resize(TD.getTypeSize(T));

    // Assign unique values to all of the elements of MergeMap
    if (MergeMap.size() < 128) {
      // Handle the common case of reasonable size structures...
      for (unsigned i = 0, e = MergeMap.size(); i != e; ++i)
        MergeMap[i] = -1-i;   // Assign -1, -2, -3, ...
    } else {
      // It's possible that we have something really big here.  In this case,
      // divide the object into chunks until it will fit into 128 elements.
      unsigned Multiple = MergeMap.size()/128;

      // It's probably an array, and probably some power of two in size.
      // Because of this, find the biggest power of two that is bigger than
      // multiple to use as our real Multiple.
      unsigned RealMultiple = 2;
      while (RealMultiple <= Multiple) RealMultiple <<= 1;

      unsigned RealBound = MergeMap.size()/RealMultiple;
      assert(RealBound <= 128 && "Math didn't work out right");

      // Now go through and assign indexes that are between -1 and -128
      // inclusive
      //
      for (unsigned i = 0, e = MergeMap.size(); i != e; ++i)
        MergeMap[i] = -1-(i % RealBound);   // Assign -1, -2, -3...
    }
  }

  TypeEntries.push_back(TypeRec(T, 0));
}

// DSNode copy constructor... do not copy over the referrers list!
DSNode::DSNode(const DSNode &N)
  : Links(N.Links), MergeMap(N.MergeMap),
    TypeEntries(N.TypeEntries), Globals(N.Globals), NodeType(N.NodeType) {
}

void DSNode::removeReferrer(DSNodeHandle *H) {
  // Search backwards, because we depopulate the list from the back for
  // efficiency (because it's a vector).
  vector<DSNodeHandle*>::reverse_iterator I =
    std::find(Referrers.rbegin(), Referrers.rend(), H);
  assert(I != Referrers.rend() && "Referrer not pointing to node!");
  Referrers.erase(I.base()-1);
}

// addGlobal - Add an entry for a global value to the Globals list.  This also
// marks the node with the 'G' flag if it does not already have it.
//
void DSNode::addGlobal(GlobalValue *GV) {
  // Keep the list sorted.
  vector<GlobalValue*>::iterator I =
    std::lower_bound(Globals.begin(), Globals.end(), GV);

  if (I == Globals.end() || *I != GV) {
    //assert(GV->getType()->getElementType() == Ty);
    Globals.insert(I, GV);
    NodeType |= GlobalNode;
  }
}


/// setLink - Set the link at the specified offset to the specified
/// NodeHandle, replacing what was there.  It is uncommon to use this method,
/// instead one of the higher level methods should be used, below.
///
void DSNode::setLink(unsigned i, const DSNodeHandle &NH) {
  // Create a new entry in the Links vector to hold a new element for offset.
  if (!hasLink(i)) {
    signed char NewIdx = Links.size();
    // Check to see if we allocate more than 128 distinct links for this node.
    // If so, just merge with the last one.  This really shouldn't ever happen,
    // but it should work regardless of whether it does or not.
    //
    if (NewIdx >= 0) {
      Links.push_back(NH);             // Allocate space: common case
    } else {                           // Wrap around?  Too many links?
      NewIdx--;                        // Merge with whatever happened last
      assert(NewIdx > 0 && "Should wrap back around");
      std::cerr << "\n*** DSNode found that requires more than 128 "
                << "active links at once!\n\n";
    } 

    signed char OldIdx = MergeMap[i];