//===- 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.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dsa"

#include "dsa/DSGraphTraits.h"
#include "dsa/DataStructure.h"
#include "dsa/DSGraph.h"
#include "dsa/DSSupport.h"
#include "dsa/DSNode.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DataLayout.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 (NumFoldsOOBOffset, "Number of OOB offsets that caused node folding");
  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;
    svset<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(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?");
  for (globals_iterator ii = globals_begin(), ee = globals_end();
       ii != ee; ++ii) {
    assert(ParentGraph->getScalarMap().global_count(*ii));
    assert(ParentGraph->getScalarMap().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 (LinkMapTy::iterator ii = Links.begin(), ee = Links.end();
       ii != ee; ++ii) {
    if (!ii->second.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 = (ii->first + Offset) % ToNH.getNode()->getSize();
      ToNH.getNode()->addEdgeTo(MergeOffset, ii->second);
    }
  }
  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
  //Clear the array flag too. Node should be of type VOID
  TyMap.clear();
  maskNodeTypes(~ArrayNode);

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

void DSNode::addValueList(std::vector<const Value*> &List) const {
  DSScalarMap &SN = getParentGraph()->getScalarMap();
  for(DSScalarMap::const_iterator I = SN.begin(), E = SN.end(); I!= E; I++) {
    if(SN[I->first].getNode() == this){
      //I->first->dump();
    }

  }
}
/// addFullGlobalsSet - 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::addFullGlobalsSet(svset<const GlobalValue*> &Set) 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())
      Set.insert(*I);
    else
      Set.insert(EC.member_begin(ECI), EC.member_end());
  }
}

/// addFullFunctionSet - Identical to addFullGlobalsSet, but only return the
/// functions in the full list.
void DSNode::addFullFunctionSet(svset<const Function*> &Set) 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))
        Set.insert(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))
          Set.insert(F);
    }
  }
}

void DSNode::dumpFuncs() {
  std::vector<const Function *> List;
  addFullFunctionList (List);
  for (unsigned index = 0; index < List.size(); ++index) {
    std::cerr << List[index]->getName().str() << std::endl;
  }
  return;
}

/// markIntPtrFlags - Mark P2 flags on node, if integer and pointer types
/// overlap at any offset.
///
void DSNode::markIntPtrFlags() {
  // check if the types merged have both int and pointer at the same offset,

  const DataLayout &TD = getParentGraph()->getDataLayout();
  // check all offsets for that node.
  for(unsigned offset = 0; offset < getSize() ; offset++) {
    // if that Node has no Type information, skip
    if(TyMap.find(offset) == TyMap.end())
      continue;
    if(!TyMap[offset])
      continue;

    bool pointerTy = false;
    bool integerTy = false;
    unsigned intSize = 0;
    unsigned ptrSize = 0;

    // Iterate through all the Types, at that offset, checking if we have
    // found a pointer type/integer type
    for (svset<Type*>::const_iterator ni = TyMap[offset]->begin(),
         ne = TyMap[offset]->end(); ni != ne; ++ni) {
      if((*ni)->isPointerTy()) {
        PointerType * PT = dyn_cast<PointerType>(*ni);
        pointerTy = true;
        ptrSize = TD.getPointerSize(PT->getAddressSpace());
      }
      if((*ni)->isIntegerTy()) {
        integerTy = true;
        if (TD.getTypeStoreSize(*ni) > intSize)
          intSize = TD.getTypeStoreSize(*ni);
      }
    }
    // If this offset itself contains both pointer and integer, set the
    // flags and exit.
    if(pointerTy && integerTy){
      setUnknownMarker()->setIntToPtrMarker()->setPtrToIntMarker();
      return;
    }
    if(!pointerTy && !integerTy){
      continue;
    }

    // If only either integer or pointer was found, we must see if it 
    // overlaps with any other pointer or integer type at an offset that
    // comes later. 
    unsigned maxOffset = offset + (pointerTy ? ptrSize:intSize);
    unsigned offset2 = offset;
    while(offset2 < maxOffset && offset2 < getSize()) {
      if(TyMap.find(offset2) == TyMap.end()) {
        offset2++;
        continue;
      }
      for (svset<Type*>::const_iterator ni = TyMap[offset2]->begin(),
           ne = TyMap[offset2]->end(); ni != ne; ++ni) {
        if((*ni)->isPointerTy()) {
          pointerTy = true;
        }
        if((*ni)->isIntegerTy()) {
          integerTy = true;
        }
      }
      // whenever we have found overlapping integer and pointer types,
      // we can set the flags, and exit.
      if(pointerTy && integerTy){
        setUnknownMarker()->setIntToPtrMarker()->setPtrToIntMarker();
        return;
      }
      offset2++;
    }
  }
}

