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 "Support/Timer.h"
#include <algorithm>

namespace {
  Statistic<> NumFolds          ("dsnode", "Number of nodes completely folded");
  Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged");
};

namespace DS {   // TODO: FIXME
  extern TargetData TD;
}
using namespace DS;

DSNode *DSNodeHandle::HandleForwarding() const {
  assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!");

  // Handle node forwarding here!
  DSNode *Next = N->ForwardNH.getNode();  // Cause recursive shrinkage
  Offset += N->ForwardNH.getOffset();

  if (--N->NumReferrers == 0) {
    // Removing the last referrer to the node, sever the forwarding link
    N->stopForwarding();
  }

  N = Next;
  N->NumReferrers++;
  if (N->Size <= Offset) {
    assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?");
    Offset = 0;
  }
  return N;
}

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

DSNode::DSNode(unsigned NT, const Type *T, DSGraph *G)
  : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(NT) {
  // Add the type entry if it is specified...
  if (T) mergeTypeInfo(T, 0);
  G->getNodes().push_back(this);
}

// DSNode copy constructor... do not copy over the referrers list!
DSNode::DSNode(const DSNode &N, DSGraph *G)
  : NumReferrers(0), Size(N.Size), ParentGraph(G), Ty(N.Ty),
    Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) {
  G->getNodes().push_back(this);
}

void DSNode::assertOK() const {
  assert((Ty != Type::VoidTy ||
          Ty == Type::VoidTy && (Size == 0 ||
                                 (NodeType & DSNode::Array))) &&
         "Node not OK!");
}

/// forwardNode - Mark this node as being obsolete, and all references to it
/// should be forwarded to the specified node and offset.
///
void DSNode::forwardNode(DSNode *To, unsigned Offset) {
  assert(this != To && "Cannot forward a node to itself!");
  assert(ForwardNH.isNull() && "Already forwarding from this node!");