Remove DSA.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32550 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 0 insertions, 466 deletions

diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp
deleted file mode 100644
index 71bf271a6e..0000000000
--- a/lib/Analysis/DataStructure/TopDownClosure.cpp
+++ /dev/null
@@ -1,466 +0,0 @@
-//===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===//
-//
-//                     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 TDDataStructures class, which represents the
-// Top-down Interprocedural closure of the data structure graph over the
-// program.  This is useful (but not strictly necessary?) for applications
-// like pointer analysis.
-//
-//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "td_dsa"
-#include "llvm/Analysis/DataStructure/DataStructure.h"
-#include "llvm/Module.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Analysis/DataStructure/DSGraph.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Timer.h"
-#include "llvm/ADT/Statistic.h"
-using namespace llvm;
-
-#if 0
-#define TIME_REGION(VARNAME, DESC) \
-   NamedRegionTimer VARNAME(DESC)
-#else
-#define TIME_REGION(VARNAME, DESC)
-#endif
-
-namespace {
-  RegisterPass<TDDataStructures>   // Register the pass
-  Y("tddatastructure", "Top-down Data Structure Analysis");
-
-  Statistic NumTDInlines("tddatastructures", "Number of graphs inlined");
-}
-
-void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N,
-                                                   hash_set<DSNode*> &Visited) {
-  if (!N || Visited.count(N)) return;
-  Visited.insert(N);
-
-  for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) {
-    DSNodeHandle &NH = N->getLink(i*N->getPointerSize());
-    if (DSNode *NN = NH.getNode()) {
-      std::vector<Function*> Functions;
-      NN->addFullFunctionList(Functions);
-      ArgsRemainIncomplete.insert(Functions.begin(), Functions.end());
-      markReachableFunctionsExternallyAccessible(NN, Visited);
-    }
-  }
-}
-
-
-// run - Calculate the top down data structure graphs for each function in the
-// program.
-//
-bool TDDataStructures::runOnModule(Module &M) {
-  BUInfo = &getAnalysis<BUDataStructures>();
-  GlobalECs = BUInfo->getGlobalECs();
-  GlobalsGraph = new DSGraph(BUInfo->getGlobalsGraph(), GlobalECs);
-  GlobalsGraph->setPrintAuxCalls();
-
-  // Figure out which functions must not mark their arguments complete because
-  // they are accessible outside this compilation unit.  Currently, these
-  // arguments are functions which are reachable by global variables in the
-  // globals graph.
-  const DSScalarMap &GGSM = GlobalsGraph->getScalarMap();
-  hash_set<DSNode*> Visited;
-  for (DSScalarMap::global_iterator I=GGSM.global_begin(), E=GGSM.global_end();
-       I != E; ++I) {
-    DSNode *N = GGSM.find(*I)->second.getNode();
-    if (N->isIncomplete())
-      markReachableFunctionsExternallyAccessible(N, Visited);
-  }
-
-  // Loop over unresolved call nodes.  Any functions passed into (but not
-  // returned!) from unresolvable call nodes may be invoked outside of the
-  // current module.
-  for (DSGraph::afc_iterator I = GlobalsGraph->afc_begin(),
-         E = GlobalsGraph->afc_end(); I != E; ++I)
-    for (unsigned arg = 0, e = I->getNumPtrArgs(); arg != e; ++arg)
-      markReachableFunctionsExternallyAccessible(I->getPtrArg(arg).getNode(),
-                                                 Visited);
-  Visited.clear();
-
-  // Functions without internal linkage also have unknown incoming arguments!
-  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-    if (!I->isExternal() && !I->hasInternalLinkage())
-      ArgsRemainIncomplete.insert(I);
-
-  // We want to traverse the call graph in reverse post-order.  To do this, we
-  // calculate a post-order traversal, then reverse it.
-  hash_set<DSGraph*> VisitedGraph;
-  std::vector<DSGraph*> PostOrder;
-
-#if 0
-{TIME_REGION(XXX, "td:Copy graphs");
-
-  // Visit each of the graphs in reverse post-order now!
-  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-    if (!I->isExternal())
-      getOrCreateDSGraph(*I);
-  return false;
-}
-#endif
-
-
-{TIME_REGION(XXX, "td:Compute postorder");
-
-  // Calculate top-down from main...
-  if (Function *F = M.getMainFunction())
-    ComputePostOrder(*F, VisitedGraph, PostOrder);
-
-  // Next calculate the graphs for each unreachable function...
-  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-    ComputePostOrder(*I, VisitedGraph, PostOrder);
-
-  VisitedGraph.clear();   // Release memory!
-}
-
-{TIME_REGION(XXX, "td:Inline stuff");
-
-  // Visit each of the graphs in reverse post-order now!
-  while (!PostOrder.empty()) {
-    InlineCallersIntoGraph(*PostOrder.back());
-    PostOrder.pop_back();
-  }
-}
-
-  // Free the IndCallMap.
-  while (!IndCallMap.empty()) {
-    delete IndCallMap.begin()->second;
-    IndCallMap.erase(IndCallMap.begin());
-  }
-
-
-  ArgsRemainIncomplete.clear();
-  GlobalsGraph->removeTriviallyDeadNodes();
-
-  return false;
-}
-
-
-DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
-  DSGraph *&G = DSInfo[&F];
-  if (G == 0) { // Not created yet?  Clone BU graph...
-    G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs,
-                    DSGraph::DontCloneAuxCallNodes);
-    assert(G->getAuxFunctionCalls().empty() && "Cloned aux calls?");
-    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 TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
-                                        std::vector<DSGraph*> &PostOrder) {
-  if (F.isExternal()) return;
-  DSGraph &G = getOrCreateDSGraph(F);
-  if (Visited.count(&G)) return;
-  Visited.insert(&G);
-
-  // Recursively traverse all of the callee graphs.
-  for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE; ++CI){
-    Instruction *CallI = CI->getCallSite().getInstruction();
-    for (BUDataStructures::callee_iterator I = BUInfo->callee_begin(CallI),
-           E = BUInfo->callee_end(CallI); I != E; ++I)
-      ComputePostOrder(*I->second, Visited, PostOrder);
-  }
-
-  PostOrder.push_back(&G);
-}
-
-
-
-
-
-// releaseMemory - If the pass pipeline is done with this pass, we can release
-// our memory... here...
-//
-// FIXME: This should be releaseMemory and will work fine, except that LoadVN
-// has no way to extend the lifetime of the pass, which screws up ds-aa.
-//
-void TDDataStructures::releaseMyMemory() {
-  for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
-         E = DSInfo.end(); I != E; ++I) {
-    I->second->getReturnNodes().erase(I->first);
-    if (I->second->getReturnNodes().empty())
-      delete I->second;
-  }
-
-  // Empty map so next time memory is released, data structures are not
-  // re-deleted.
-  DSInfo.clear();
-  delete GlobalsGraph;
-  GlobalsGraph = 0;
-}
-
-/// InlineCallersIntoGraph - Inline all of the callers of the specified DS graph
-/// into it, then recompute completeness of nodes in the resultant graph.
-void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
-  // Inline caller graphs into this graph.  First step, get the list of call
-  // sites that call into this graph.
-  std::vector<CallerCallEdge> EdgesFromCaller;
-  std::map<DSGraph*, std::vector<CallerCallEdge> >::iterator
-    CEI = CallerEdges.find(&DSG);
-  if (CEI != CallerEdges.end()) {
-    std::swap(CEI->second, EdgesFromCaller);
-    CallerEdges.erase(CEI);
-  }
-
-  // Sort the caller sites to provide a by-caller-graph ordering.
-  std::sort(EdgesFromCaller.begin(), EdgesFromCaller.end());
-
-
-  // Merge information from the globals graph into this graph.  FIXME: This is
-  // stupid.  Instead of us cloning information from the GG into this graph,
-  // then having RemoveDeadNodes clone it back, we should do all of this as a
-  // post-pass over all of the graphs.  We need to take cloning out of
-  // removeDeadNodes and gut removeDeadNodes at the same time first though. :(
-  {
-    DSGraph &GG = *DSG.getGlobalsGraph();
-    ReachabilityCloner RC(DSG, GG,
-                          DSGraph::DontCloneCallNodes |
-                          DSGraph::DontCloneAuxCallNodes);
-    for (DSScalarMap::global_iterator
-           GI = DSG.getScalarMap().global_begin(),
-           E = DSG.getScalarMap().global_end(); GI != E; ++GI)
-      RC.getClonedNH(GG.getNodeForValue(*GI));
-  }
-
-  DOUT << "[TD] Inlining callers into '" << DSG.getFunctionNames() << "'\n";
-
-  // Iteratively inline caller graphs into this graph.
-  while (!EdgesFromCaller.empty()) {
-    DSGraph &CallerGraph = *EdgesFromCaller.back().CallerGraph;
-
-    // Iterate through all of the call sites of this graph, cloning and merging
-    // any nodes required by the call.
-    ReachabilityCloner RC(DSG, CallerGraph,
-                          DSGraph::DontCloneCallNodes |
-                          DSGraph::DontCloneAuxCallNodes);
-
-    // Inline all call sites from this caller graph.
-    do {
-      const DSCallSite &CS = *EdgesFromCaller.back().CS;
-      Function &CF = *EdgesFromCaller.back().CalledFunction;
-      DOUT << "   [TD] Inlining graph into Fn '" << CF.getName() << "' from ";
-      if (CallerGraph.getReturnNodes().empty())
-        DOUT << "SYNTHESIZED INDIRECT GRAPH";
-      else
-        DOUT << "Fn '" << CS.getCallSite().getInstruction()->
-                            getParent()->getParent()->getName() << "'";
-      DOUT << ": " << CF.getFunctionType()->getNumParams() << " args\n";
-
-      // Get the formal argument and return nodes for the called function and
-      // merge them with the cloned subgraph.
-      DSCallSite T1 = DSG.getCallSiteForArguments(CF);
-      RC.mergeCallSite(T1, CS);
-      ++NumTDInlines;
-
-      EdgesFromCaller.pop_back();
-    } while (!EdgesFromCaller.empty() &&
-             EdgesFromCaller.back().CallerGraph == &CallerGraph);
-  }
-
-
-  // Next, now that this graph is finalized, we need to recompute the
-  // incompleteness markers for this graph and remove unreachable nodes.
-  DSG.maskIncompleteMarkers();
-
-  // If any of the functions has incomplete incoming arguments, don't mark any
-  // of them as complete.
-  bool HasIncompleteArgs = false;
-  for (DSGraph::retnodes_iterator I = DSG.retnodes_begin(),
-         E = DSG.retnodes_end(); I != E; ++I)
-    if (ArgsRemainIncomplete.count(I->first)) {
-      HasIncompleteArgs = true;
-      break;
-    }
-
-  // Recompute the Incomplete markers.  Depends on whether args are complete
-  unsigned Flags
-    = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs;
-  DSG.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
-
-  // Delete dead nodes.  Treat globals that are unreachable as dead also.
-  DSG.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
-
-  // We are done with computing the current TD Graph!  Finally, before we can
-  // finish processing this function, we figure out which functions it calls and
-  // records these call graph edges, so that we have them when we process the
-  // callee graphs.
-  if (DSG.fc_begin() == DSG.fc_end()) return;
-
-  // Loop over all the call sites and all the callees at each call site, and add
-  // edges to the CallerEdges structure for each callee.
-  for (DSGraph::fc_iterator CI = DSG.fc_begin(), E = DSG.fc_end();
-       CI != E; ++CI) {
-
-    // Handle direct calls efficiently.
-    if (CI->isDirectCall()) {
-      if (!CI->getCalleeFunc()->isExternal() &&
-          !DSG.getReturnNodes().count(CI->getCalleeFunc()))
-        CallerEdges[&getDSGraph(*CI->getCalleeFunc())]
-          .push_back(CallerCallEdge(&DSG, &*CI, CI->getCalleeFunc()));
-      continue;
-    }
-
-    Instruction *CallI = CI->getCallSite().getInstruction();
-    // For each function in the invoked function list at this call site...
-    BUDataStructures::callee_iterator IPI =
-      BUInfo->callee_begin(CallI), IPE = BUInfo->callee_end(CallI);
-
-    // Skip over all calls to this graph (SCC calls).
-    while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
-      ++IPI;
-
-    // All SCC calls?
-    if (IPI == IPE) continue;
-
-    Function *FirstCallee = IPI->second;
-    ++IPI;
-
-    // Skip over more SCC calls.
-    while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
-      ++IPI;
-
-    // If there is exactly one callee from this call site, remember the edge in
-    // CallerEdges.
-    if (IPI == IPE) {
-      if (!FirstCallee->isExternal())
-        CallerEdges[&getDSGraph(*FirstCallee)]
-          .push_back(CallerCallEdge(&DSG, &*CI, FirstCallee));
-      continue;
-    }
-
-    // Otherwise, there are multiple callees from this call site, so it must be
-    // an indirect call.  Chances are that there will be other call sites with
-    // this set of targets.  If so, we don't want to do M*N inlining operations,
-    // so we build up a new, private, graph that represents the calls of all
-    // calls to this set of functions.
-    std::vector<Function*> Callees;
-    for (BUDataStructures::ActualCalleesTy::const_iterator I =
-           BUInfo->callee_begin(CallI), E = BUInfo->callee_end(CallI);
-         I != E; ++I)
-      if (!I->second->isExternal())
-        Callees.push_back(I->second);
-    std::sort(Callees.begin(), Callees.end());
-
-    std::map<std::vector<Function*>, DSGraph*>::iterator IndCallRecI =
-      IndCallMap.lower_bound(Callees);
-
-    DSGraph *IndCallGraph;
-
-    // If we already have this graph, recycle it.
-    if (IndCallRecI != IndCallMap.end() && IndCallRecI->first == Callees) {
-      DOUT << "  [TD] *** Reuse of indcall graph for " << Callees.size()
-           << " callees!\n";
-      IndCallGraph = IndCallRecI->second;
-    } else {
-      // Otherwise, create a new DSGraph to represent this.
-      IndCallGraph = new DSGraph(DSG.getGlobalECs(), DSG.getTargetData());
-
-      // Make a nullary dummy call site, which will eventually get some content
-      // merged into it.  The actual callee function doesn't matter here, so we
-      // just pass it something to keep the ctor happy.
-      std::vector<DSNodeHandle> ArgDummyVec;
-      DSCallSite DummyCS(CI->getCallSite(), DSNodeHandle(), Callees[0]/*dummy*/,
-                         ArgDummyVec);
-      IndCallGraph->getFunctionCalls().push_back(DummyCS);
-
-      IndCallRecI = IndCallMap.insert(IndCallRecI,
-                                      std::make_pair(Callees, IndCallGraph));
-
-      // Additionally, make sure that each of the callees inlines this graph
-      // exactly once.
-      DSCallSite *NCS = &IndCallGraph->getFunctionCalls().front();
-      for (unsigned i = 0, e = Callees.size(); i != e; ++i) {
-        DSGraph& CalleeGraph = getDSGraph(*Callees[i]);
-        if (&CalleeGraph != &DSG)
-          CallerEdges[&CalleeGraph].push_back(CallerCallEdge(IndCallGraph, NCS,
-                                                             Callees[i]));
-      }
-    }
-
-    // Now that we know which graph to use for this, merge the caller
-    // information into the graph, based on information from the call site.
-    ReachabilityCloner RC(*IndCallGraph, DSG, 0);
-    RC.mergeCallSite(IndCallGraph->getFunctionCalls().front(), *CI);
-  }
-}
-
-
-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;
-}
-
-void TDDataStructures::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 TDDataStructures::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);
-    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)) {
-    DSGraph &G = getDSGraph(*F);
-    G.getScalarMap().copyScalarIfExists(From, To);
-    return;
-  }
-
-  DOUT << *From;
-  DOUT << *To;
-  assert(0 && "Do not know how to copy this yet!");
-  abort();
-}