/// growSizeForType - This method increases the size of the node 
/// to accomodate NewTy at the given offset. This is useful for
/// updating the size of a DSNode, without actually inferring a 
/// Type.
void DSNode::growSizeForType(Type *NewTy, unsigned Offset) {

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

  if (isCollapsedNode()) return;
  if (isArrayNode() && getSize() > 0) {
    Offset %= getSize();
  }
  const DataLayout &TD = getParentGraph()->getDataLayout();
  if (Offset + TD.getTypeAllocSize(NewTy) >= getSize())
    growSize(Offset + TD.getTypeAllocSize(NewTy));

}

/// 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(Type *NewTy, unsigned Offset) {
  if (!NewTy || NewTy->isVoidTy()) return;
  if (isCollapsedNode()) return;

  growSizeForType(NewTy, Offset);

  // Clang generates loads and stores of struct types.
  // %tmp12 = load %struct.demand* %retval, align 1 

  // In such cases, merge type information for each struct field
  // individually(at the appropriate offset), instead of the 
  // struct type.
  if(NewTy->isStructTy()) {
    const DataLayout &TD = getParentGraph()->getDataLayout();
    StructType *STy = cast<StructType>(NewTy);
    const StructLayout *SL = TD.getStructLayout(cast<StructType>(STy));
    unsigned count = 0;
    for(Type::subtype_iterator ii = STy->element_begin(), ee = STy->element_end(); ii!= ee; ++ii, ++count) {
      unsigned FieldOffset = SL->getElementOffset(count);
      mergeTypeInfo(*ii, Offset + FieldOffset);
    }
  } else {
    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();

  const DataLayout &TD = getParentGraph()->getDataLayout();
  if (!TyMap[Offset]){
    TyMap[Offset] = TyIt;
    for (svset<Type*>::const_iterator ni = TyMap[Offset]->begin(),
         ne = TyMap[Offset]->end(); ni != ne; ++ni) {
      if (Offset + TD.getTypeAllocSize(*ni) >= getSize())
        growSize(Offset + TD.getTypeAllocSize(*ni));
    }
  } else if (TyIt) {
    svset<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());
}

// 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()->isArrayNode())
        NH.getNode()->foldNodeCompletely();
    } else if (CurNodeH.getNode()->isArrayNode()) {
      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);
  }

  // FIXME:Add comments.
  if(NH.getNode()->isArrayNode() && !CurNodeH.getNode()->isArrayNode()) {
    if(NH.getNode()->getSize() != 0 && CurNodeH.getNode()->getSize() != 0) { 
      if((NH.getNode()->getSize() != CurNodeH.getNode()->getSize() &&
          (NH.getOffset() != 0 || CurNodeH.getOffset() != 0) 
          && NH.getNode()->getSize() < CurNodeH.getNode()->getSize())) {
        CurNodeH.getNode()->foldNodeCompletely();
        NH.getNode()->foldNodeCompletely();
        NSize = NH.getNode()->getSize();
        NOffset = NH.getOffset();
      }
    }
  }
  if(!NH.getNode()->isArrayNode() && CurNodeH.getNode()->isArrayNode()) {
    if(NH.getNode()->getSize() != 0 && CurNodeH.getNode()->getSize() != 0) { 
      if((NH.getNode()->getSize() != CurNodeH.getNode()->getSize() &&
          (NH.getOffset() != 0 || CurNodeH.getOffset() != 0) 
          && NH.getNode()->getSize() > CurNodeH.getNode()->getSize())) {
        CurNodeH.getNode()->foldNodeCompletely();
        NH.getNode()->foldNodeCompletely();
        NSize = NH.getNode()->getSize();
        NOffset = NH.getOffset();
      }
    }
  }

  if (CurNodeH.getNode()->isArrayNode() && NH.getNode()->isArrayNode()) {
    if(NH.getNode()->getSize() != 0 && CurNodeH.getNode()->getSize() != 0
       && (NH.getNode()->getSize() != CurNodeH.getNode()->getSize())){
      CurNodeH.getNode()->foldNodeCompletely();
      NH.getNode()->foldNodeCompletely();
      NSize = NH.getNode()->getSize();
      NOffset = NH.getOffset();
    }
  }


  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());

  // Make all of the outgoing links of N now be outgoing links of CurNodeH.
  //
  for (LinkMapTy::iterator ii = N->Links.begin(), ee = N->Links.end();
       ii != ee; ++ii)
    if (ii->second.getNode()) {
      // 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 = CurNodeH.getNode();
      if (CN->Size != 1)
        MergeOffset = (ii->first + NOffset) % CN->getSize();
      CN->addEdgeTo(MergeOffset, ii->second);
    }

  // Now that there are no outgoing edges, all of the Links are dead.
  N->Links.clear();

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

