Remove trailing whitespace
[oota-llvm.git] / lib / Analysis / DataStructure / EquivClassGraphs.cpp
index 8e69291cdbc95566f1b1fcfea4baab53218f562d..e9b324aed64c1764f49a41402d20371e620a3dce 100644 (file)
@@ -1,10 +1,10 @@
 //===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
-// 
+//
 //                     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 pass is the same as the complete bottom-up graphs, but
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "ECGraphs"
-#include "llvm/Analysis/DataStructure/EquivClassGraphs.h"
+#include "llvm/Analysis/DataStructure/DataStructure.h"
+#include "llvm/DerivedTypes.h"
 #include "llvm/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Analysis/DataStructure/DSGraph.h"
-#include "llvm/Analysis/DataStructure/DataStructure.h"
 #include "llvm/Support/CallSite.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/SCCIterator.h"
@@ -45,19 +45,17 @@ static void CheckAllGraphs(Module *M, GT &ECGraphs) {
   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
     if (!I->isExternal()) {
       DSGraph &G = ECGraphs.getDSGraph(*I);
+      if (G.retnodes_begin()->first != I)
+        continue;  // Only check a graph once.
 
       DSGraph::NodeMapTy GlobalsGraphNodeMapping;
-      for (DSScalarMap::global_iterator I = G.getScalarMap().global_begin(),
-             E = G.getScalarMap().global_end(); I != E; ++I)
-        DSGraph::computeNodeMapping(G.getNodeForValue(*I),
-                                    GG.getNodeForValue(*I),
-                                    GlobalsGraphNodeMapping);
-    } 
+      G.computeGToGGMapping(GlobalsGraphNodeMapping);
+    }
 }
 #endif
 
 // getSomeCalleeForCallSite - Return any one callee function at a call site.
-// 
+//
 Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
   Function *thisFunc = CS.getCaller();
   assert(thisFunc && "getSomeCalleeForCallSite(): Not a valid call site?");
@@ -73,9 +71,10 @@ Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
 //
 bool EquivClassGraphs::runOnModule(Module &M) {
   CBU = &getAnalysis<CompleteBUDataStructures>();
+  GlobalECs = CBU->getGlobalECs();
   DEBUG(CheckAllGraphs(&M, *CBU));
 
-  GlobalsGraph = new DSGraph(CBU->getGlobalsGraph());
+  GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs);
   GlobalsGraph->setPrintAuxCalls();
 
   ActualCallees = CBU->getActualCallees();
@@ -95,7 +94,7 @@ bool EquivClassGraphs::runOnModule(Module &M) {
   } else {
     std::cerr << "Fold Graphs: No 'main' function found!\n";
   }
-  
+
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
     if (!I->isExternal())
       processSCC(getOrCreateGraph(*I), Stack, NextID, ValMap);
