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) {
  // Add the type entry if it is specified...
  if (T) getTypeRec(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;
  }
}

/// foldNodeCompletely - If we determine that this node has some funny
/// behavior happening to it that we cannot represent, we fold it down to a
/// single, completely pessimistic, node.  This node is represented as a
/// single byte with a single TypeEntry of "void".
///
void DSNode::foldNodeCompletely() {
  // We are no longer typed at all...
  TypeEntries.clear();
  TypeEntries.push_back(DSTypeRec(Type::VoidTy, 0));

  // Loop over all of our referrers, making them point to our one byte of space.
  for (vector<DSNodeHandle*>::iterator I = Referrers.begin(), E=Referrers.end();
       I != E; ++I)
    (*I)->setOffset(0);

  // Fold the MergeMap down to a single byte of space...
  MergeMap.resize(1);
  MergeMap[0] = -1;

  // If we have links, merge all of our outgoing links together...
  if (!Links.empty()) {
    MergeMap[0] = 0;      // We now contain an outgoing edge...
    for (unsigned i = 1, e = Links.size(); i != e; ++i)
      Links[0].mergeWith(Links[i]);
    Links.resize(1);
  }
}

/// isNodeCompletelyFolded - Return true if this node has been completely
/// folded down to something that can never be expanded, effectively losing
/// all of the field sensitivity that may be present in the node.
///
bool DSNode::isNodeCompletelyFolded() const {
  return getSize() == 1 && TypeEntries.size() == 1 &&
         TypeEntries[0].Ty == Type::<