void DSNode::checkOffsetFoldIfNeeded(int Offset) {
  if (!isNodeCompletelyFolded() &&
      (Size != 0 || Offset != 0) &&
      !isForwarding()) {
    if ((Offset >= (int)Size) || Offset < 0) {
      // Accessing offsets out of node size range
      // This is seen in the "magic" struct in named (from bind), where the
      // fourth field is an array of length 0, presumably used to create struct
      // instances of different sizes
      // More generally this happens whenever code indexes past the end
      // of a struct type.  We don't model this, so fold!

      // Collapse the node since its size is now variable
      foldNodeCompletely();

      ++NumFoldsOOBOffset;
    }
  }
}
//===----------------------------------------------------------------------===//
// 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();
    unsigned NewOffset = NH.getOffset() + SrcNH.getOffset();
    if (NHN) {
      NHN->checkOffsetFoldIfNeeded(NewOffset);
      NHN = NH.getNode();
    }
    return DSNodeHandle(NHN, NewOffset);
  }

  // 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();
        unsigned NewOffset = NH.getOffset() + SrcNH.getOffset();
        if (NHN) {
          NHN->checkOffsetFoldIfNeeded(NewOffset);
          NHN = NH.getNode();
        }
        return DSNodeHandle(NHN, NewOffset);
      }
    }
  }

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

  DSNode *DN = new DSNode(*SN, Dest, true /* Null out all links */);
  DN->maskNodeTypes(BitsToKeep);
  NH = DN;

  // 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);

  DSNode* NHN = NH.getNode();
  unsigned NewOffset = NH.getOffset() + SrcNH.getOffset();
  if (NHN) {
    NHN->checkOffsetFoldIfNeeded(NewOffset);
    NHN = NH.getNode();
  }
  return DSNodeHandle(NHN, NewOffset);
}

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->isArrayNode()) {
            DN->foldNodeCompletely();
            DN = NH.getNode();
          }
        } else if (DN->isArrayNode()) {
          DN->foldNodeCompletely();
          DN = NH.getNode();
        }
#endif
      }


      // FIXME:Add comments.
      if(!DN->isArrayNode() && SN->isArrayNode()) {
        if(DN->getSize() != 0 && SN->getSize() != 0) { 
          if((DN->getSize() != SN->getSize() &&
              (NH.getOffset() != 0 || SrcNH.getOffset() != 0) 
              && DN->getSize() > SN->getSize())) {
            DN->foldNodeCompletely();
            DN = NH.getNode();
          }
        }
      }
      if(!SN->isArrayNode() && DN->isArrayNode()) {
        if(DN->getSize() != 0 && SN->getSize() != 0) { 
          if((DN->getSize() != SN->getSize() &&
              (NH.getOffset() != 0 || SrcNH.getOffset() != 0) 
              && DN->getSize() < SN->getSize())) {
            DN->foldNodeCompletely();
            DN = NH.getNode();
          }
        }
      } 

      if (SN->isArrayNode() && DN->isArrayNode()) {
        if((SN->getSize() != DN->getSize()) && (SN->getSize() != 0) 
           && DN->getSize() != 0) {
          DN->foldNodeCompletely();
          DN = NH.getNode();
        }
      }
      if (!DN->isNodeCompletelyFolded() && 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);

#ifndef NDEBUG
    unsigned NHOffset = NH.getOffset();
