poolalloc/lib/DSA/DataStructure.cpp

//===- DataStructure.cpp - Implement the core data structure analysis -----===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the core data structure functionality.
//
//===----------------------------------------------------------------------===//

#include "dsa/DSGraphTraits.h"
#include "dsa/DataStructure.h"
#include "dsa/DSGraph.h"
#include "dsa/DSSupport.h"
#include "dsa/DSNode.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"

#include <iostream>
#include <algorithm>
using namespace llvm;

#define COLLAPSE_ARRAYS_AGGRESSIVELY 0
namespace {
  STATISTIC (NumFolds, "Number of nodes completely folded");
  STATISTIC (NumNodeAllocated  , "Number of nodes allocated");
}

/// isForwarding - Return true if this NodeHandle is forwarding to another
/// one.
bool DSNodeHandle::isForwarding() const {
  return N && N->isForwarding();
}

DSNode *DSNodeHandle::HandleForwarding() const {
  assert(N->isForwarding() && "Can only be invoked if forwarding!");
  DEBUG(
        { //assert not looping
          DSNode* NH = N;
          sv::set<DSNode*> seen;
          while(NH && NH->isForwarding()) {
            assert(seen.find(NH) == seen.end() && "Loop detected");
            seen.insert(NH);
            NH = NH->ForwardNH.N;
          }
        }
        );
  // 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->getSize() <= Offset) {
    assert(N->getSize() <= 1 && "Forwarded to shrunk but not collapsed node?");
    Offset = 0;
  }
  return N;
}

//===----------------------------------------------------------------------===//
// DSScalarMap Implementation
//===----------------------------------------------------------------------===//

DSNodeHandle &DSScalarMap::AddGlobal(const GlobalValue *GV) {
  assert(ValueMap.count(GV) == 0 && "GV already exists!");

  // If the node doesn't exist, check to see if it's a global that is
  // equated to another global in the program.
  EquivalenceClasses<const GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
  if (ECI != GlobalECs.end()) {
    const GlobalValue *Leader = *GlobalECs.findLeader(ECI);
    if (Leader != GV) {
      GV = Leader;
      iterator I = ValueMap.find(GV);
      if (I != ValueMap.end())
        return I->second;
    }
  }

  // Okay, this is either not an equivalenced global or it is the leader, it
  // will be inserted into the scalar map now.
  GlobalSet.insert(GV);

  return ValueMap.insert(std::make_pair(GV, DSNodeHandle())).first->second;
}

/// spliceFrom - Copy all entries from RHS, then clear RHS.
///
void DSScalarMap::spliceFrom(DSScalarMap &RHS) {
  // Special case if this is empty.
  if (ValueMap.empty()) {
    ValueMap.swap(RHS.ValueMap);
    GlobalSet.swap(RHS.GlobalSet);
  } else {
    GlobalSet.insert(RHS.GlobalSet.begin(), RHS.GlobalSet.end());
    for (ValueMapTy::iterator I = RHS.ValueMap.begin(), E = RHS.ValueMap.end();
         I != E; ++I)
      ValueMap[I->first].mergeWith(I->second);
    RHS.ValueMap.clear();
  }
}

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

DSNode::DSNode(DSGraph *G)
: NumReferrers(0), Size(0), ParentGraph(G), NodeType(0) {
  // Add the type entry if it is specified...
  if (G) G->addNode(this);
  ++NumNodeAllocated;
}

// DSNode copy constructor... do not copy over the referrers list!
DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks)
  : NumReferrers(0), Size(N.Size), ParentGraph(G), TyMap(N.TyMap),
    Globals(N.Globals), NodeType(N.NodeType) {
  if (!NullLinks) Links = N.Links;
  G->addNode(this);
  ++NumNodeAllocated;
}

DSNode::~DSNode() {
  dropAllReferences();
  assert(hasNoReferrers() && "Referrers to dead node exist!");
}

void DSNode::assertOK() const {
//  assert(((Ty && Ty->getTypeID() != Type::VoidTyID) ||
//         ((!Ty || Ty->getTypeID() == Type::VoidTyID) && (Size == 0 ||
//         (NodeType & DSNode::ArrayNode)))) &&
//         "Node not OK!");

  assert(ParentGraph && "Node has no parent?");
  const DSScalarMap &SM = ParentGraph->getScalarMap();
  for (globals_iterator ii = globals_begin(), ee = globals_end();
       ii != ee; ++ii) {
    assert(SM.global_count(*ii));
    assert(SM.find(*ii)->second.getNode() == this);
  }
}

/// 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!");
  if (To->Size <= 1) Offset = 0;
  assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) &&
         "Forwarded offset is wrong!");
  ForwardNH.setTo(To, Offset);
  NodeType = DeadNode;
  Size = 0;

  DSNodeHandle ToNH(To,Offset);

  //Move the Links
  for (unsigned x = 0, xe = Links.size(); x != xe; ++x)
    if (!Links[x].isNull()) {
      // Compute the offset into the current node at which to
      // merge this link.  In the common case, this is a linear
      // relation to the offset in the original node (with
      // wrapping), but if the current node gets collapsed due to
      // recursive merging, we must make sure to merge in all remaining
      // links at offset zero.
      unsigned MergeOffset = 0;
      if (ToNH.getNode()->getSize() != 1)
        MergeOffset = (x + Offset) % ToNH.getNode()->getSize();
      ToNH.getNode()->addEdgeTo(MergeOffset, Links[x]);
    }
  Links.clear();

  // Remove this node from the parent graph's Nodes list.
  ParentGraph->unlinkNode(this);
  ParentGraph = 0;
}

