<commit_before>//===- EliminateNodes.cpp - Prune unneccesary nodes in the graph ----------===//
//
// This file contains two node optimizations:
//   1. UnlinkUndistinguishableNodes - Often, after unification, shadow
//      nodes are left around that should not exist anymore.  An example is when
//      a shadow gets unified with a 'new' node, the following graph gets
//      generated:  %X -> Shadow, %X -> New.  Since all of the edges to the
//      shadow node also all go to the New node, we can eliminate the shadow.
//
//   2. RemoveUnreachableNodes - Remove shadow and allocation nodes that are not
//      reachable from some other node in the graph.  Unreachable nodes are left
//      lying around often because a method only refers to some allocations with
//      scalar values or an alloca, then when it is inlined, these references
//      disappear and the nodes become homeless and prunable.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DataStructureGraph.h"
#include "llvm/Value.h"
#include "Support/STLExtras.h"
#include <algorithm>

//#define DEBUG_NODE_ELIMINATE 1


// isIndistinguishableNode - A node is indistinguishable if some other node
// has exactly the same incoming links to it and if the node considers itself
// to be the same as the other node...
//
static bool isIndistinguishableNode(DSNode *DN) {
  if (DN->getReferrers().empty()) {       // No referrers...
    if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
      return true;  // Node is trivially dead
    else
      return false;
  }
  
  // Pick a random referrer... Ptr is the things that the referrer points to.
  // Since DN is in the Ptr set, look through the set seeing if there are any
  // other nodes that are exactly equilivant to DN (with the exception of node
  // type), but are not DN.  If anything exists, then DN is indistinguishable.
  //

  DSNode *IndFrom = 0;
  const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
    const PointerValSet &Ptr = *Refs[R];

    for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
      DSNode *N2 = Ptr[i].Node;
      if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
          DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {

        IndFrom = N2;
        R = RE-1;
        break;
      }
    }
  }

  // If we haven't found an equivalent node to merge with, see if one of the
  // nodes pointed to by this node is equivalent to this one...
  //
  if (IndFrom == 0) {
    unsigned NumOutgoing = DN->getNumOutgoingLinks();
    for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
      DSNode *Linked = *I;
      if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
          DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
#if 0
        // Make sure the leftover node contains links to everything we do...
        for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
          Linked->getLink(i).add(DN->getLink(i));
#endif

        IndFrom = Linked;
        break;
      }
    }
  }


  // If DN is indistinguishable from some other node, merge them now...
  if (IndFrom == 0)
    return false;     // Otherwise, nothing found, perhaps next time....

  // The nodes can be merged.  Make sure that IndFrom contains all of the
  // outgoing edges (fields) that DN does...
  //
  assert(DN->getNumLinks() == IndFrom->getNumLinks() &&
         "Same type, diff # fields?");
  for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
    IndFrom->getLink(i).add(DN->getLink(i));
  
  // Now make sure that all of the nodes that point to the shadow node also
  // point to the node that we are merging it with...
  //
  for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
    PointerValSet &PVS = *Refs[i];

    bool RanOnce = false;
    for (unsigned j = 0, je = PVS.size(); j != je; ++j)
      if (PVS[j].Node == DN) {
        RanOnce = true;
        PVS.add(PointerVal(IndFrom, PVS[j].Index));
      }

    assert(RanOnce && "Node on user set but cannot find the use!");
  }
  return true;
}

template<typename NodeTy>
static bool removeIndistinguishableNodes(std::vector<NodeTy*> &Nodes) {
  bool Changed = false;
  std::vector<NodeTy*>::iterator I = Nodes.begin();
  while (I != Nodes.end()) {
    if (isIndistinguishableNode(*I)) {
#ifdef DEBUG_NODE_ELIMINATE
      cerr << "Found Indistinguishable Node:\n";
      (*I)->print(cerr);
#endif
      (*I)->removeAllIncomingEdges();
      delete *I;
      I = Nodes.erase(I);
      Changed = true;
    } else {
      ++I;
    }
  }
  return Changed;
}