#endif
    NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset()));

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

    // 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());
  merge(DestCS.getVAVal(), SrcCS.getVAVal());
  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) {
    // If a call site passes more params, ignore the extra params.
    // If the called function is varargs, merge the extra params, with
    // the varargs node.
    if(DestCS.getVAVal() != NULL) {
      merge(DestCS.getVAVal(), SrcCS.getPtrArg(a));
    }
  }

  for (unsigned a = MinArgs, e = DestCS.getNumPtrArgs(); a!=e; ++a) {
    // If a call site passes less explicit params, than the function needs
    // But passes params through a varargs node, merge those in.
    if(SrcCS.getVAVal() != NULL)  {
      merge(DestCS.getPtrArg(a), SrcCS.getVAVal());
    }
  }
}

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()),
                      getClonedNH(SrcCS.getVAVal()),
                      SrcCS.getCalleeFunc(),
                      Args);
  else {
    DSNodeHandle Ret = getClonedNH(SrcCS.getRetVal()),
                 VA = getClonedNH(SrcCS.getVAVal()),
                 Callee = getClonedNH(SrcCS.getCalleeNode());
    // Resolve forwarding now as much as possible.
    Ret.getNode(); VA.getNode();
    // Most importantly, ensure the node passed to DSCallSite
    // is not a forwarding node:
    DSNode * CalleeN = Callee.getNode();
    return DSCallSite(SrcCS.getCallSite(), Ret, VA, CalleeN, 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);
}

/// FunctionTypeOfCallSite - Helper method to extract the signature of a function
/// that is called a given CallSite
///
const FunctionType *DSCallSite::FunctionTypeOfCallSite(const CallSite & Site) {
  Value *Callee = Site.getCalledValue();

  // Direct call, simple
  if (Function *F = dyn_cast<Function>(Callee))
    return F->getFunctionType();

  // Indirect call, extract the type
  const FunctionType *CalleeFuncType = NULL;

  const PointerType *CalleeType = dyn_cast<PointerType>(Callee->getType());
  if (!CalleeType) {
    assert(0 && "Call through a non-pointer type?");
  } else {
    CalleeFuncType = dyn_cast<FunctionType>(CalleeType->getElementType());
    assert(CalleeFuncType &&
           "Call through pointer to non-function?");
  }

  return CalleeFuncType;
}

/// isVarArg - Determines if the call this represents is to a variable argument
/// function
///
bool DSCallSite::isVarArg() const {
  const FunctionType *FT = FunctionTypeOfCallSite(Site);
  return FT->isVarArg();
}

/// isUnresolvable - Determines if this call has properties that would
/// prevent it from ever being resolvded.  Put another way, no amount
/// additional information will make this callsite resolvable.
///
bool DSCallSite::isUnresolvable() const {
  // Direct calls are forever unresolvable if they are calls to declarations.
  if (isDirectCall())
    return getCalleeFunc()->isDeclaration();
  // Indirect calls are forever unresolvable if the call node is marked
  // external.
  // (Nodes can't become non-external through additional information)
  return getCalleeNode()->isExternFuncNode();
}

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

/// 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);
  getVAVal().getNode()->markReachableNodes(Nodes);
  if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);

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