// 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(const GlobalValue *GV) {
  // First, check to make sure this is the leader if the global is in an
  // equivalence class.
  GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV);

  Globals.insert(GV);
  setGlobalMarker();
}

void DSNode::addFunction(const Function* F) {
  addGlobal(F);
}

// removeGlobal - Remove the specified global that is explicitly in the globals
// list.
void DSNode::removeGlobal(const GlobalValue *GV) {
  assert (Globals.count(GV) && "Global not in Node!");
  Globals.erase(GV);
}

/// 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() {
  if (isNodeCompletelyFolded()) return;  // If this node is already folded...

//  assert(0 && "Folding is happening");

  ++NumFolds;

  //Collapsed nodes don't really need a type
  TyMap.clear();

  // If this node has a size that is <= 1, we don't need to create a forwarding
  // node.
  if (getSize() <= 1) {
    setCollapsedMarker();
    Size = 1;
    assert(Links.size() <= 1 && "Size is 1, but has more links?");
  } else {
    // Create the node we are going to forward to.  This is required because
    // some referrers may have an offset that is > 0.  By forcing them to
    // forward, the forwarder has the opportunity to correct the offset.
    DSNode *DestNode = new DSNode(ParentGraph);
    DestNode->NodeType = NodeType;
    DestNode->setCollapsedMarker();
    DestNode->Size = 1;
    DestNode->Globals.swap(Globals);

    // Start forwarding to the destination node...
    forwardNode(DestNode, 0);

  }
}

/// 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  isCollapsedNode();
}

/// addFullGlobalsList - Compute the full set of global values that are
/// represented by this node.  Unlike getGlobalsList(), this requires fair
/// amount of work to compute, so don't treat this method call as free.
void DSNode::addFullGlobalsList(std::vector<const GlobalValue*> &List) const {
  if (globals_begin() == globals_end()) return;

  EquivalenceClasses<const GlobalValue*> &EC = getParentGraph()->getGlobalECs();

  for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
    EquivalenceClasses<const GlobalValue*>::iterator ECI = EC.findValue(*I);
    if (ECI == EC.end())
      List.push_back(*I);
    else
      List.insert(List.end(), EC.member_begin(ECI), EC.member_end());
  }
}

/// addFullFunctionList - Identical to addFullGlobalsList, but only return the
/// functions in the full list.
void DSNode::addFullFunctionList(std::vector<const Function*> &List) const {
  if (globals_begin() == globals_end()) return;

  EquivalenceClasses<const GlobalValue*> &EC = getParentGraph()->getGlobalECs();

  for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
    EquivalenceClasses<const GlobalValue*>::iterator ECI = EC.findValue(*I);
    if (ECI == EC.end()) {
      if (const Function *F = dyn_cast<Function>(*I))
        List.push_back(F);
    } else {
      for (EquivalenceClasses<const GlobalValue*>::member_iterator MI =
             EC.member_begin(ECI), E = EC.member_end(); MI != E; ++MI)
        if (const Function *F = dyn_cast<Function>(*MI))
          List.push_back(F);
    }
  }
}

/// mergeTypeInfo - This method merges the specified type into the current node
/// at the specified offset.  This may update the current node's type record if
/// this gives more information to the node, it may do nothing to the node if
/// this information is already known, or it may merge the node completely (and
/// return true) if the information is incompatible with what is already known.
///
/// This method returns true if the node is completely folded, otherwise false.
///
void DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) {

  if (!NewTy || NewTy->isVoidTy()) return;

  if (isCollapsedNode()) return;
  if (isArrayNode()) Offset %= getSize();

  if (Offset >= getSize()) growSize(Offset+1);

  TyMap[Offset] = getParentGraph()->getTypeSS().getOrCreate(TyMap[Offset], NewTy);
  assert(TyMap[Offset]);
}

void DSNode::mergeTypeInfo(const TyMapTy::mapped_type TyIt, unsigned Offset) {
  if (isCollapsedNode()) return;
  if (isArrayNode()) Offset %= getSize();

  if (Offset >= getSize())
    growSize(Offset + 1);

  if (!TyMap[Offset])
    TyMap[Offset] = TyIt;
  if (TyIt) {
    sv::set<const Type*> S(*TyMap[Offset]);
    S.insert(TyIt->begin(), TyIt->end());
    TyMap[Offset] = getParentGraph()->getTypeSS().getOrCreate(S);
  }
  assert(TyMap[Offset]);
}

void DSNode::mergeTypeInfo(const DSNode* DN, unsigned Offset) {
  if (isCollapsedNode()) return;

  for (TyMapTy::const_iterator ii = DN->TyMap.begin(), ee = DN->TyMap.end();
       ii != ee; ++ii)
    mergeTypeInfo(ii->second, ii->first + Offset);
}

/// addEdgeTo - Add an edge from the current node to the specified node.  This
/// can cause merging of nodes in the graph.
///
void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
  if (NH.isNull()) return;       // Nothing to do

  if (isNodeCompletelyFolded())
    Offset = 0;

  DSNodeHandle &ExistingEdge = getLink(Offset);
  if (!ExistingEdge.isNull()) {
    // Merge the two nodes...
    ExistingEdge.mergeWith(NH);
  } else {                             // No merging to perform...
    setLink(Offset, NH);               // Just force a link in there...
  }
}


void DSNode::mergeGlobals(const DSNode &RHS) {
  Globals.insert(RHS.Globals.begin(), RHS.Globals.end());
}