@@ -103,14 +102,15 @@ bool EquivClassGraphs::runOnModule(Module &M) {
   DEBUG(CheckAllGraphs(&M, *this));
 
   getGlobalsGraph().removeTriviallyDeadNodes();
+  getGlobalsGraph().markIncompleteNodes(DSGraph::IgnoreGlobals);
 
   // Merge the globals variables (not the calls) from the globals graph back
   // into the main function's graph so that the main function contains all of
   // the information about global pools and GV usage in the program.
-  if (MainFunc) {
+  if (MainFunc && !MainFunc->isExternal()) {
     DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
     const DSGraph &GG = *MainGraph.getGlobalsGraph();
-    ReachabilityCloner RC(MainGraph, GG, 
+    ReachabilityCloner RC(MainGraph, GG,
                           DSGraph::DontCloneCallNodes |
                           DSGraph::DontCloneAuxCallNodes);
 
@@ -121,10 +121,33 @@ bool EquivClassGraphs::runOnModule(Module &M) {
         RC.getClonedNH(GG.getNodeForValue(*I));
 
     MainGraph.maskIncompleteMarkers();
-    MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | 
+    MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
                                   DSGraph::IgnoreGlobals);
   }
 
+  // Final processing.  Note that dead node elimination may actually remove
+  // globals from a function graph that are immediately used.  If there are no
+  // scalars pointing to the node (e.g. because the only use is a direct store
+  // to a scalar global) we have to make sure to rematerialize the globals back
+  // into the graphs here, or clients will break!
+  for (Module::global_iterator GI = M.global_begin(), E = M.global_end();
+       GI != E; ++GI)
+    // This only happens to first class typed globals.
+    if (GI->getType()->getElementType()->isFirstClassType())
+      for (Value::use_iterator UI = GI->use_begin(), E = GI->use_end();
+           UI != E; ++UI)
+        // This only happens to direct uses by instructions.
+        if (Instruction *User = dyn_cast<Instruction>(*UI)) {
+          DSGraph &DSG = getOrCreateGraph(*User->getParent()->getParent());
+          if (!DSG.getScalarMap().count(GI)) {
+            // If this global does not exist in the graph, but it is immediately
+            // used by an instruction in the graph, clone it over from the
+            // globals graph.
+            ReachabilityCloner RC(DSG, *GlobalsGraph, 0);
+            RC.getClonedNH(GlobalsGraph->getNodeForValue(GI));
+          }
+        }
+
   return false;
 }
 
@@ -135,7 +158,7 @@ bool EquivClassGraphs::runOnModule(Module &M) {
 //
 void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
   const ActualCalleesTy& AC = CBU->getActualCallees();
-  
+
   // Loop over all of the indirect calls in the program.  If a call site can
   // call multiple different functions, we need to unify all of the callees into
   // the same equivalence class.
@@ -148,7 +171,7 @@ void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
     CallSite CS = CallSite::get(I->first);
 
     if (CS.getCalledFunction()) {       // Direct call:
-      FuncECs.addElement(I->second);    // -- Make sure function has equiv class
+      FuncECs.insert(I->second);        // -- Make sure function has equiv class
       FirstFunc = I->second;            // -- First callee at this site
     } else {                            // Else indirect call
       // DEBUG(std::cerr << "CALLEE: " << I->second->getName()
@@ -163,11 +186,11 @@ void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
        DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
         OneCalledFunction[calleeNode] = FirstFunc;
-        FuncECs.addElement(I->second);
+        FuncECs.insert(I->second);
       } else {
         // This is not the first possible callee from a particular call site.
         // Union the callee in with the other functions.
-        FuncECs.unionSetsWith(FirstFunc, I->second);
+        FuncECs.unionSets(FirstFunc, I->second);
 #ifndef NDEBUG
        Function *thisFunc = LastInst->getParent()->getParent();
         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
@@ -181,92 +204,89 @@ void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
     // equivalence class.  More precisely, if F is in the class, and G(F) is
     // its graph, then we include all other functions that are also in G(F).
     // Currently, that is just the functions in the same call-graph-SCC as F.
-    // 
+    //
     DSGraph& funcDSGraph = CBU->getDSGraph(*I->second);
-    const DSGraph::ReturnNodesTy &RetNodes = funcDSGraph.getReturnNodes();
-    for (DSGraph::ReturnNodesTy::const_iterator RI=RetNodes.begin(),
-           RE=RetNodes.end(); RI != RE; ++RI)
-      FuncECs.unionSetsWith(FirstFunc, RI->first);
+    for (DSGraph::retnodes_iterator RI = funcDSGraph.retnodes_begin(),
+           RE = funcDSGraph.retnodes_end(); RI != RE; ++RI)
+      FuncECs.unionSets(FirstFunc, RI->first);
   }
 
   // Now that all of the equivalences have been built, merge the graphs for
   // each equivalence class.
   //
-  std::set<Function*> &leaderSet = FuncECs.getLeaderSet();
   DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n");
-  for (std::set<Function*>::iterator LI = leaderSet.begin(),
-        LE = leaderSet.end(); LI != LE; ++LI) {
+  for (EquivalenceClasses<Function*>::iterator EQSI = FuncECs.begin(), E =
+         FuncECs.end(); EQSI != E; ++EQSI) {
+    if (!EQSI->isLeader()) continue;
+
+    EquivalenceClasses<Function*>::member_iterator SI =
+      FuncECs.member_begin(EQSI);
+    assert(SI != FuncECs.member_end() && "Empty equiv set??");
+    EquivalenceClasses<Function*>::member_iterator SN = SI;
+    ++SN;
+    if (SN == FuncECs.member_end())
+      continue;   // Single function equivalence set, no merging to do.
 
-    Function* LF = *LI;
-    const std::set<Function*>& EqClass = FuncECs.getEqClass(LF);
+    Function* LF = *SI;
 
-    if (EqClass.size() > 1) {
 #ifndef NDEBUG
-      DEBUG(std::cerr <<"  Equivalence set for leader " <<LF->getName()<<" = ");
-      for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
-             EqEnd = EqClass.end(); EqI != EqEnd; ++EqI)
-        DEBUG(std::cerr << " " << (*EqI)->getName() << ",");
-      DEBUG(std::cerr << "\n");
+    DEBUG(std::cerr <<"  Equivalence set for leader " << LF->getName() <<" = ");
+    for (SN = SI; SN != FuncECs.member_end(); ++SN)
+      DEBUG(std::cerr << " " << (*SN)->getName() << "," );
+    DEBUG(std::cerr << "\n");
 #endif
 
-      // This equiv class has multiple functions: merge their graphs.  First,
-      // clone the CBU graph for the leader and make it the common graph for the
-      // equivalence graph.
-      DSGraph &MergedG = getOrCreateGraph(*LF);
-
-      // Record the argument nodes for use in merging later below.
-      std::vector<DSNodeHandle> ArgNodes;  
-
-      for (Function::aiterator AI1 = LF->abegin(); AI1 != LF->aend(); ++AI1)
-        if (DS::isPointerType(AI1->getType()))
-          ArgNodes.push_back(MergedG.getNodeForValue(AI1));
-      
-      // Merge in the graphs of all other functions in this equiv. class.  Note
-      // that two or more functions may have the same graph, and it only needs
-      // to be merged in once.
-      std::set<DSGraph*> GraphsMerged;
-      GraphsMerged.insert(&CBU->getDSGraph(*LF));
-
-      for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
-             E = EqClass.end(); EqI != E; ++EqI) {
-        Function *F = *EqI;
-        DSGraph *&FG = DSInfo[F];
-
-        DSGraph &CBUGraph = CBU->getDSGraph(*F); 
-        if (!GraphsMerged.insert(&CBUGraph).second)
-          continue;
-        
+    // This equiv class has multiple functions: merge their graphs.  First,
+    // clone the CBU graph for the leader and make it the common graph for the
+    // equivalence graph.
+    DSGraph &MergedG = getOrCreateGraph(*LF);
+
+    // Record the argument nodes for use in merging later below.
+    std::vector<DSNodeHandle> ArgNodes;
+
+    for (Function::arg_iterator AI = LF->arg_begin(), E = LF->arg_end();
+         AI != E; ++AI)
+      if (DS::isPointerType(AI->getType()))
+        ArgNodes.push_back(MergedG.getNodeForValue(AI));
+
+    // Merge in the graphs of all other functions in this equiv. class.  Note
+    // that two or more functions may have the same graph, and it only needs
+    // to be merged in once.
+    std::set<DSGraph*> GraphsMerged;
+    GraphsMerged.insert(&CBU->getDSGraph(*LF));
+
+    for (++SI; SI != FuncECs.member_end(); ++SI) {
+      Function *F = *SI;
+      DSGraph *&FG = DSInfo[F];
+
+      DSGraph &CBUGraph = CBU->getDSGraph(*F);
+      if (GraphsMerged.insert(&CBUGraph).second) {
         // Record the "folded" graph for the function.
-        for (DSGraph::ReturnNodesTy::iterator
-               I = CBUGraph.getReturnNodes().begin(),
-               E = CBUGraph.getReturnNodes().end();
-             I != E; ++I) {
+        for (DSGraph::retnodes_iterator I = CBUGraph.retnodes_begin(),
+               E = CBUGraph.retnodes_end(); I != E; ++I) {
           assert(DSInfo[I->first] == 0 && "Graph already exists for Fn!");
           DSInfo[I->first] = &MergedG;
         }
-        
+
         // Clone this member of the equivalence class into MergedG.
-        DSGraph::NodeMapTy NodeMap;    
-
-        MergedG.cloneInto(CBUGraph, MergedG.getScalarMap(),
-                          MergedG.getReturnNodes(), NodeMap, 0);
-
-        // Merge the return nodes of all functions together.
-        MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
-
-        // Merge the function arguments with all argument nodes found so far.
-        // If there are extra function args, add them to the vector of argNodes
-        Function::aiterator AI2 = F->abegin(), AI2end = F->aend();
-        for (unsigned arg=0, numArgs = ArgNodes.size();
-             arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
-          if (DS::isPointerType(AI2->getType()))
-            ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
-
-        for ( ; AI2 != AI2end; ++AI2)
-          if (DS::isPointerType(AI2->getType()))
-            ArgNodes.push_back(MergedG.getNodeForValue(AI2));
-        DEBUG(MergedG.AssertGraphOK());
+        MergedG.cloneInto(CBUGraph);
       }
+
+      // Merge the return nodes of all functions together.
+      MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
+
+      // Merge the function arguments with all argument nodes found so far.
+      // If there are extra function args, add them to the vector of argNodes
+      Function::arg_iterator AI2 = F->arg_begin(), AI2end = F->arg_end();
+      for (unsigned arg = 0, numArgs = ArgNodes.size();
+           arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
+        if (DS::isPointerType(AI2->getType()))
+          ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
+
+      for ( ; AI2 != AI2end; ++AI2)
+        if (DS::isPointerType(AI2->getType()))
+          ArgNodes.push_back(MergedG.getNodeForValue(AI2));
+      DEBUG(MergedG.AssertGraphOK());
     }
   }
   DEBUG(std::cerr << "\n");
@@ -281,13 +301,13 @@ DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) {
   DSGraph &CBUGraph = CBU->getDSGraph(F);
 
   // Copy the CBU graph...
-  Graph = new DSGraph(CBUGraph);           // updates the map via reference
+  Graph = new DSGraph(CBUGraph, GlobalECs);   // updates the map via reference
   Graph->setGlobalsGraph(&getGlobalsGraph());
   Graph->setPrintAuxCalls();
 
   // Make sure to update the DSInfo map for all functions in the graph!
-  for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
-       I != Graph->getReturnNodes().end(); ++I)
+  for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
+       I != Graph->retnodes_end(); ++I)
     if (I->first != &F) {
       DSGraph *&FG = DSInfo[I->first];
       assert(FG == 0 && "Merging function in SCC twice?");
@@ -299,7 +319,7 @@ DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) {
 
 
 unsigned EquivClassGraphs::
-processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID, 
+processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
            std::map<DSGraph*, unsigned> &ValMap) {
   std::map<DSGraph*, unsigned>::iterator It = ValMap.lower_bound(&FG);
   if (It != ValMap.end() && It->first == &FG)
@@ -313,12 +333,13 @@ processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
   Stack.push_back(&FG);
 
   // The edges out of the current node are the call site targets...
-  for (DSGraph::fc_iterator CI = FG.fc_begin(), E = FG.fc_end(); CI != E; ++CI){
+  for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
+       CI != CE; ++CI) {
     Instruction *Call = CI->getCallSite().getInstruction();
 
     // Loop over all of the actually called functions...
-    ActualCalleesTy::const_iterator I, E;
-    for (tie(I, E) = getActualCallees().equal_range(Call); I != E; ++I)
+    for (callee_iterator I = callee_begin(Call), E = callee_end(Call);
+         I != E; ++I)
       if (!I->second->isExternal()) {
         // Process the callee as necessary.
         unsigned M = processSCC(getOrCreateGraph(*I->second),
@@ -339,14 +360,13 @@ processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
 
     // If the SCC found is not the same as those found in CBU, make sure to
     // merge the graphs as appropriate.
-    DSGraph::NodeMapTy NodeMap;
-    FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
+    FG.cloneInto(*NG);
 
     // Update the DSInfo map and delete the old graph...
-    for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
-         I != NG->getReturnNodes().end(); ++I)
+    for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
+         I != NG->retnodes_end(); ++I)
       DSInfo[I->first] = &FG;
-    
+
     // Remove NG from the ValMap since the pointer may get recycled.
     ValMap.erase(NG);
     delete NG;
@@ -377,21 +397,23 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
   // Else we need to inline some callee graph.  Visit all call sites.
   // The edges out of the current node are the call site targets...
   unsigned i = 0;
-  for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E;
+  for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
        ++CI, ++i) {
     const DSCallSite &CS = *CI;
     Instruction *TheCall = CS.getCallSite().getInstruction();
 
     assert(calls.insert(TheCall).second &&
            "Call instruction occurs multiple times in graph??");
-    
+
+    if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
+      continue;
+
     // Inline the common callee graph into the current graph, if the callee
     // graph has not changed.  Note that all callees should have the same
     // graph so we only need to do this once.
-    // 
+    //
     DSGraph* CalleeGraph = NULL;
-    ActualCalleesTy::const_iterator I, E;
-    tie(I, E) = getActualCallees().equal_range(TheCall);
+    callee_iterator I = callee_begin(TheCall), E = callee_end(TheCall);
     unsigned TNum, Num;
 
     // Loop over all potential callees to find the first non-external callee.
@@ -402,17 +424,17 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
     // Now check if the graph has changed and if so, clone and inline it.
     if (I != E) {
       Function *CalleeFunc = I->second;
-      
+
       // Merge the callee's graph into this graph, if not already the same.
       // Callees in the same equivalence class (which subsumes those
       // in the same SCCs) have the same graph.  Note that all recursion
       // including self-recursion have been folded in the equiv classes.
-      // 
+      //
       CalleeGraph = &getOrCreateGraph(*CalleeFunc);
       if (CalleeGraph != &G) {
         ++NumFoldGraphInlines;
         G.mergeInGraph(CS, *CalleeFunc, *CalleeGraph,
-                       DSGraph::KeepModRefBits | DSGraph::StripAllocaBit |
+                       DSGraph::StripAllocaBit |
                        DSGraph::DontCloneCallNodes |
                        DSGraph::DontCloneAuxCallNodes);
         DEBUG(std::cerr << "    Inlining graph [" << i << "/"
@@ -439,10 +461,9 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
   }
 
   // Recompute the Incomplete markers.
-  assert(G.getInlinedGlobals().empty());
   G.maskIncompleteMarkers();
   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
-  
+
   // Delete dead nodes.  Treat globals that are unreachable but that can
   // reach live nodes as live.
   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
@@ -455,7 +476,7 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
   // globals graph.
   DSScalarMap &MainSM = G.getScalarMap();
   for (DSScalarMap::global_iterator I = MainSM.global_begin(),
-         E = MainSM.global_end(); I != E; ++I) 
+         E = MainSM.global_end(); I != E; ++I)
     RC.getClonedNH(MainSM[*I]);
 
   DEBUG(std::cerr << "  -- DONE ProcessGraph for function "