////////////////////////////////////////////////////////////////////////////////
//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.
/// FIXME: Do these update all the datastructures needed?
/// FIXME: What exactly does it mean to tell DSA to 'copy' a value? or delete it? (particularly a function)
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)) {
    DSGraph *G = getDSGraph(*F);
    if (G->getReturnNodes().size() == 1) {
      // If this is function is part of its own SCC, just delete the graph for it
      delete G;
      DSInfo.erase(F);
    } else {
      // SCC case

      // Remove some of the graph's information about this function since it's no longer needed
      G->getReturnNodes().erase(F);
      G->getVANodes().erase(F);

      // Remove entry for the function, but don't delete the graph since others need it
      DSInfo.erase(F);

      // FIXME: Can more be done here? Is there a good way to remove from the SCC's graph more
      // of the information this function contributed?

    }

    return;
  }

  assert(!isa<GlobalVariable>(V) && "Do not know how to delete GV's yet!");

  assert(0 && "Unrecognized value!");
  abort();
}

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 *G = getDSGraph(*FromF);
    if (G->getReturnNodes().size() == 1) {
      // Copy a single function by duplicating its dsgraph

      DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs, *TypeSS);
      DSInfo[ToF] = NG;

      // Change the Function* is the returnnodes map to the ToF.
      DSNodeHandle Ret = NG->retnodes_begin()->second;
      NG->getReturnNodes().clear();
      NG->getReturnNodes()[ToF] = Ret;

      // Change the Function* in the vanodes map to the ToF
      DSNodeHandle VA = NG->vanodes_begin()->second;
      NG->getVANodes().clear();
      NG->getVANodes()[ToF] = VA;
    } else {
      // A copy request on a function that's part of an SCC, we just map the new function to the same information

      // G is the graph for ToF as well (add it to the SCC)
      setDSGraph(*ToF,G);

      // Map ToF to the same return/va nodes as FromF
      G->getReturnNodes()[ToF] = G->getReturnNodes()[FromF];
      G->getVANodes()[ToF] = G->getVANodes()[FromF];
    }

    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) {
    assert (F->isDeclaration() || GraphSource->hasDSGraph(*F));
    //Clone or Steal the Source Graph
    DSGraph* BaseGraph = GraphSource->getDSGraph(*F);
    if (Clone) {
      G = new DSGraph(BaseGraph, GlobalECs, *TypeSS);
      if (resetAuxCalls)
        G->getAuxFunctionCalls() = G->getFunctionCalls();
    } else {
      G = new DSGraph(GlobalECs, GraphSource->getDataLayout(), *TypeSS);
      G->spliceFrom(BaseGraph);
      if (resetAuxCalls)
        G->getAuxFunctionCalls() = G->getFunctionCalls();
    }
    G->setUseAuxCalls();
    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::formGlobalFunctionList() {
  std::vector<const Function*> List;
  DSScalarMap &SN = GlobalsGraph->getScalarMap();
  EquivalenceClasses<const GlobalValue*> &EC = GlobalsGraph->getGlobalECs();
  for (DSScalarMap::global_iterator I = SN.global_begin(), E = SN.global_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), ME = EC.member_end(); MI != ME; ++MI){
        if (const Function *F = dyn_cast<Function>(*MI))
          List.push_back(F);
      }
    }
  }
  GlobalFunctionList.swap(List);
}


void DataStructures::formGlobalECs() {
  // Grow the equivalence classes for the globals to include anything that we
  // now know to be aliased.
  svset<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(svset<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 svset<const GlobalValue*> &ECGlobals) {
  DSScalarMap &SM = G.getScalarMap();
  EquivalenceClasses<const GlobalValue*> &GlobalECs = SM.getGlobalECs();

#ifndef NDEBUG
  bool MadeChange = false;
#endif
  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);
#ifndef NDEBUG
    MadeChange = true;
#endif
  }

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

//For Entry Points
void DataStructures::cloneGlobalsInto(DSGraph* Graph, unsigned cloneFlags) {
  // If this graph contains main, copy the contents of the globals graph over.
  // Note that this is *required* for correctness.  If a callee contains a use
  // of a global, we have to make sure to link up nodes due to global-argument
  // bindings.
  const DSGraph* GG = Graph->getGlobalsGraph();
  ReachabilityCloner RC(Graph, GG, cloneFlags);

  // Clone the global nodes into this graph.
  for (DSScalarMap::global_iterator I = Graph->getScalarMap().global_begin(),
       E = Graph->getScalarMap().global_end(); I != E; ++I)
    RC.getClonedNH(GG->getNodeForValue(*I));
}

//For all graphs
void DataStructures::cloneIntoGlobals(DSGraph* Graph, unsigned cloneFlags) {
  // When this graph is finalized, clone the globals in the graph into the
  // globals graph to make sure it has everything, from all graphs.
  DSScalarMap &MainSM = Graph->getScalarMap();
  ReachabilityCloner RC(GlobalsGraph, Graph, cloneFlags);

  // Clone everything reachable from globals in the function graph into the
  // globals graph.
  for (DSScalarMap::global_iterator I = MainSM.global_begin(),
       E = MainSM.global_end(); I != E; ++I)
    RC.getClonedNH(MainSM[*I]);
}


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

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

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

// CBU has the correct call graph. All the passes that follow it 
// must resotre the call graph, at the end, so that it it correct.
// This is simpler than keeping all the CBU data structures around.
// EQBU and subsequent passes must call this.
void DataStructures::restoreCorrectCallGraph(){
  callgraph = GraphSource->callgraph;
}

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();

  delete GlobalsGraph;
  GlobalsGraph = 0;
}