static unsigned gcd(unsigned m, unsigned n) {
  if (m < n) return gcd(n,m);
  unsigned r = m % n;
  if (r == 0) {
    return n;
  } else {
    return gcd(n, r);
  }
}

// MergeNodes - Helper function for DSNode::mergeWith().
// This function does the hard work of merging two nodes, CurNodeH
// and NH after filtering out trivial cases and making sure that
// CurNodeH.offset >= NH.offset.
//
// ***WARNING***
// Since merging may cause either node to go away, we must always
// use the node-handles to refer to the nodes.  These node handles are
// automatically updated during merging, so will always provide access
// to the correct node after a merge.
//
void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
  assert(CurNodeH.getOffset() >= NH.getOffset() &&
         "This should have been enforced in the caller.");
  assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() &&
         "Cannot merge two nodes that are not in the same graph!");

  // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with
  // respect to NH.Offset) is now zero.  NOffset is the distance from the base
  // of our object that N starts from.
  //
  unsigned NOffset = CurNodeH.getOffset()-NH.getOffset();
  unsigned NSize = NH.getNode()->getSize();

  // If the two nodes are of different size, and the smaller node has the array
  // bit set, collapse!
  if (NSize != CurNodeH.getNode()->getSize()) {
#if COLLAPSE_ARRAYS_AGGRESSIVELY
    if (NSize < CurNodeH.getNode()->getSize()) {
      if (NH.getNode()->isArray())
        NH.getNode()->foldNodeCompletely();
    } else if (CurNodeH.getNode()->isArray()) {
      NH.getNode()->foldNodeCompletely();
    }
#endif
  }

  // If we are merging a node with a completely folded node, then both nodes are
  // now completely folded.
  //
  if (CurNodeH.getNode()->isNodeCompletelyFolded()) {
    if (!NH.getNode()->isNodeCompletelyFolded()) {
      NH.getNode()->foldNodeCompletely();
      assert(NH.getNode() && NH.getOffset() == 0 &&
             "folding did not make offset 0?");
      NOffset = NH.getOffset();
      NSize = NH.getNode()->getSize();
      assert(NOffset == 0 && NSize == 1);
    }
  } else if (NH.getNode()->isNodeCompletelyFolded()) {
    CurNodeH.getNode()->foldNodeCompletely();
    assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 &&
           "folding did not make offset 0?");
    NSize = NH.getNode()->getSize();
    NOffset = NH.getOffset();
    assert(NOffset == 0 && NSize == 1);
  } 

  DSNode *N = NH.getNode();
  if (CurNodeH.getNode() == N || N == 0) return;
  assert(!CurNodeH.getNode()->isDeadNode());

  // Merge the type entries of the two nodes together...
  CurNodeH.getNode()->mergeTypeInfo(NH.getNode(), NOffset);
  if (NH.getNode()->getSize() + NOffset > CurNodeH.getNode()->getSize())
    CurNodeH.getNode()->growSize(NH.getNode()->getSize() + NOffset);
  assert(!CurNodeH.getNode()->isDeadNode());

  // Merge the NodeType information.
  CurNodeH.getNode()->NodeType |= N->NodeType;

  // Start forwarding to the new node!
  N->forwardNode(CurNodeH.getNode(), NOffset);
  assert(!CurNodeH.getNode()->isDeadNode());

  // Merge the globals list...
  CurNodeH.getNode()->mergeGlobals(*N);

  // Delete the globals from the old node...
  N->Globals.clear();
}


/// mergeWith - Merge this node and the specified node, moving all links to and
/// from the argument node into the current node, deleting the node argument.
/// Offset indicates what offset the specified node is to be merged into the
/// current node.
///
/// The specified node may be a null pointer (in which case, we update it to
/// point to this node).
///
void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
  //DOUT << "mergeWith: " << this << " becomes " << NH.getNode() << "\n";
  DSNode *N = NH.getNode();
  if (N == this && NH.getOffset() == Offset)
    return;  // Noop

  // If the RHS is a null node, make it point to this node!
  if (N == 0) {
    NH.mergeWith(DSNodeHandle(this, Offset));
    return;
  }

  assert(!N->isDeadNode() && !isDeadNode());
  assert(!hasNoReferrers() && "Should not try to fold a useless node!");

  if (N == this) {
    // We cannot merge two pieces of the same node together, collapse the node
    // completely.
    DEBUG(errs() << "Attempting to merge two chunks of the same node together!\n");
    foldNodeCompletely();
    return;
  }

  // If both nodes are not at offset 0, make sure that we are merging the node
  // at an later offset into the node with the zero offset.
  //
  if (Offset < NH.getOffset()) {
    N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
    return;
  } else if (Offset == NH.getOffset() && getSize() < N->getSize()) {
    // If the offsets are the same, merge the smaller node into the bigger node
    N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
    return;
  }

  // Ok, now we can merge the two nodes.  Use a static helper that works with
  // two node handles, since "this" may get merged away at intermediate steps.
  DSNodeHandle CurNodeH(this, Offset);
  DSNodeHandle NHCopy(NH);
  if (CurNodeH.getOffset() >= NHCopy.getOffset())
    DSNode::MergeNodes(CurNodeH, NHCopy);
  else
    DSNode::MergeNodes(NHCopy, CurNodeH);
}

