lib/Analysis/DataStructure/BottomUpClosure.cpp - fp2-dev/platform/external/llvm - Gitiles

 //===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
 //
 // This file implements the BUDataStructures class, which represents the
 // Bottom-Up Interprocedural closure of the data structure graph over the
 // program.  This is useful for applications like pool allocation, but **not**
 // applications like alias analysis.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/Analysis/DataStructure.h"
 #include "llvm/Analysis/DSGraph.h"
 #include "llvm/Module.h"
 #include "Support/Statistic.h"
 using std::map;

 static RegisterAnalysis<BUDataStructures>
 X("budatastructure", "Bottom-up Data Structure Analysis Closure");

 using namespace DS;

 // run - Calculate the bottom up data structure graphs for each function in the
 // program.
 //
 bool BUDataStructures::run(Module &M) {
   GlobalsGraph = new DSGraph();

   // Simply calculate the graphs for each function...
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
     if (!I->isExternal())
       calculateGraph(*I, 0);
   return false;
 }

 // releaseMemory - If the pass pipeline is done with this pass, we can release
 // our memory... here...
 //
 void BUDataStructures::releaseMemory() {
   for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
          E = DSInfo.end(); I != E; ++I)
     delete I->second;

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


 // Return true if a graph was inlined
 // Can not modify the part of the AuxCallList < FirstResolvableCall.
 //
 bool BUDataStructures::ResolveFunctionCalls(DSGraph &G,
                                             unsigned &FirstResolvableCall,
                                    std::map<Function*, DSCallSite> &InProcess,
                                             unsigned Indent) {
   std::vector<DSCallSite> &FCs = G.getAuxFunctionCalls();
   bool Changed = false;

   // Loop while there are call sites that we can resolve!
   while (FirstResolvableCall != FCs.size()) {
     DSCallSite Call = FCs[FirstResolvableCall];

     // If the function list is incomplete...
     if (Call.getCallee().getNode()->NodeType & DSNode::Incomplete) {
       // If incomplete, we cannot resolve it, so leave it at the beginning of
       // the call list with the other unresolvable calls...
       ++FirstResolvableCall;
     } else {
       // Start inlining all of the functions we can... some may not be
       // inlinable if they are external...
       //
       const std::vector<GlobalValue*> &Callees =
         Call.getCallee().getNode()->getGlobals();

       bool hasExternalTarget = false;

       // Loop over the functions, inlining whatever we can...
       for (unsigned c = 0, e = Callees.size(); c != e; ++c) {
         // Must be a function type, so this cast should succeed unless something
         // really wierd is happening.
         Function &FI = cast<Function>(*Callees[c]);

         if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
             FI.getName() == "fprintf" || FI.getName() == "open" ||
             FI.getName() == "sprintf" || FI.getName() == "fputs") {
           // Ignore
         } else if (FI.isExternal()) {
           // If the function is external, then we cannot resolve this call site!
           hasExternalTarget = true;
           break;
         } else {
           std::map<Function*, DSCallSite>::iterator I =
             InProcess.lower_bound(&FI);

           if (I != InProcess.end() && I->first == &FI) {  // Recursion detected?
             // Merge two call sites to eliminate recursion...
             Call.mergeWith(I->second);

             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "* Recursion detected for function " << FI.getName()<<"\n");
           } else {
             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "Inlining: " << FI.getName() << "\n");

             // Get the data structure graph for the called function, closing it
             // if possible...
             //
             DSGraph &GI = calculateGraph(FI, Indent+1);  // Graph to inline

             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "Got graph for: " << FI.getName() << "["
                   << GI.getGraphSize() << "+"
                   << GI.getAuxFunctionCalls().size() << "] "
                   << " in: " << G.getFunction().getName() << "["
                   << G.getGraphSize() << "+"
                   << G.getAuxFunctionCalls().size() << "]\n");

             // Keep track of how many call sites are added by the inlining...
             unsigned NumCalls = FCs.size();

             // Resolve the arguments and return value
             G.mergeInGraph(Call, GI, DSGraph::StripAllocaBit |
                            DSGraph::DontCloneCallNodes);

             // Added a call site?
             if (FCs.size() != NumCalls) {
               // Otherwise we need to inline the graph.  Temporarily add the
               // current function to the InProcess map to be able to handle
               // recursion successfully.
               //
               I = InProcess.insert(I, std::make_pair(&FI, Call));

               // ResolveFunctionCalls - Resolve the function calls that just got
               // inlined...
               //
               Changed |= ResolveFunctionCalls(G, NumCalls, InProcess, Indent+1);

               // Now that we are done processing the inlined graph, remove our
               // cycle detector record...
               //
               //InProcess.erase(I);
             }
           }
         }
       }

       if (hasExternalTarget) {
         // If we cannot resolve this call site...
         ++FirstResolvableCall;
       } else {
         Changed = true;
         FCs.erase(FCs.begin()+FirstResolvableCall);
       }
     }
   }

   return Changed;
 }

 DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
   // Make sure this graph has not already been calculated, or that we don't get
   // into an infinite loop with mutually recursive functions.
   //
   DSGraph *&GraphPtr = DSInfo[&F];
   if (GraphPtr) return *GraphPtr;

   // Copy the local version into DSInfo...
   GraphPtr = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
   DSGraph &Graph = *GraphPtr;

   Graph.setGlobalsGraph(GlobalsGraph);
   Graph.setPrintAuxCalls();

   // Start resolving calls...
   std::vector<DSCallSite> &FCs = Graph.getAuxFunctionCalls();

   // Start with a copy of the original call sites...
   FCs = Graph.getFunctionCalls();

   DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "[BU] Calculating graph for: " << F.getName() << "\n");

   bool Changed;
   while (1) {
     unsigned FirstResolvableCall = 0;
     std::map<Function *, DSCallSite> InProcess;

     // Insert a call site for self to handle self recursion...
     std::vector<DSNodeHandle> Args;
     Args.reserve(F.asize());
     for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
       if (isPointerType(I->getType()))
         Args.push_back(Graph.getNodeForValue(I));

     InProcess.insert(std::make_pair(&F,
            DSCallSite(*(CallInst*)0, Graph.getRetNode(),(DSNode*)0,Args)));

     Changed = ResolveFunctionCalls(Graph, FirstResolvableCall, InProcess,
                                    Indent);

     if (Changed) {
       Graph.maskIncompleteMarkers();
       Graph.markIncompleteNodes();
       Graph.removeDeadNodes();
       break;
     } else {
       break;
     }
   }

 #if 0
   bool Inlined;
   do {
     Inlined = false;

     for (unsigned i = 0; i != FCs.size(); ++i) {
       // Copy the call, because inlining graphs may invalidate the FCs vector.
       DSCallSite Call = FCs[i];

       // If the function list is complete...
       if ((Call.getCallee().getNode()->NodeType & DSNode::Incomplete)==0) {
         // Start inlining all of the functions we can... some may not be
         // inlinable if they are external...
         //
         std::vector<GlobalValue*> Callees =
           Call.getCallee().getNode()->getGlobals();

         unsigned OldNumCalls = FCs.size();

         // Loop over the functions, inlining whatever we can...
         for (unsigned c = 0; c != Callees.size(); ++c) {
           // Must be a function type, so this cast MUST succeed.
           Function &FI = cast<Function>(*Callees[c]);

           if (&FI == &F) {
             // Self recursion... simply link up the formal arguments with the
             // actual arguments...
             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "[BU] Self Inlining: " << F.getName() << "\n");

             // Handle self recursion by resolving the arguments and return value
             Graph.mergeInGraph(Call, Graph, DSGraph::StripAllocaBit);

             // Erase the entry in the callees vector
             Callees.erase(Callees.begin()+c--);

           } else if (!FI.isExternal()) {
             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "[BU] In " << F.getName() << " inlining: "
                   << FI.getName() << "\n");

             // Get the data structure graph for the called function, closing it
             // if possible (which is only impossible in the case of mutual
             // recursion...
             //
             DSGraph &GI = calculateGraph(FI, Indent+1);  // Graph to inline

             DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "[BU] Got graph for " << FI.getName()
                   << " in: " << F.getName() << "[" << GI.getGraphSize() << "+"
                   << GI.getAuxFunctionCalls().size() << "]\n");

             // Handle self recursion by resolving the arguments and return value
             Graph.mergeInGraph(Call, GI, DSGraph::StripAllocaBit |
                                 DSGraph::DontCloneCallNodes);

             // Erase the entry in the Callees vector
             Callees.erase(Callees.begin()+c--);

           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
                      FI.getName() == "fprintf" || FI.getName() == "open" ||
                      FI.getName() == "sprintf" || FI.getName() == "fputs") {
             // FIXME: These special cases (eg printf) should go away when we can
             // define functions that take a variable number of arguments.

             // FIXME: at the very least, this should update mod/ref info
             // Erase the entry in the globals vector
             Callees.erase(Callees.begin()+c--);
           }
         }

         if (Callees.empty()) {         // Inlined all of the function calls?
           // Erase the call if it is resolvable...
           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
           Inlined = true;
         } else if (Callees.size() !=
                    Call.getCallee().getNode()->getGlobals().size()) {
           // Was able to inline SOME, but not all of the functions.  Construct a
           // new global node here.
           //
           assert(0 && "Unimpl!");
           Inlined = true;
         }


 #if 0
         // If we just inlined a function that had call nodes, chances are that
         // the call nodes are redundant with ones we already have.  Eliminate
         // those call nodes now.
         //
         if (FCs.size() >= OldNumCalls)
           Graph.removeTriviallyDeadNodes();
 #endif
       }

       if (FCs.size() > 200) {
         std::cerr << "Aborted inlining fn: '" << F.getName() << "'!"
                   << std::endl;
         Graph.maskIncompleteMarkers();
         Graph.markIncompleteNodes();
         Graph.removeDeadNodes();
         Graph.writeGraphToFile(std::cerr, "crap."+F.getName());
         exit(1);
         return Graph;
       }

     }

     // Recompute the Incomplete markers.  If there are any function calls left
     // now that are complete, we must loop!
     if (Inlined) {
       Graph.maskIncompleteMarkers();
       Graph.markIncompleteNodes();
       Graph.removeDeadNodes();
     }

   } while (Inlined && !FCs.empty());
 #endif

   DEBUG(std::cerr << std::string(Indent*2, ' ')
         << "[BU] Done inlining: " << F.getName() << " ["
         << Graph.getGraphSize() << "+" << Graph.getAuxFunctionCalls().size()
         << "]\n");

   Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());

   return Graph;
 }
	//===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
	//
	// This file implements the BUDataStructures class, which represents the
	// Bottom-Up Interprocedural closure of the data structure graph over the
	// program. This is useful for applications like pool allocation, but not
	// applications like alias analysis.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/Analysis/DataStructure.h"
	#include "llvm/Analysis/DSGraph.h"
	#include "llvm/Module.h"
	#include "Support/Statistic.h"
	using std::map;

	static RegisterAnalysis<BUDataStructures>
	X("budatastructure", "Bottom-up Data Structure Analysis Closure");

	using namespace DS;

	// run - Calculate the bottom up data structure graphs for each function in the
	// program.
	//
	bool BUDataStructures::run(Module &M) {
	GlobalsGraph = new DSGraph();

	// Simply calculate the graphs for each function...
	for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
	if (!I->isExternal())
	calculateGraph(*I, 0);
	return false;
	}

	// releaseMemory - If the pass pipeline is done with this pass, we can release
	// our memory... here...
	//
	void BUDataStructures::releaseMemory() {
	for (map<const Function, DSGraph>::iterator I = DSInfo.begin(),
	E = DSInfo.end(); I != E; ++I)
	delete I->second;

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


	// Return true if a graph was inlined
	// Can not modify the part of the AuxCallList < FirstResolvableCall.
	//
	bool BUDataStructures::ResolveFunctionCalls(DSGraph &G,
	unsigned &FirstResolvableCall,
	std::map<Function*, DSCallSite> &InProcess,
	unsigned Indent) {
	std::vector<DSCallSite> &FCs = G.getAuxFunctionCalls();
	bool Changed = false;

	// Loop while there are call sites that we can resolve!
	while (FirstResolvableCall != FCs.size()) {
	DSCallSite Call = FCs[FirstResolvableCall];

	// If the function list is incomplete...
	if (Call.getCallee().getNode()->NodeType & DSNode::Incomplete) {
	// If incomplete, we cannot resolve it, so leave it at the beginning of
	// the call list with the other unresolvable calls...
	++FirstResolvableCall;
	} else {
	// Start inlining all of the functions we can... some may not be
	// inlinable if they are external...
	//
	const std::vector<GlobalValue*> &Callees =
	Call.getCallee().getNode()->getGlobals();

	bool hasExternalTarget = false;

	// Loop over the functions, inlining whatever we can...
	for (unsigned c = 0, e = Callees.size(); c != e; ++c) {
	// Must be a function type, so this cast should succeed unless something
	// really wierd is happening.
	Function &FI = cast<Function>(*Callees[c]);

	if (FI.getName() == "printf" \|\| FI.getName() == "sscanf" \|\|
	FI.getName() == "fprintf" \|\| FI.getName() == "open" \|\|
	FI.getName() == "sprintf" \|\| FI.getName() == "fputs") {
	// Ignore
	} else if (FI.isExternal()) {
	// If the function is external, then we cannot resolve this call site!
	hasExternalTarget = true;
	break;
	} else {
	std::map<Function*, DSCallSite>::iterator I =
	InProcess.lower_bound(&FI);

	if (I != InProcess.end() && I->first == &FI) { // Recursion detected?
	// Merge two call sites to eliminate recursion...
	Call.mergeWith(I->second);

	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "* Recursion detected for function " << FI.getName()<<"\n");
	} else {
	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "Inlining: " << FI.getName() << "\n");

	// Get the data structure graph for the called function, closing it
	// if possible...
	//
	DSGraph &GI = calculateGraph(FI, Indent+1); // Graph to inline

	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "Got graph for: " << FI.getName() << "["
	<< GI.getGraphSize() << "+"
	<< GI.getAuxFunctionCalls().size() << "] "
	<< " in: " << G.getFunction().getName() << "["
	<< G.getGraphSize() << "+"
	<< G.getAuxFunctionCalls().size() << "]\n");

	// Keep track of how many call sites are added by the inlining...
	unsigned NumCalls = FCs.size();

	// Resolve the arguments and return value
	G.mergeInGraph(Call, GI, DSGraph::StripAllocaBit \|
	DSGraph::DontCloneCallNodes);

	// Added a call site?
	if (FCs.size() != NumCalls) {
	// Otherwise we need to inline the graph. Temporarily add the
	// current function to the InProcess map to be able to handle
	// recursion successfully.
	//
	I = InProcess.insert(I, std::make_pair(&FI, Call));

	// ResolveFunctionCalls - Resolve the function calls that just got
	// inlined...
	//
	Changed \|= ResolveFunctionCalls(G, NumCalls, InProcess, Indent+1);

	// Now that we are done processing the inlined graph, remove our
	// cycle detector record...
	//
	//InProcess.erase(I);
	}
	}
	}
	}

	if (hasExternalTarget) {
	// If we cannot resolve this call site...
	++FirstResolvableCall;
	} else {
	Changed = true;
	FCs.erase(FCs.begin()+FirstResolvableCall);
	}
	}
	}

	return Changed;
	}

	DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
	// Make sure this graph has not already been calculated, or that we don't get
	// into an infinite loop with mutually recursive functions.
	//
	DSGraph *&GraphPtr = DSInfo[&F];
	if (GraphPtr) return *GraphPtr;

	// Copy the local version into DSInfo...
	GraphPtr = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
	DSGraph &Graph = *GraphPtr;

	Graph.setGlobalsGraph(GlobalsGraph);
	Graph.setPrintAuxCalls();

	// Start resolving calls...
	std::vector<DSCallSite> &FCs = Graph.getAuxFunctionCalls();

	// Start with a copy of the original call sites...
	FCs = Graph.getFunctionCalls();

	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "[BU] Calculating graph for: " << F.getName() << "\n");

	bool Changed;
	while (1) {
	unsigned FirstResolvableCall = 0;
	std::map<Function *, DSCallSite> InProcess;

	// Insert a call site for self to handle self recursion...
	std::vector<DSNodeHandle> Args;
	Args.reserve(F.asize());
	for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
	if (isPointerType(I->getType()))
	Args.push_back(Graph.getNodeForValue(I));

	InProcess.insert(std::make_pair(&F,
	DSCallSite((CallInst)0, Graph.getRetNode(),(DSNode*)0,Args)));

	Changed = ResolveFunctionCalls(Graph, FirstResolvableCall, InProcess,
	Indent);

	if (Changed) {
	Graph.maskIncompleteMarkers();
	Graph.markIncompleteNodes();
	Graph.removeDeadNodes();
	break;
	} else {
	break;
	}
	}

	#if 0
	bool Inlined;
	do {
	Inlined = false;

	for (unsigned i = 0; i != FCs.size(); ++i) {
	// Copy the call, because inlining graphs may invalidate the FCs vector.
	DSCallSite Call = FCs[i];

	// If the function list is complete...
	if ((Call.getCallee().getNode()->NodeType & DSNode::Incomplete)==0) {
	// Start inlining all of the functions we can... some may not be
	// inlinable if they are external...
	//
	std::vector<GlobalValue*> Callees =
	Call.getCallee().getNode()->getGlobals();

	unsigned OldNumCalls = FCs.size();

	// Loop over the functions, inlining whatever we can...
	for (unsigned c = 0; c != Callees.size(); ++c) {
	// Must be a function type, so this cast MUST succeed.
	Function &FI = cast<Function>(*Callees[c]);

	if (&FI == &F) {
	// Self recursion... simply link up the formal arguments with the
	// actual arguments...
	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "[BU] Self Inlining: " << F.getName() << "\n");

	// Handle self recursion by resolving the arguments and return value
	Graph.mergeInGraph(Call, Graph, DSGraph::StripAllocaBit);

	// Erase the entry in the callees vector
	Callees.erase(Callees.begin()+c--);

	} else if (!FI.isExternal()) {
	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "[BU] In " << F.getName() << " inlining: "
	<< FI.getName() << "\n");

	// Get the data structure graph for the called function, closing it
	// if possible (which is only impossible in the case of mutual
	// recursion...
	//
	DSGraph &GI = calculateGraph(FI, Indent+1); // Graph to inline

	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "[BU] Got graph for " << FI.getName()
	<< " in: " << F.getName() << "[" << GI.getGraphSize() << "+"
	<< GI.getAuxFunctionCalls().size() << "]\n");

	// Handle self recursion by resolving the arguments and return value
	Graph.mergeInGraph(Call, GI, DSGraph::StripAllocaBit \|
	DSGraph::DontCloneCallNodes);

	// Erase the entry in the Callees vector
	Callees.erase(Callees.begin()+c--);

	} else if (FI.getName() == "printf" \|\| FI.getName() == "sscanf" \|\|
	FI.getName() == "fprintf" \|\| FI.getName() == "open" \|\|
	FI.getName() == "sprintf" \|\| FI.getName() == "fputs") {
	// FIXME: These special cases (eg printf) should go away when we can
	// define functions that take a variable number of arguments.

	// FIXME: at the very least, this should update mod/ref info
	// Erase the entry in the globals vector
	Callees.erase(Callees.begin()+c--);
	}
	}

	if (Callees.empty()) { // Inlined all of the function calls?
	// Erase the call if it is resolvable...
	FCs.erase(FCs.begin()+i--); // Don't skip a the next call...
	Inlined = true;
	} else if (Callees.size() !=
	Call.getCallee().getNode()->getGlobals().size()) {
	// Was able to inline SOME, but not all of the functions. Construct a
	// new global node here.
	//
	assert(0 && "Unimpl!");
	Inlined = true;
	}


	#if 0
	// If we just inlined a function that had call nodes, chances are that
	// the call nodes are redundant with ones we already have. Eliminate
	// those call nodes now.
	//
	if (FCs.size() >= OldNumCalls)
	Graph.removeTriviallyDeadNodes();
	#endif
	}

	if (FCs.size() > 200) {
	std::cerr << "Aborted inlining fn: '" << F.getName() << "'!"
	<< std::endl;
	Graph.maskIncompleteMarkers();
	Graph.markIncompleteNodes();
	Graph.removeDeadNodes();
	Graph.writeGraphToFile(std::cerr, "crap."+F.getName());
	exit(1);
	return Graph;
	}

	}

	// Recompute the Incomplete markers. If there are any function calls left
	// now that are complete, we must loop!
	if (Inlined) {
	Graph.maskIncompleteMarkers();
	Graph.markIncompleteNodes();
	Graph.removeDeadNodes();
	}

	} while (Inlined && !FCs.empty());
	#endif

	DEBUG(std::cerr << std::string(Indent*2, ' ')
	<< "[BU] Done inlining: " << F.getName() << " ["
	<< Graph.getGraphSize() << "+" << Graph.getAuxFunctionCalls().size()
	<< "]\n");

	Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());

	return Graph;
	}