template<typename NodeTy>
static bool removeIndistinguishableNodePairs(std::vector<NodeTy*> &Nodes) {
  bool Changed = false;
  std::vector<NodeTy*>::iterator I = Nodes.begin();
  while (I != Nodes.end()) {
    NodeTy *N1 = *I++;
    for (std::vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
         I2 != I2E; ++I2) {
      NodeTy *N2 = *I2;
      if (N1->isEquivalentTo(N2)) {
#ifdef DEBUG_NODE_ELIMINATE
        cerr << "Found Indistinguishable Node:\n";
        N1->print(cerr);
#endif
        N1->removeAllIncomingEdges();
        delete N1;
        --I;
        I = Nodes.erase(I);
        Changed = true;
        break;
      }
    }
  }
  return Changed;<commit_msg>Unify the destruction code used for node pairs vs normal nodes.  This was causing a problem before because global values with incoming edges didn't copy the incoming edges to the node they were being merged from, causing the poolalloc pass to die.<commit_after>//===- EliminateNodes.cpp - Prune unneccesary nodes in the graph ----------===//
//
// This file contains two node optimizations:
//   1. UnlinkUndistinguishableNodes - Often, after unification, shadow
//      nodes are left around that should not exist anymore.  An example is when
//      a shadow gets unified with a 'new' node, the following graph gets
//      generated:  %X -> Shadow, %X -> New.  Since all of the edges to the
//      shadow node also all go to the New node, we can eliminate the shadow.
//
//   2. RemoveUnreachableNodes - Remove shadow and allocation nodes that are not
//      reachable from some other node in the graph.  Unreachable nodes are left
//      lying around often because a method only refers to some allocations with
//      scalar values or an alloca, then when it is inlined, these references
//      disappear and the nodes become homeless and prunable.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DataStructureGraph.h"
#include "llvm/Value.h"
#include "Support/STLExtras.h"
#include <algorithm>

//#define DEBUG_NODE_ELIMINATE 1

static void DestroyFirstNodeOfPair(DSNode *N1, DSNode *N2) {
#ifdef DEBUG_NODE_ELIMINATE
  cerr << "Found Indistinguishable Node:\n";
  N1->print(cerr);
#endif

  // The nodes can be merged.  Make sure that N2 contains all of the
  // outgoing edges (fields) that N1 does...
  //
  assert(N1->getNumLinks() == N2->getNumLinks() &&
         "Same type, diff # fields?");
  for (unsigned i = 0, e = N1->getNumLinks(); i != e; ++i)
    N2->getLink(i).add(N1->getLink(i));
  
  // Now make sure that all of the nodes that point to N1 also point to the node
  // that we are merging it with...
  //
  const std::vector<PointerValSet*> &Refs = N1->getReferrers();
  for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
    PointerValSet &PVS = *Refs[i];

    bool RanOnce = false;
    for (unsigned j = 0, je = PVS.size(); j != je; ++j)
      if (PVS[j].Node == N1) {
        RanOnce = true;
        PVS.add(PointerVal(N2, PVS[j].Index));
      }

    assert(RanOnce && "Node on user set but cannot find the use!");
  }

  N1->removeAllIncomingEdges();
  delete N1;
}

// isIndistinguishableNode - A node is indistinguishable if some other node
// has exactly the same incoming links to it and if the node considers itself
// to be the same as the other node...
//
static bool isIndistinguishableNode(DSNode *DN) {
  if (DN->getReferrers().empty()) {       // No referrers...
    if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
      return true;  // Node is trivially dead
    else
      return false;
  }
  
  // Pick a random referrer... Ptr is the things that the referrer points to.
  // Since DN is in the Ptr set, look through the set seeing if there are any
  // other nodes that are exactly equilivant to DN (with the exception of node
  // type), but are not DN.  If anything exists, then DN is indistinguishable.
  //

  DSNode *IndFrom = 0;
  const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
    const PointerValSet &Ptr = *Refs[R];

    for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
      DSNode *N2 = Ptr[i].Node;
      if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
          DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {

        IndFrom = N2;
        R = RE-1;
        break;
      }
    }
  }

  // If we haven't found an equivalent node to merge with, see if one of the
  // nodes pointed to by this node is equivalent to this one...
  //
  if (IndFrom == 0) {
    unsigned NumOutgoing = DN->getNumOutgoingLinks();
    for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
      DSNode *Linked = *I;
      if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
          DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
#if 0
        // Make sure the leftover node contains links to everything we do...
        for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
          Linked->getLink(i).add(DN->getLink(i));
#endif

        IndFrom = Linked;
        break;
      }
    }
  }


  // If DN is indistinguishable from some other node, merge them now...
  if (IndFrom == 0)
    return false;     // Otherwise, nothing found, perhaps next time....

  DestroyFirstNodeOfPair(DN, IndFrom);
  return true;
}

template<typename NodeTy>
static bool removeIndistinguishableNodes(std::vector<NodeTy*> &Nodes) {
  bool Changed = false;
  std::vector<NodeTy*>::iterator I = Nodes.begin();
  while (I != Nodes.end()) {
    if (isIndistinguishableNode(*I)) {
      I = Nodes.erase(I);
      Changed = true;
    } else {
      ++I;
    }
  }
  return Changed;
}

template<typename NodeTy>
static bool removeIndistinguishableNodePairs(std::vector<NodeTy*> &Nodes) {
  bool Changed = false;
  std::vector<NodeTy*>::iterator I = Nodes.begin();
  while (I != Nodes.end()) {
    NodeTy *N1 = *I++;
    for (std::vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
         I2 != I2E; ++I2) {
      NodeTy *N2 = *I2;
      if (N1->isEquivalentTo(N2)) {
        DestroyFirstNodeOfPair(N1, N2);
        --I;
        I = Nodes.erase(I);
        Changed = true;
        break;
      }
    }
  }
  return Changed;
{'fraction_non_alphanumeric': 0.15014242396398053, 'fraction_numerical': 0.007442800698336856, 'mean_word_length': 2.5246113989637307, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 81, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2392812', 'n_tokens_mistral': 3584, 'n_tokens_neox': 3434, 'n_words': 1197}