void DSNode::cleanEdges() {
  //get rid of any type edge pointing to the null type
  for (type_iterator ii = type_begin(); ii != type_end(); ) {
    if (ii->second)
      ++ii;
    else {
      type_iterator backup = ii;
      ++backup;
      TyMap.erase(ii);
      ii = backup;
    }
  }
  //get rid of any node edge pointing to nothing
  for (edge_iterator ii = edge_begin(); ii != edge_end(); ) {
    if (ii->second.isNull()) {
      edge_iterator backup = ii;
      ++backup;
      Links.erase(ii);
      ii = backup;
    } else
      ++ii;
  }
}

//===----------------------------------------------------------------------===//
// ReachabilityCloner Implementation
//===----------------------------------------------------------------------===//

DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) {
  if (SrcNH.isNull()) return DSNodeHandle();
  const DSNode *SN = SrcNH.getNode();

  DSNodeHandle &NH = NodeMap[SN];
  if (!NH.isNull()) { // Node already mapped?
    DSNode *NHN = NH.getNode();
    return DSNodeHandle(NHN, NH.getOffset() + SrcNH.getOffset());
  }
  
  // If SrcNH has globals and the destination graph has one of the same globals,
  // merge this node with the destination node, which is much more efficient.
  if (SN->globals_begin() != SN->globals_end()) {
    DSScalarMap &DestSM = Dest->getScalarMap();
    for (DSNode::globals_iterator I = SN->globals_begin(),E = SN->globals_end();
         I != E; ++I) {
      const GlobalValue *GV = *I;
      DSScalarMap::iterator GI = DestSM.find(GV);
      if (GI != DestSM.end() && !GI->second.isNull()) {
        // We found one, use merge instead!
        merge(GI->second, Src->getNodeForValue(GV));
        assert(!NH.isNull() && "Didn't merge node!");
        DSNode *NHN = NH.getNode();
        return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset());
      }
    }
  }

  if (!createDest) return DSNodeHandle(0,0);

  DSNode *DN = new DSNode(*SN, Dest, true /* Null out all links */);
  DN->maskNodeTypes(BitsToKeep);
  NH = DN;
  //DOUT << "getClonedNH: " << SN << " becomes " << DN << "\n";

  // Next, recursively clone all outgoing links as necessary.  Note that
  // adding these links can cause the node to collapse itself at any time, and
  // the current node may be merged with arbitrary other nodes.  For this
  // reason, we must always go through NH.
  DN = 0;
  for (DSNode::const_edge_iterator ii = SN->edge_begin(), ee = SN->edge_end();
       ii != ee; ++ii) {
    const DSNodeHandle &SrcEdge = ii->second;
    if (!SrcEdge.isNull()) {
      const DSNodeHandle &DestEdge = getClonedNH(SrcEdge);
      // Compute the offset into the current node at which to
      // merge this link.  In the common case, this is a linear
      // relation to the offset in the original node (with
      // wrapping), but if the current node gets collapsed due to
      // recursive merging, we must make sure to merge in all remaining
      // links at offset zero.
      unsigned MergeOffset = 0;
      DSNode *CN = NH.getNode();
      if (CN->getSize() != 1)
        MergeOffset = (ii->first + NH.getOffset()) % CN->getSize();
      CN->addEdgeTo(MergeOffset, DestEdge);
    }
  }

  // If this node contains any globals, make sure they end up in the scalar
  // map with the correct offset.
  for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end();
       I != E; ++I) {
    const GlobalValue *GV = *I;
    const DSNodeHandle &SrcGNH = Src->getNodeForValue(GV);
    DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
    assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent");
    Dest->getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
                                        DestGNH.getOffset()+SrcGNH.getOffset()));
  }
  NH.getNode()->mergeGlobals(*SN);

  return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
}

void ReachabilityCloner::merge(const DSNodeHandle &NH,
                               const DSNodeHandle &SrcNH) {
  if (SrcNH.isNull()) return;  // Noop
  if (NH.isNull()) {
    // If there is no destination node, just clone the source and assign the
    // destination node to be it.
    NH.mergeWith(getClonedNH(SrcNH));
    return;
  }

  // Okay, at this point, we know that we have both a destination and a source
  // node that need to be merged.  Check to see if the source node has already
  // been cloned.
  const DSNode *SN = SrcNH.getNode();
  DSNodeHandle &SCNH = NodeMap[SN];  // SourceClonedNodeHandle
  if (!SCNH.isNull()) {   // Node already cloned?
    DSNode *SCNHN = SCNH.getNode();
    NH.mergeWith(DSNodeHandle(SCNHN,
                              SCNH.getOffset()+SrcNH.getOffset()));
    return;  // Nothing to do!
  }

  // Okay, so the source node has not already been cloned.  Instead of creating
  // a new DSNode, only to merge it into the one we already have, try to perform
  // the merge in-place.  The only case we cannot handle here is when the offset
  // into the existing node is less than the offset into the virtual node we are
  // merging in.  In this case, we have to extend the existing node, which
  // requires an allocation anyway.
  DSNode *DN = NH.getNode();   // Make sure the Offset is up-to-date
  if (NH.getOffset() >= SrcNH.getOffset()) {
    if (!DN->isNodeCompletelyFolded()) {
      // Make sure the destination node is folded if the source node is folded.
      if (SN->isNodeCompletelyFolded()) {
        DN->foldNodeCompletely();
        DN = NH.getNode();
      } else if (SN->getSize() != DN->getSize()) {
        // If the two nodes are of different size, and the smaller node has the
        // array bit set, collapse!
#if COLLAPSE_ARRAYS_AGGRESSIVELY
        if (SN->getSize() < DN->getSize()) {
          if (SN->isArray()) {
            DN->foldNodeCompletely();
            DN = NH.getNode();
          }
        } else if (DN->isArray()) {
          DN->foldNodeCompletely();
          DN = NH.getNode();
        }
#endif
      }
      if (DN->getSize() < SN->getSize())
        DN->growSize(SN->getSize());

      // Merge the type entries of the two nodes together...
      if (!DN->isNodeCompletelyFolded())
          DN->mergeTypeInfo(SN, NH.getOffset() - SrcNH.getOffset());

    }

    assert(!DN->isDeadNode());

    // Merge the NodeType information.
    DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep);

    // Before we start merging outgoing links and updating the scalar map, make
    // sure it is known that this is the representative node for the src node.
    SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset());

    // If the source node contains any globals, make sure they end up in the
    // scalar map with the correct offset.
    if (SN->globals_begin() != SN->globals_end()) {
      // Update the globals in the destination node itself.
      DN->mergeGlobals(*SN);

      // Update the scalar map for the graph we are merging the source node
      // into.
      for (DSNode::globals_iterator I = SN->globals_begin(),
             E = SN->globals_end(); I != E; ++I) {
        const GlobalValue *GV = *I;
        const DSNodeHandle &SrcGNH = Src->getNodeForValue(GV);
        DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
        assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
        Dest->getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
                                      DestGNH.getOffset()+SrcGNH.getOffset()));
      }
      NH.getNode()->mergeGlobals(*SN);
    }
  } else {
    // We cannot handle this case without allocating a temporary node.  Fall
    // back on being simple.
    DSNode *NewDN = new DSNode(*SN, Dest, true /* Null out all links */);
    NewDN->maskNodeTypes(BitsToKeep);

    unsigned NHOffset = NH.getOffset();
    NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset()));

    assert(NH.getNode() &&
           (NH.getOffset() > NHOffset ||
            (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) &&
           "Merging did not adjust the offset!");

    // Before we start merging outgoing links and updating the scalar map, make
    // sure it is known that this is the representative node for the src node.
    SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset());

    // If the source node contained any globals, make sure to create entries
    // in the scalar map for them!
    for (DSNode::globals_iterator I = SN->globals_begin(),
           E = SN->globals_end(); I != E; ++I) {
      const GlobalValue *GV = *I;
      const DSNodeHandle &SrcGNH = Src->getNodeForValue(GV);
      DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
      assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
      assert(SrcGNH.getNode() == SN && "Global mapping inconsistent");
      Dest->getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
                                    DestGNH.getOffset()+SrcGNH.getOffset()));
    }
  }

  //  DOUT << "LLVA: mergeWith: " << SN << " becomes " << DN << "\n";

  // Next, recursively merge all outgoing links as necessary.  Note that
  // adding these links can cause the destination node to collapse itself at
  // any time, and the current node may be merged with arbitrary other nodes.
  // For this reason, we must always go through NH.
  DN = 0;
  for (DSNode::const_edge_iterator ii = SN->edge_begin(), ee = SN->edge_end();
       ii != ee; ++ii) {
    const DSNodeHandle &SrcEdge = ii->second;
    if (!SrcEdge.isNull()) {
      // Compute the offset into the current node at which to
      // merge this link.  In the common case, this is a linear
      // relation to the offset in the original node (with
      // wrapping), but if the current node gets collapsed due to
      // recursive merging, we must make sure to merge in all remaining
      // links at offset zero.
      DSNode *CN = SCNH.getNode();
      unsigned MergeOffset = (ii->first+SCNH.getOffset()) % CN->getSize();

      DSNodeHandle Tmp = CN->getLink(MergeOffset);
      if (!Tmp.isNull()) {
        // Perform the recursive merging.  Make sure to create a temporary NH,
        // because the Link can disappear in the process of recursive merging.
        merge(Tmp, SrcEdge);
      } else {
        Tmp.mergeWith(getClonedNH(SrcEdge));
        // Merging this could cause all kinds of recursive things to happen,
        // culminating in the current node being eliminated.  Since this is
        // possible, make sure to reaquire the link from 'CN'.

        unsigned MergeOffset = 0;
        CN = SCNH.getNode();
        MergeOffset = (ii->first + SCNH.getOffset()) % CN->getSize();
        CN->getLink(MergeOffset).mergeWith(Tmp);
      }
    }
  }
}

/// mergeCallSite - Merge the nodes reachable from the specified src call
/// site into the nodes reachable from DestCS.
void ReachabilityCloner::mergeCallSite(DSCallSite &DestCS,
                                       const DSCallSite &SrcCS) {
  merge(DestCS.getRetVal(), SrcCS.getRetVal());
  unsigned MinArgs = DestCS.getNumPtrArgs();
  if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs();

  for (unsigned a = 0; a != MinArgs; ++a)
    merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a));

  for (unsigned a = MinArgs, e = SrcCS.getNumPtrArgs(); a != e; ++a)
    DestCS.addPtrArg(getClonedNH(SrcCS.getPtrArg(a)));
}

DSCallSite ReachabilityCloner::cloneCallSite(const DSCallSite& SrcCS) {
  std::vector<DSNodeHandle> Args;
  for(unsigned x = 0; x < SrcCS.getNumPtrArgs(); ++x)
    Args.push_back(getClonedNH(SrcCS.getPtrArg(x)));
  if (SrcCS.isDirectCall())
    return DSCallSite(SrcCS.getCallSite(),
                      getClonedNH(SrcCS.getRetVal()),
                      SrcCS.getCalleeFunc(),
                      Args);
  else
    return DSCallSite(SrcCS.getCallSite(),
                      getClonedNH(SrcCS.getRetVal()),
                      getClonedNH(SrcCS.getCalleeNode()).getNode(),
                      Args);
}

//===----------------------------------------------------------------------===//
// DSCallSite Implementation
//===----------------------------------------------------------------------===//

// Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h
const Function &DSCallSite::getCaller() const {
  return *Site.getInstruction()->getParent()->getParent();
}

void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
                        ReachabilityCloner &RC) {
  NH = RC.getClonedNH(Src);
}

/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
///
void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) {
  for (LinkMapTy::iterator ii = edge_begin(), ee = edge_end();
       ii != ee; ++ii)
    if (DSNode *N = ii->second.getNode()) {
      DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N);
      if (ONMI != OldNodeMap.end()) {
        DSNode *ONMIN = ONMI->second.getNode();
        ii->second.setTo(ONMIN, ii->second.getOffset()+ONMI->second.getOffset());
      }
    }
}

namespace {
  // HackedGraphSCCFinder - This is used to find nodes that have a path from the
  // node to a node cloned by the ReachabilityCloner object contained.  To be
  // extra obnoxious it ignores edges from nodes that are globals, and truncates
  // search at RC marked nodes.  This is designed as an object so that
  // intermediate results can be memoized across invocations of
  // PathExistsToClonedNode.
  struct HackedGraphSCCFinder {
    ReachabilityCloner &RC;
    unsigned CurNodeId;
    std::vector<const DSNode*> SCCStack;
    std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo;

    HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) {
      // Remove null pointer as a special case.
      NodeInfo[0] = std::make_pair(0, false);
    }

    std::pair<unsigned, bool> &VisitForSCCs(const DSNode *N);

    bool PathExistsToClonedNode(const DSNode *N) {
      return VisitForSCCs(N).second;
    }

    bool PathExistsToClonedNode(const DSCallSite &CS) {
      if (PathExistsToClonedNode(CS.getRetVal().getNode()))
        return true;
      if (CS.isDirectCall() || PathExistsToClonedNode(CS.getCalleeNode()))
        return true;
      for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
        if (PathExistsToClonedNode(CS.getPtrArg(i).getNode()))
          return true;
      return false;
    }
  };
}

std::pair<unsigned, bool> &HackedGraphSCCFinder::
VisitForSCCs(const DSNode *N) {
  std::map<const DSNode*, std::pair<unsigned, bool> >::iterator
    NodeInfoIt = NodeInfo.lower_bound(N);
  if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N)
    return NodeInfoIt->second;

  unsigned Min = CurNodeId++;
  unsigned MyId = Min;
  std::pair<unsigned, bool> &ThisNodeInfo =
    NodeInfo.insert(NodeInfoIt,
                    std::make_pair(N, std::make_pair(MyId, false)))->second;

  // Base case: if we find a global, this doesn't reach the cloned graph
  // portion.
  if (N->isGlobalNode()) {
    ThisNodeInfo.second = false;
    return ThisNodeInfo;
  }

  // Base case: if this does reach the cloned graph portion... it does. :)
  if (RC.hasClonedNode(N)) {
    ThisNodeInfo.second = true;
    return ThisNodeInfo;
  }

  SCCStack.push_back(N);

  // Otherwise, check all successors.
  bool AnyDirectSuccessorsReachClonedNodes = false;
  for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
       EI != EE; ++EI)
    if (DSNode * Succ = EI->second.getNode()) {
      std::pair<unsigned, bool> &SuccInfo = VisitForSCCs(Succ);
      if (SuccInfo.first < Min) Min = SuccInfo.first;
      AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second;
    }

  if (Min != MyId)
    return ThisNodeInfo;  // Part of a large SCC.  Leave self on stack.

  if (SCCStack.back() == N) {  // Special case single node SCC.
    SCCStack.pop_back();
    ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
    return ThisNodeInfo;
  }

  // Find out if any direct successors of any node reach cloned nodes.
  if (!AnyDirectSuccessorsReachClonedNodes)
    for (unsigned i = SCCStack.size() - 1; SCCStack[i] != N; --i)
      for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
           EI != EE; ++EI)
        if (DSNode * N = EI->second.getNode())
          if (NodeInfo[N].second) {
            AnyDirectSuccessorsReachClonedNodes = true;
            goto OutOfLoop;
          }
OutOfLoop:
  // If any successor reaches a cloned node, mark all nodes in this SCC as
  // reaching the cloned node.
  if (AnyDirectSuccessorsReachClonedNodes)
    while (SCCStack.back() != N) {
      NodeInfo[SCCStack.back()].second = true;
      SCCStack.pop_back();
    }
  SCCStack.pop_back();
  ThisNodeInfo.second = true;
  return ThisNodeInfo;
}

/// markReachableNodes - This method recursively traverses the specified
/// DSNodes, marking any nodes which are reachable.  All reachable nodes it adds
/// to the set, which allows it to only traverse visited nodes once.
///
void DSNode::markReachableNodes(DenseSet<const DSNode*> &ReachableNodes) const {
  if (this == 0) return;
  assert(!isForwarding() && "Cannot mark a forwarded node!");
  if (ReachableNodes.insert(this).second) // Is newly reachable?
    for (DSNode::const_edge_iterator I = edge_begin(), E = edge_end();
         I != E; ++I)
      I->second.getNode()->markReachableNodes(ReachableNodes);
}

void DSCallSite::markReachableNodes(DenseSet<const DSNode*> &Nodes) const {
  getRetVal().getNode()->markReachableNodes(Nodes);
  if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);

  for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i)
    getPtrArg(i).getNode()->markReachableNodes(Nodes);
}

// CanReachAliveNodes - Simple graph walker that recursively traverses the graph
// looking for a node that is marked alive.  If an alive node is found, return
// true, otherwise return false.  If an alive node is reachable, this node is
// marked as alive...
//
static bool CanReachAliveNodes(DSNode *N, DenseSet<const DSNode*> &Alive,
                               DenseSet<const DSNode*> &Visited,
                               bool IgnoreGlobals) {
  if (N == 0) return false;
  assert(N->isForwarding() == 0 && "Cannot mark a forwarded node!");

  // If this is a global node, it will end up in the globals graph anyway, so we
  // don't need to worry about it.
  if (IgnoreGlobals && N->isGlobalNode()) return false;

  // If we know that this node is alive, return so!
  if (Alive.count(N)) return true;

  // Otherwise, we don't think the node is alive yet, check for infinite
  // recursion.
  if (Visited.count(N)) return false;  // Found a cycle
  Visited.insert(N);   // No recursion, insert into Visited...

  for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
    if (CanReachAliveNodes(I->second.getNode(), Alive, Visited, IgnoreGlobals)) {
      N->markReachableNodes(Alive);
      return true;
    }
  return false;
}

////////////////////////////////////////////////////////////////////////////////
//Base DataStructures impl:
////////////////////////////////////////////////////////////////////////////////

static const Function *getFnForValue(const Value *V) {
  if (const Instruction *I = dyn_cast<Instruction>(V))
    return I->getParent()->getParent();
  else if (const Argument *A = dyn_cast<Argument>(V))
    return A->getParent();
  else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
    return BB->getParent();
  return 0;
}

/// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
/// These correspond to the interfaces defined in the AliasAnalysis class.
void DataStructures::deleteValue(Value *V) {
  if (const Function *F = getFnForValue(V)) {  // Function local value?
    // If this is a function local value, just delete it from the scalar map!
    getDSGraph(*F)->getScalarMap().eraseIfExists(V);
    return;
  }
  
  if (Function *F = dyn_cast<Function>(V)) {
    assert(getDSGraph(*F)->getReturnNodes().size() == 1 &&
           "cannot handle scc's");
    delete DSInfo[F];
    DSInfo.erase(F);
    return;
  }
  
  assert(!isa<GlobalVariable>(V) && "Do not know how to delete GV's yet!");
}

void DataStructures::copyValue(Value *From, Value *To) {
  if (From == To) return;
  if (const Function *F = getFnForValue(From)) {  // Function local value?
    // If this is a function local value, just delete it from the scalar map!
    getDSGraph(*F)->getScalarMap().copyScalarIfExists(From, To);
    return;
  }
  
  if (Function *FromF = dyn_cast<Function>(From)) {
    Function *ToF = cast<Function>(To);
    assert(!DSInfo.count(ToF) && "New Function already exists!");
    DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs, *TypeSS);
    DSInfo[ToF] = NG;
    assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!");
    
    // Change the Function* is the returnnodes map to the ToF.
    DSNodeHandle Ret = NG->retnodes_begin()->second;
    NG->getReturnNodes().clear();
    NG->getReturnNodes()[ToF] = Ret;
    return;
  }
  
  if (const Function *F = getFnForValue(To)) {
    getDSGraph(*F)->getScalarMap().copyScalarIfExists(From, To);
    return;
  }
  
  errs() << *From;
  errs() << *To;
  assert(0 && "Do not know how to copy this yet!");
  abort();
}

DSGraph* DataStructures::getOrCreateGraph(const Function* F) {
  assert(F && "No function");
  DSGraph *&G = DSInfo[F];
  if (!G) {
    //Clone or Steal the Source Graph
    DSGraph* BaseGraph = GraphSource->getDSGraph(*F);
    if (Clone) {
      G = new DSGraph(BaseGraph, GlobalECs, *TypeSS, DSGraph::DontCloneAuxCallNodes);
    } else {
      G = new DSGraph(GlobalECs, GraphSource->getTargetData(), *TypeSS);
      G->spliceFrom(BaseGraph);
      if (resetAuxCalls) 
        G->getAuxFunctionCalls() = G->getFunctionCalls();
    }
    G->setPrintAuxCalls();
    G->setGlobalsGraph(GlobalsGraph);
    
    // Note that this graph is the graph for ALL of the function in the SCC, not
    // just F.
    for (DSGraph::retnodes_iterator RI = G->retnodes_begin(),
           E = G->retnodes_end(); RI != E; ++RI)
      if (RI->first != F)
        DSInfo[RI->first] = G;
  }
  return G;
}


void DataStructures::formGlobalECs() {
  // Grow the equivalence classes for the globals to include anything that we
  // now know to be aliased.
  sv::set<const GlobalValue*> ECGlobals;
  buildGlobalECs(ECGlobals);
  if (!ECGlobals.empty()) {
    DEBUG(errs() << "Eliminating " << ECGlobals.size() << " EC Globals!\n");
    for (DSInfoTy::iterator I = DSInfo.begin(),
           E = DSInfo.end(); I != E; ++I)
      eliminateUsesOfECGlobals(*I->second, ECGlobals);
  }
}

/// BuildGlobalECs - Look at all of the nodes in the globals graph.  If any node
/// contains multiple globals, DSA will never, ever, be able to tell the globals
/// apart.  Instead of maintaining this information in all of the graphs
/// throughout the entire program, store only a single global (the "leader") in
/// the graphs, and build equivalence classes for the rest of the globals.
void DataStructures::buildGlobalECs(sv::set<const GlobalValue*> &ECGlobals) {
  DSScalarMap &SM = GlobalsGraph->getScalarMap();
  EquivalenceClasses<const GlobalValue*> &GlobalECs = SM.getGlobalECs();
  for (DSGraph::node_iterator I = GlobalsGraph->node_begin(), 
         E = GlobalsGraph->node_end();
       I != E; ++I) {
    if (I->numGlobals() <= 1) continue;

    // First, build up the equivalence set for this block of globals.
    DSNode::globals_iterator i = I->globals_begin(); 
    const GlobalValue *First = *i;
    if (GlobalECs.findValue(*i) != GlobalECs.end())
      First = GlobalECs.getLeaderValue(*i);
    if (*i == First) ++i;
    for( ; i != I->globals_end(); ++i) {
      GlobalECs.unionSets(First, *i);
      ECGlobals.insert(*i);
      if (SM.find(*i) != SM.end())
        SM.erase(SM.find(*i));
      else
        errs() << "Global missing in scalar map " << (*i)->getName() << "\n";
    }

    // Next, get the leader element.
    assert(First == GlobalECs.getLeaderValue(First) &&
           "First did not end up being the leader?");

    // Finally, change the global node to only contain the leader.
    I->clearGlobals();
    I->addGlobal(First);
  }

  DEBUG(GlobalsGraph->AssertGraphOK());
}

/// EliminateUsesOfECGlobals - Once we have determined that some globals are in
/// really just equivalent to some other globals, remove the globals from the
/// specified DSGraph (if present), and merge any nodes with their leader nodes.
void DataStructures::eliminateUsesOfECGlobals(DSGraph &G,
                                              const sv::set<const GlobalValue*> &ECGlobals) {
  DSScalarMap &SM = G.getScalarMap();
  EquivalenceClasses<const GlobalValue*> &GlobalECs = SM.getGlobalECs();

  bool MadeChange = false;
  std::vector<const GlobalValue*> SMGVV(SM.global_begin(), SM.global_end());

  for (std::vector<const GlobalValue*>::iterator GI = SMGVV.begin(),
       E = SMGVV.end(); GI != E; ) {
    const GlobalValue *GV = *GI; ++GI;
    if (!ECGlobals.count(GV)) continue;

    const DSNodeHandle &GVNH = SM[GV];
    assert(!GVNH.isNull() && "Global has null NH!?");

    // Okay, this global is in some equivalence class.  Start by finding the
    // leader of the class.
    const GlobalValue *Leader = GlobalECs.getLeaderValue(GV);

    // If the leader isn't already in the graph, insert it into the node
    // corresponding to GV.
    if (!SM.global_count(Leader)) {
      GVNH.getNode()->addGlobal(Leader);
      SM[Leader] = GVNH;
    } else {
      // Otherwise, the leader is in the graph, make sure the nodes are the
      // merged in the specified graph.
      const DSNodeHandle &LNH = SM[Leader];
      if (LNH.getNode() != GVNH.getNode())
        LNH.mergeWith(GVNH);
    }

    // Next step, remove the global from the DSNode.
    GVNH.getNode()->removeGlobal(GV);

    // Finally, remove the global from the ScalarMap.
    SM.erase(GV);
    MadeChange = true;
  }

  DEBUG(if(MadeChange) G.AssertGraphOK());
}

void DataStructures::init(DataStructures* D, bool clone, bool printAuxCalls, 
                          bool copyGlobalAuxCalls, bool resetAux) {
  assert (!GraphSource && "Already init");
  GraphSource = D;
  Clone = clone;
  resetAuxCalls = resetAux;
  TD = D->TD;
  TypeSS = D->TypeSS;
  callgraph = D->callgraph;
  GlobalECs = D->getGlobalECs();
  GlobalsGraph = new DSGraph(D->getGlobalsGraph(), GlobalECs, *TypeSS,
                             copyGlobalAuxCalls?0:DSGraph::DontCloneAuxCallNodes);
  if (printAuxCalls) GlobalsGraph->setPrintAuxCalls();

  //
  // Tell the other DSA pass if we're stealing its graph.
  //
  if (!clone) D->DSGraphsStolen = true;
}

void DataStructures::init(TargetData* T) {
  assert (!TD && "Already init");
  GraphSource = 0;
  Clone = false;
  TD = T;
  TypeSS = new SuperSet<const Type*>();
  GlobalsGraph = new DSGraph(GlobalECs, *T, *TypeSS);
}

void DataStructures::releaseMemory() {
  //
  // If the DSGraphs were stolen by another pass, free nothing.
  //
  if (DSGraphsStolen) return;

  std::set<DSGraph*> toDelete;
  for (DSInfoTy::iterator I = DSInfo.begin(), E = DSInfo.end(); I != E; ++I) {
    I->second->getReturnNodes().clear();
    toDelete.insert(I->second);
  }
  for (std::set<DSGraph*>::iterator I = toDelete.begin(), E = toDelete.end(); I != E; ++I)
    delete *I;

  // Empty map so next time memory is released, data structures are not
  // re-deleted.
  DSInfo.clear();
  callgraph.clear();
  delete GlobalsGraph;
  GlobalsGraph = 0;
}