From 2957f129a7390a068610e9af5a079c6fa1bead24 Mon Sep 17 00:00:00 2001 From: John Criswell Date: Wed, 13 Dec 2006 19:41:57 +0000 Subject: [PATCH] Remove DSA. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32550 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../DataStructure/BottomUpClosure.cpp | 753 ----- lib/Analysis/DataStructure/CallTargets.cpp | 128 - .../DataStructure/CompleteBottomUp.cpp | 239 -- lib/Analysis/DataStructure/DataStructure.cpp | 2435 ----------------- .../DataStructure/DataStructureAA.cpp | 300 -- .../DataStructure/DataStructureOpt.cpp | 102 - .../DataStructure/DataStructureStats.cpp | 150 - .../DataStructure/EquivClassGraphs.cpp | 477 ---- lib/Analysis/DataStructure/GraphChecker.cpp | 204 -- lib/Analysis/DataStructure/Local.cpp | 1333 --------- lib/Analysis/DataStructure/Makefile | 14 - lib/Analysis/DataStructure/Printer.cpp | 356 --- lib/Analysis/DataStructure/Steensgaard.cpp | 278 -- lib/Analysis/DataStructure/TopDownClosure.cpp | 466 ---- 14 files changed, 7235 deletions(-) delete mode 100644 lib/Analysis/DataStructure/BottomUpClosure.cpp delete mode 100644 lib/Analysis/DataStructure/CallTargets.cpp delete mode 100644 lib/Analysis/DataStructure/CompleteBottomUp.cpp delete mode 100644 lib/Analysis/DataStructure/DataStructure.cpp delete mode 100644 lib/Analysis/DataStructure/DataStructureAA.cpp delete mode 100644 lib/Analysis/DataStructure/DataStructureOpt.cpp delete mode 100644 lib/Analysis/DataStructure/DataStructureStats.cpp delete mode 100644 lib/Analysis/DataStructure/EquivClassGraphs.cpp delete mode 100644 lib/Analysis/DataStructure/GraphChecker.cpp delete mode 100644 lib/Analysis/DataStructure/Local.cpp delete mode 100644 lib/Analysis/DataStructure/Makefile delete mode 100644 lib/Analysis/DataStructure/Printer.cpp delete mode 100644 lib/Analysis/DataStructure/Steensgaard.cpp delete mode 100644 lib/Analysis/DataStructure/TopDownClosure.cpp diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp deleted file mode 100644 index e8592b13b67..00000000000 --- a/lib/Analysis/DataStructure/BottomUpClosure.cpp +++ /dev/null @@ -1,753 +0,0 @@ -//===- BottomUpClosure.cpp - Compute bottom-up interprocedural 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 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. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "bu_dsa" -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Module.h" -#include "llvm/DerivedTypes.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Timer.h" -using namespace llvm; - -namespace { - Statistic MaxSCC("budatastructure", "Maximum SCC Size in Call Graph"); - Statistic NumBUInlines("budatastructures", "Number of graphs inlined"); - Statistic NumCallEdges("budatastructures", "Number of 'actual' call edges"); - - cl::opt - AddGlobals("budatastructures-annotate-calls", cl::Hidden, - cl::desc("Annotate call sites with functions as they are resolved")); - cl::opt - UpdateGlobals("budatastructures-update-from-globals", cl::Hidden, - cl::desc("Update local graph from global graph when processing function")); - - RegisterPass - X("budatastructure", "Bottom-up Data Structure Analysis"); -} - -static bool GetAllCalleesN(const DSCallSite &CS, - std::vector &Callees); - -/// 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. -static void BuildGlobalECs(DSGraph &GG, std::set &ECGlobals) { - DSScalarMap &SM = GG.getScalarMap(); - EquivalenceClasses &GlobalECs = SM.getGlobalECs(); - for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); - I != E; ++I) { - if (I->getGlobalsList().size() <= 1) continue; - - // First, build up the equivalence set for this block of globals. - const std::vector &GVs = I->getGlobalsList(); - GlobalValue *First = GVs[0]; - for (unsigned i = 1, e = GVs.size(); i != e; ++i) - GlobalECs.unionSets(First, GVs[i]); - - // Next, get the leader element. - assert(First == GlobalECs.getLeaderValue(First) && - "First did not end up being the leader?"); - - // Next, remove all globals from the scalar map that are not the leader. - assert(GVs[0] == First && "First had to be at the front!"); - for (unsigned i = 1, e = GVs.size(); i != e; ++i) { - ECGlobals.insert(GVs[i]); - SM.erase(SM.find(GVs[i])); - } - - // Finally, change the global node to only contain the leader. - I->clearGlobals(); - I->addGlobal(First); - } - - DEBUG(GG.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. -static void EliminateUsesOfECGlobals(DSGraph &G, - const std::set &ECGlobals) { - DSScalarMap &SM = G.getScalarMap(); - EquivalenceClasses &GlobalECs = SM.getGlobalECs(); - - bool MadeChange = false; - for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); - GI != E; ) { - GlobalValue *GV = *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. - 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); - MadeChange = true; - } - - DEBUG(if(MadeChange) G.AssertGraphOK()); -} - -static void AddGlobalToNode(BUDataStructures* B, DSCallSite D, Function* F) { - if(!AddGlobals) - return; - if(D.isIndirectCall()) { - DSGraph* GI = &B->getDSGraph(D.getCaller()); - DSNodeHandle& NHF = GI->getNodeForValue(F); - DSCallSite DL = GI->getDSCallSiteForCallSite(D.getCallSite()); - if (DL.getCalleeNode() != NHF.getNode() || NHF.isNull()) { - if (NHF.isNull()) { - DSNode *N = new DSNode(F->getType()->getElementType(), GI); // Create the node - N->addGlobal(F); - NHF.setTo(N,0); - DOUT << "Adding " << F->getName() << " to a call node in " - << D.getCaller().getName() << "\n"; - } - DL.getCalleeNode()->mergeWith(NHF, 0); - } - } -} - -// run - Calculate the bottom up data structure graphs for each function in the -// program. -// -bool BUDataStructures::runOnModule(Module &M) { - LocalDataStructures &LocalDSA = getAnalysis(); - GlobalECs = LocalDSA.getGlobalECs(); - - GlobalsGraph = new DSGraph(LocalDSA.getGlobalsGraph(), GlobalECs); - GlobalsGraph->setPrintAuxCalls(); - - IndCallGraphMap = new std::map, - std::pair > >(); - - std::vector Stack; - hash_map ValMap; - unsigned NextID = 1; - - Function *MainFunc = M.getMainFunction(); - if (MainFunc) - calculateGraphs(MainFunc, Stack, NextID, ValMap); - - // Calculate the graphs for any functions that are unreachable from main... - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal() && !DSInfo.count(I)) { - if (MainFunc) - DOUT << "*** BU: Function unreachable from main: " - << I->getName() << "\n"; - calculateGraphs(I, Stack, NextID, ValMap); // Calculate all graphs. - } - - // If we computed any temporary indcallgraphs, free them now. - for (std::map, - std::pair > >::iterator I = - IndCallGraphMap->begin(), E = IndCallGraphMap->end(); I != E; ++I) { - I->second.second.clear(); // Drop arg refs into the graph. - delete I->second.first; - } - delete IndCallGraphMap; - - // At the end of the bottom-up pass, the globals graph becomes complete. - // FIXME: This is not the right way to do this, but it is sorta better than - // nothing! In particular, externally visible globals and unresolvable call - // nodes at the end of the BU phase should make things that they point to - // incomplete in the globals graph. - // - GlobalsGraph->removeTriviallyDeadNodes(); - GlobalsGraph->maskIncompleteMarkers(); - - // Mark external globals incomplete. - GlobalsGraph->markIncompleteNodes(DSGraph::IgnoreGlobals); - - // Grow the equivalence classes for the globals to include anything that we - // now know to be aliased. - std::set ECGlobals; - BuildGlobalECs(*GlobalsGraph, ECGlobals); - if (!ECGlobals.empty()) { - NamedRegionTimer X("Bottom-UP EC Cleanup"); - DOUT << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; - for (hash_map::iterator I = DSInfo.begin(), - E = DSInfo.end(); I != E; ++I) - EliminateUsesOfECGlobals(*I->second, ECGlobals); - } - - // 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 && !MainFunc->isExternal()) { - DSGraph &MainGraph = getOrCreateGraph(MainFunc); - const DSGraph &GG = *MainGraph.getGlobalsGraph(); - ReachabilityCloner RC(MainGraph, GG, - DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - - // Clone the global nodes into this graph. - for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), - E = GG.getScalarMap().global_end(); I != E; ++I) - if (isa(*I)) - RC.getClonedNH(GG.getNodeForValue(*I)); - - MainGraph.maskIncompleteMarkers(); - MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | - DSGraph::IgnoreGlobals); - - //Debug messages if along the way we didn't resolve a call site - //also update the call graph and callsites we did find. - for(DSGraph::afc_iterator ii = MainGraph.afc_begin(), - ee = MainGraph.afc_end(); ii != ee; ++ii) { - std::vector Funcs; - GetAllCalleesN(*ii, Funcs); - DOUT << "Lost site\n"; - DEBUG(ii->getCallSite().getInstruction()->dump()); - for (std::vector::iterator iif = Funcs.begin(), eef = Funcs.end(); - iif != eef; ++iif) { - AddGlobalToNode(this, *ii, *iif); - DOUT << "Adding\n"; - ActualCallees.insert(std::make_pair(ii->getCallSite().getInstruction(), *iif)); - } - } - - } - - NumCallEdges += ActualCallees.size(); - - return false; -} - -DSGraph &BUDataStructures::getOrCreateGraph(Function *F) { - // Has the graph already been created? - DSGraph *&Graph = DSInfo[F]; - if (Graph) return *Graph; - - DSGraph &LocGraph = getAnalysis().getDSGraph(*F); - - // Steal the local graph. - Graph = new DSGraph(GlobalECs, LocGraph.getTargetData()); - Graph->spliceFrom(LocGraph); - - Graph->setGlobalsGraph(GlobalsGraph); - Graph->setPrintAuxCalls(); - - // Start with a copy of the original call sites... - Graph->getAuxFunctionCalls() = Graph->getFunctionCalls(); - return *Graph; -} - -static bool isVAHackFn(const Function *F) { - return F->getName() == "printf" || F->getName() == "sscanf" || - F->getName() == "fprintf" || F->getName() == "open" || - F->getName() == "sprintf" || F->getName() == "fputs" || - F->getName() == "fscanf" || F->getName() == "malloc" || - F->getName() == "free"; -} - -static bool isResolvableFunc(const Function* callee) { - return !callee->isExternal() || isVAHackFn(callee); -} - -static void GetAllCallees(const DSCallSite &CS, - std::vector &Callees) { - if (CS.isDirectCall()) { - if (isResolvableFunc(CS.getCalleeFunc())) - Callees.push_back(CS.getCalleeFunc()); - } else if (!CS.getCalleeNode()->isIncomplete()) { - // Get all callees. - unsigned OldSize = Callees.size(); - CS.getCalleeNode()->addFullFunctionList(Callees); - - // If any of the callees are unresolvable, remove the whole batch! - for (unsigned i = OldSize, e = Callees.size(); i != e; ++i) - if (!isResolvableFunc(Callees[i])) { - Callees.erase(Callees.begin()+OldSize, Callees.end()); - return; - } - } -} - -//returns true if all callees were resolved -static bool GetAllCalleesN(const DSCallSite &CS, - std::vector &Callees) { - if (CS.isDirectCall()) { - if (isResolvableFunc(CS.getCalleeFunc())) { - Callees.push_back(CS.getCalleeFunc()); - return true; - } else - return false; - } else { - // Get all callees. - bool retval = CS.getCalleeNode()->isComplete(); - unsigned OldSize = Callees.size(); - CS.getCalleeNode()->addFullFunctionList(Callees); - - // If any of the callees are unresolvable, remove that one - for (unsigned i = OldSize; i != Callees.size(); ++i) - if (!isResolvableFunc(Callees[i])) { - Callees.erase(Callees.begin()+i); - --i; - retval = false; - } - return retval; - //return false; - } -} - -/// GetAllAuxCallees - Return a list containing all of the resolvable callees in -/// the aux list for the specified graph in the Callees vector. -static void GetAllAuxCallees(DSGraph &G, std::vector &Callees) { - Callees.clear(); - for (DSGraph::afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I) - GetAllCallees(*I, Callees); -} - -unsigned BUDataStructures::calculateGraphs(Function *F, - std::vector &Stack, - unsigned &NextID, - hash_map &ValMap) { - assert(!ValMap.count(F) && "Shouldn't revisit functions!"); - unsigned Min = NextID++, MyID = Min; - ValMap[F] = Min; - Stack.push_back(F); - - // FIXME! This test should be generalized to be any function that we have - // already processed, in the case when there isn't a main or there are - // unreachable functions! - if (F->isExternal()) { // sprintf, fprintf, sscanf, etc... - // No callees! - Stack.pop_back(); - ValMap[F] = ~0; - return Min; - } - - DSGraph &Graph = getOrCreateGraph(F); - if (UpdateGlobals) - Graph.updateFromGlobalGraph(); - - // Find all callee functions. - std::vector CalleeFunctions; - GetAllAuxCallees(Graph, CalleeFunctions); - - // The edges out of the current node are the call site targets... - for (unsigned i = 0, e = CalleeFunctions.size(); i != e; ++i) { - Function *Callee = CalleeFunctions[i]; - unsigned M; - // Have we visited the destination function yet? - hash_map::iterator It = ValMap.find(Callee); - if (It == ValMap.end()) // No, visit it now. - M = calculateGraphs(Callee, Stack, NextID, ValMap); - else // Yes, get it's number. - M = It->second; - if (M < Min) Min = M; - } - - assert(ValMap[F] == MyID && "SCC construction assumption wrong!"); - if (Min != MyID) - return Min; // This is part of a larger SCC! - - // If this is a new SCC, process it now. - if (Stack.back() == F) { // Special case the single "SCC" case here. - DOUT << "Visiting single node SCC #: " << MyID << " fn: " - << F->getName() << "\n"; - Stack.pop_back(); - DSGraph &G = getDSGraph(*F); - DOUT << " [BU] Calculating graph for: " << F->getName()<< "\n"; - calculateGraph(G); - DOUT << " [BU] Done inlining: " << F->getName() << " [" - << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() - << "]\n"; - - if (MaxSCC < 1) MaxSCC = 1; - - // Should we revisit the graph? Only do it if there are now new resolvable - // callees. - GetAllAuxCallees(Graph, CalleeFunctions); - if (!CalleeFunctions.empty()) { - DOUT << "Recalculating " << F->getName() << " due to new knowledge\n"; - ValMap.erase(F); - return calculateGraphs(F, Stack, NextID, ValMap); - } else { - ValMap[F] = ~0U; - } - return MyID; - - } else { - // SCCFunctions - Keep track of the functions in the current SCC - // - std::vector SCCGraphs; - - unsigned SCCSize = 1; - Function *NF = Stack.back(); - ValMap[NF] = ~0U; - DSGraph &SCCGraph = getDSGraph(*NF); - - // First thing first, collapse all of the DSGraphs into a single graph for - // the entire SCC. Splice all of the graphs into one and discard all of the - // old graphs. - // - while (NF != F) { - Stack.pop_back(); - NF = Stack.back(); - ValMap[NF] = ~0U; - - DSGraph &NFG = getDSGraph(*NF); - - // Update the Function -> DSG map. - for (DSGraph::retnodes_iterator I = NFG.retnodes_begin(), - E = NFG.retnodes_end(); I != E; ++I) - DSInfo[I->first] = &SCCGraph; - - SCCGraph.spliceFrom(NFG); - delete &NFG; - - ++SCCSize; - } - Stack.pop_back(); - - DOUT << "Calculating graph for SCC #: " << MyID << " of size: " - << SCCSize << "\n"; - - // Compute the Max SCC Size. - if (MaxSCC < SCCSize) - MaxSCC = SCCSize; - - // Clean up the graph before we start inlining a bunch again... - SCCGraph.removeDeadNodes(DSGraph::KeepUnreachableGlobals); - - // Now that we have one big happy family, resolve all of the call sites in - // the graph... - calculateGraph(SCCGraph); - DOUT << " [BU] Done inlining SCC [" << SCCGraph.getGraphSize() - << "+" << SCCGraph.getAuxFunctionCalls().size() << "]\n" - << "DONE with SCC #: " << MyID << "\n"; - - // We never have to revisit "SCC" processed functions... - return MyID; - } - - return MyID; // == Min -} - - -// releaseMemory - If the pass pipeline is done with this pass, we can release -// our memory... here... -// -void BUDataStructures::releaseMyMemory() { - for (hash_map::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; -} - -DSGraph &BUDataStructures::CreateGraphForExternalFunction(const Function &Fn) { - Function *F = const_cast(&Fn); - DSGraph *DSG = new DSGraph(GlobalECs, GlobalsGraph->getTargetData()); - DSInfo[F] = DSG; - DSG->setGlobalsGraph(GlobalsGraph); - DSG->setPrintAuxCalls(); - - // Add function to the graph. - DSG->getReturnNodes().insert(std::make_pair(F, DSNodeHandle())); - - if (F->getName() == "free") { // Taking the address of free. - - // Free should take a single pointer argument, mark it as heap memory. - DSNode *N = new DSNode(0, DSG); - N->setHeapNodeMarker(); - DSG->getNodeForValue(F->arg_begin()).mergeWith(N); - - } else { - cerr << "Unrecognized external function: " << F->getName() << "\n"; - abort(); - } - - return *DSG; -} - -void BUDataStructures::calculateGraph(DSGraph &Graph) { - // If this graph contains the main function, clone the globals graph into this - // graph before we inline callees and other fun stuff. - bool ContainsMain = false; - DSGraph::ReturnNodesTy &ReturnNodes = Graph.getReturnNodes(); - - for (DSGraph::ReturnNodesTy::iterator I = ReturnNodes.begin(), - E = ReturnNodes.end(); I != E; ++I) - if (I->first->hasExternalLinkage() && I->first->getName() == "main") { - ContainsMain = true; - break; - } - - // 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. - if (ContainsMain) { - const DSGraph &GG = *Graph.getGlobalsGraph(); - ReachabilityCloner RC(Graph, GG, - DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - - // Clone the global nodes into this graph. - for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), - E = GG.getScalarMap().global_end(); I != E; ++I) - if (isa(*I)) - RC.getClonedNH(GG.getNodeForValue(*I)); - } - - - // Move our call site list into TempFCs so that inline call sites go into the - // new call site list and doesn't invalidate our iterators! - std::list TempFCs; - std::list &AuxCallsList = Graph.getAuxFunctionCalls(); - TempFCs.swap(AuxCallsList); - - bool Printed = false; - std::vector CalledFuncs; - while (!TempFCs.empty()) { - DSCallSite &CS = *TempFCs.begin(); - - CalledFuncs.clear(); - - // Fast path for noop calls. Note that we don't care about merging globals - // in the callee with nodes in the caller here. - if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) { - TempFCs.erase(TempFCs.begin()); - continue; - } else if (CS.isDirectCall() && isVAHackFn(CS.getCalleeFunc())) { - TempFCs.erase(TempFCs.begin()); - continue; - } - - GetAllCallees(CS, CalledFuncs); - - if (CalledFuncs.empty()) { - // Remember that we could not resolve this yet! - AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin()); - continue; - } else { - DSGraph *GI; - Instruction *TheCall = CS.getCallSite().getInstruction(); - - if (CalledFuncs.size() == 1) { - Function *Callee = CalledFuncs[0]; - ActualCallees.insert(std::make_pair(TheCall, Callee)); - - // Get the data structure graph for the called function. - GI = &getDSGraph(*Callee); // Graph to inline - DOUT << " Inlining graph for " << Callee->getName() - << "[" << GI->getGraphSize() << "+" - << GI->getAuxFunctionCalls().size() << "] into '" - << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+" - << Graph.getAuxFunctionCalls().size() << "]\n"; - Graph.mergeInGraph(CS, *Callee, *GI, - DSGraph::StripAllocaBit|DSGraph::DontCloneCallNodes); - ++NumBUInlines; - } else { - if (!Printed) - cerr << "In Fns: " << Graph.getFunctionNames() << "\n"; - cerr << " calls " << CalledFuncs.size() - << " fns from site: " << CS.getCallSite().getInstruction() - << " " << *CS.getCallSite().getInstruction(); - cerr << " Fns ="; - unsigned NumPrinted = 0; - - for (std::vector::iterator I = CalledFuncs.begin(), - E = CalledFuncs.end(); I != E; ++I) { - if (NumPrinted++ < 8) cerr << " " << (*I)->getName(); - - // Add the call edges to the call graph. - ActualCallees.insert(std::make_pair(TheCall, *I)); - } - cerr << "\n"; - - // See if we already computed a graph for this set of callees. - std::sort(CalledFuncs.begin(), CalledFuncs.end()); - std::pair > &IndCallGraph = - (*IndCallGraphMap)[CalledFuncs]; - - if (IndCallGraph.first == 0) { - std::vector::iterator I = CalledFuncs.begin(), - E = CalledFuncs.end(); - - // Start with a copy of the first graph. - GI = IndCallGraph.first = new DSGraph(getDSGraph(**I), GlobalECs); - GI->setGlobalsGraph(Graph.getGlobalsGraph()); - std::vector &Args = IndCallGraph.second; - - // Get the argument nodes for the first callee. The return value is - // the 0th index in the vector. - GI->getFunctionArgumentsForCall(*I, Args); - - // Merge all of the other callees into this graph. - for (++I; I != E; ++I) { - // If the graph already contains the nodes for the function, don't - // bother merging it in again. - if (!GI->containsFunction(*I)) { - GI->cloneInto(getDSGraph(**I)); - ++NumBUInlines; - } - - std::vector NextArgs; - GI->getFunctionArgumentsForCall(*I, NextArgs); - unsigned i = 0, e = Args.size(); - for (; i != e; ++i) { - if (i == NextArgs.size()) break; - Args[i].mergeWith(NextArgs[i]); - } - for (e = NextArgs.size(); i != e; ++i) - Args.push_back(NextArgs[i]); - } - - // Clean up the final graph! - GI->removeDeadNodes(DSGraph::KeepUnreachableGlobals); - } else { - cerr << "***\n*** RECYCLED GRAPH ***\n***\n"; - } - - GI = IndCallGraph.first; - - // Merge the unified graph into this graph now. - DOUT << " Inlining multi callee graph " - << "[" << GI->getGraphSize() << "+" - << GI->getAuxFunctionCalls().size() << "] into '" - << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+" - << Graph.getAuxFunctionCalls().size() << "]\n"; - - Graph.mergeInGraph(CS, IndCallGraph.second, *GI, - DSGraph::StripAllocaBit | - DSGraph::DontCloneCallNodes); - ++NumBUInlines; - } - } - TempFCs.erase(TempFCs.begin()); - } - - // Recompute the Incomplete markers - Graph.maskIncompleteMarkers(); - Graph.markIncompleteNodes(DSGraph::MarkFormalArgs); - - // Delete dead nodes. Treat globals that are unreachable but that can - // reach live nodes as live. - Graph.removeDeadNodes(DSGraph::KeepUnreachableGlobals); - - // 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, DSGraph::StripAllocaBit); - - // 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]); - - //Graph.writeGraphToFile(cerr, "bu_" + F.getName()); -} - -static const Function *getFnForValue(const Value *V) { - if (const Instruction *I = dyn_cast(V)) - return I->getParent()->getParent(); - else if (const Argument *A = dyn_cast(V)) - return A->getParent(); - else if (const BasicBlock *BB = dyn_cast(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. -void BUDataStructures::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(V)) { - assert(getDSGraph(*F).getReturnNodes().size() == 1 && - "cannot handle scc's"); - delete DSInfo[F]; - DSInfo.erase(F); - return; - } - - assert(!isa(V) && "Do not know how to delete GV's yet!"); -} - -void BUDataStructures::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(From)) { - Function *ToF = cast(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; - } - - cerr << *From; - cerr << *To; - assert(0 && "Do not know how to copy this yet!"); - abort(); -} diff --git a/lib/Analysis/DataStructure/CallTargets.cpp b/lib/Analysis/DataStructure/CallTargets.cpp deleted file mode 100644 index bae866fd343..00000000000 --- a/lib/Analysis/DataStructure/CallTargets.cpp +++ /dev/null @@ -1,128 +0,0 @@ -//=- lib/Analysis/IPA/CallTargets.cpp - Resolve Call Targets --*- C++ -*-=====// -// -// 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 uses DSA to map targets of all calls, and reports on if it -// thinks it knows all targets of a given call. -// -// Loop over all callsites, and lookup the DSNode for that site. Pull the -// Functions from the node as callees. -// This is essentially a utility pass to simplify later passes that only depend -// on call sites and callees to operate (such as a devirtualizer). -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/CallTargets.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Support/Streams.h" -#include "llvm/Constants.h" -#include -using namespace llvm; - -namespace { - Statistic DirCall("calltarget", "Number of direct calls"); - Statistic IndCall("calltarget", "Number of indirect calls"); - Statistic CompleteInd("calltarget", "Number of complete indirect calls"); - Statistic CompleteEmpty("calltarget", "Number of complete empty calls"); - - RegisterPass X("calltarget","Find Call Targets (uses DSA)"); -} - -void CallTargetFinder::findIndTargets(Module &M) -{ - TDDataStructures* T = &getAnalysis(); - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal()) - for (Function::iterator F = I->begin(), FE = I->end(); F != FE; ++F) - for (BasicBlock::iterator B = F->begin(), BE = F->end(); B != BE; ++B) - if (isa(B) || isa(B)) { - CallSite cs = CallSite::get(B); - AllSites.push_back(cs); - if (!cs.getCalledFunction()) { - IndCall++; - DSNode* N = T->getDSGraph(*cs.getCaller()) - .getNodeForValue(cs.getCalledValue()).getNode(); - N->addFullFunctionList(IndMap[cs]); - if (N->isComplete() && IndMap[cs].size()) { - CompleteSites.insert(cs); - ++CompleteInd; - } - if (N->isComplete() && !IndMap[cs].size()) { - ++CompleteEmpty; - cerr << "Call site empty: '" - << cs.getInstruction()->getName() - << "' In '" - << cs.getInstruction()->getParent()->getParent()->getName() - << "'\n"; - } - } else { - ++DirCall; - IndMap[cs].push_back(cs.getCalledFunction()); - CompleteSites.insert(cs); - } - } -} - -void CallTargetFinder::print(std::ostream &O, const Module *M) const -{ - return; - O << "[* = incomplete] CS: func list\n"; - for (std::map >::const_iterator ii = - IndMap.begin(), - ee = IndMap.end(); ii != ee; ++ii) { - if (!ii->first.getCalledFunction()) { //only print indirect - if (!isComplete(ii->first)) { - O << "* "; - CallSite cs = ii->first; - cs.getInstruction()->dump(); - O << cs.getInstruction()->getParent()->getParent()->getName() << " " - << cs.getInstruction()->getName() << " "; - } - O << ii->first.getInstruction() << ":"; - for (std::vector::const_iterator i = ii->second.begin(), - e = ii->second.end(); i != e; ++i) { - O << " " << (*i)->getName(); - } - O << "\n"; - } - } -} - -bool CallTargetFinder::runOnModule(Module &M) { - findIndTargets(M); - return false; -} - -void CallTargetFinder::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); -} - -std::vector::iterator CallTargetFinder::begin(CallSite cs) { - return IndMap[cs].begin(); -} - -std::vector::iterator CallTargetFinder::end(CallSite cs) { - return IndMap[cs].end(); -} - -bool CallTargetFinder::isComplete(CallSite cs) const { - return CompleteSites.find(cs) != CompleteSites.end(); -} - -std::list::iterator CallTargetFinder::cs_begin() { - return AllSites.begin(); -} - -std::list::iterator CallTargetFinder::cs_end() { - return AllSites.end(); -} diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp deleted file mode 100644 index af33e0d7417..00000000000 --- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp +++ /dev/null @@ -1,239 +0,0 @@ -//===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===// -// -// 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 is the exact same as the bottom-up graphs, but we use take a completed -// call graph and inline all indirect callees into their callers graphs, making -// the result more useful for things like pool allocation. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "cbudatastructure" -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Module.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Support/Debug.h" -#include "llvm/ADT/SCCIterator.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -using namespace llvm; - -namespace { - RegisterPass - X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis"); - Statistic NumCBUInlines("cbudatastructures", "Number of graphs inlined"); -} - - -// run - Calculate the bottom up data structure graphs for each function in the -// program. -// -bool CompleteBUDataStructures::runOnModule(Module &M) { - BUDataStructures &BU = getAnalysis(); - GlobalECs = BU.getGlobalECs(); - GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs); - GlobalsGraph->setPrintAuxCalls(); - - // Our call graph is the same as the BU data structures call graph - ActualCallees = BU.getActualCallees(); - - std::vector Stack; - hash_map ValMap; - unsigned NextID = 1; - - Function *MainFunc = M.getMainFunction(); - if (MainFunc) { - if (!MainFunc->isExternal()) - calculateSCCGraphs(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap); - } else { - DOUT << "CBU-DSA: No 'main' function found!\n"; - } - - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal() && !DSInfo.count(I)) { - if (MainFunc) { - DOUT << "*** CBU: Function unreachable from main: " - << I->getName() << "\n"; - } - calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap); - } - - GlobalsGraph->removeTriviallyDeadNodes(); - - - // 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 && !MainFunc->isExternal()) { - DSGraph &MainGraph = getOrCreateGraph(*MainFunc); - const DSGraph &GG = *MainGraph.getGlobalsGraph(); - ReachabilityCloner RC(MainGraph, GG, - DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - - // Clone the global nodes into this graph. - for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), - E = GG.getScalarMap().global_end(); I != E; ++I) - if (isa(*I)) - RC.getClonedNH(GG.getNodeForValue(*I)); - - MainGraph.maskIncompleteMarkers(); - MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | - DSGraph::IgnoreGlobals); - } - - return false; -} - -DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) { - // Has the graph already been created? - DSGraph *&Graph = DSInfo[&F]; - if (Graph) return *Graph; - - // Copy the BU graph... - Graph = new DSGraph(getAnalysis().getDSGraph(F), GlobalECs); - Graph->setGlobalsGraph(GlobalsGraph); - Graph->setPrintAuxCalls(); - - // Make sure to update the DSInfo map for all of the functions currently in - // this graph! - for (DSGraph::retnodes_iterator I = Graph->retnodes_begin(); - I != Graph->retnodes_end(); ++I) - DSInfo[I->first] = Graph; - - return *Graph; -} - - - -unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG, - std::vector &Stack, - unsigned &NextID, - hash_map &ValMap) { - assert(!ValMap.count(&FG) && "Shouldn't revisit functions!"); - unsigned Min = NextID++, MyID = Min; - ValMap[&FG] = Min; - Stack.push_back(&FG); - - // The edges out of the current node are the call site targets... - 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... - callee_iterator I = callee_begin(Call), E = callee_end(Call); - for (; I != E && I->first == Call; ++I) { - assert(I->first == Call && "Bad callee construction!"); - if (!I->second->isExternal()) { - DSGraph &Callee = getOrCreateGraph(*I->second); - unsigned M; - // Have we visited the destination function yet? - hash_map::iterator It = ValMap.find(&Callee); - if (It == ValMap.end()) // No, visit it now. - M = calculateSCCGraphs(Callee, Stack, NextID, ValMap); - else // Yes, get it's number. - M = It->second; - if (M < Min) Min = M; - } - } - } - - assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); - if (Min != MyID) - return Min; // This is part of a larger SCC! - - // If this is a new SCC, process it now. - bool IsMultiNodeSCC = false; - while (Stack.back() != &FG) { - DSGraph *NG = Stack.back(); - ValMap[NG] = ~0U; - - FG.cloneInto(*NG); - - // Update the DSInfo map and delete the old graph... - 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; - - Stack.pop_back(); - IsMultiNodeSCC = true; - } - - // Clean up the graph before we start inlining a bunch again... - if (IsMultiNodeSCC) - FG.removeTriviallyDeadNodes(); - - Stack.pop_back(); - processGraph(FG); - ValMap[&FG] = ~0U; - return MyID; -} - - -/// processGraph - Process the BU graphs for the program in bottom-up order on -/// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs. -void CompleteBUDataStructures::processGraph(DSGraph &G) { - hash_set calls; - - // The edges out of the current node are the call site targets... - unsigned i = 0; - 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??"); - - // Fast path for noop calls. Note that we don't care about merging globals - // in the callee with nodes in the caller here. - if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) - continue; - - // Loop over all of the potentially called functions... - // Inline direct calls as well as indirect calls because the direct - // callee may have indirect callees and so may have changed. - // - callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall); - unsigned TNum = 0, Num = 0; - DEBUG(Num = std::distance(I, E)); - for (; I != E; ++I, ++TNum) { - assert(I->first == TheCall && "Bad callee construction!"); - Function *CalleeFunc = I->second; - if (!CalleeFunc->isExternal()) { - // Merge the callee's graph into this graph. This works for normal - // calls or for self recursion within an SCC. - DSGraph &GI = getOrCreateGraph(*CalleeFunc); - ++NumCBUInlines; - G.mergeInGraph(CS, *CalleeFunc, GI, - DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - DOUT << " Inlining graph [" << i << "/" - << G.getFunctionCalls().size()-1 - << ":" << TNum << "/" << Num-1 << "] for " - << CalleeFunc->getName() << "[" - << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size() - << "] into '" /*<< G.getFunctionNames()*/ << "' [" - << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() - << "]\n"; - } - } - } - - // Recompute the Incomplete markers - 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); -} diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp deleted file mode 100644 index 666b615825b..00000000000 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ /dev/null @@ -1,2435 +0,0 @@ -//===- 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. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DSGraphTraits.h" -#include "llvm/Constants.h" -#include "llvm/Function.h" -#include "llvm/GlobalVariable.h" -#include "llvm/Instructions.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Assembly/Writer.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 -using namespace llvm; - -#define COLLAPSE_ARRAYS_AGGRESSIVELY 0 - -namespace { - Statistic NumFolds ("dsa", "Number of nodes completely folded"); - Statistic NumCallNodesMerged("dsa", "Number of call nodes merged"); - Statistic NumNodeAllocated ("dsa", "Number of nodes allocated"); - Statistic NumDNE ("dsa", "Number of nodes removed by reachability"); - Statistic NumTrivialDNE ("dsa", "Number of nodes trivially removed"); - Statistic NumTrivialGlobalDNE("dsa", "Number of globals trivially removed"); - static cl::opt - DSAFieldLimit("dsa-field-limit", cl::Hidden, - cl::desc("Number of fields to track before collapsing a node"), - cl::init(256)); -} - -#if 0 -#define TIME_REGION(VARNAME, DESC) \ - NamedRegionTimer VARNAME(DESC) -#else -#define TIME_REGION(VARNAME, DESC) -#endif - -using namespace DS; - -/// 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; - std::set 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->Size <= Offset) { - assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?"); - Offset = 0; - } - return N; -} - -//===----------------------------------------------------------------------===// -// DSScalarMap Implementation -//===----------------------------------------------------------------------===// - -DSNodeHandle &DSScalarMap::AddGlobal(GlobalValue *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::iterator ECI = GlobalECs.findValue(GV); - if (ECI != GlobalECs.end()) { - 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; -} - - -//===----------------------------------------------------------------------===// -// DSNode Implementation -//===----------------------------------------------------------------------===// - -DSNode::DSNode(const Type *T, DSGraph *G) - : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) { - // Add the type entry if it is specified... - if (T) mergeTypeInfo(T, 0); - 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), - Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) { - if (!NullLinks) { - Links = N.Links; - } else - Links.resize(N.Links.size()); // Create the appropriate number of null links - G->addNode(this); - ++NumNodeAllocated; -} - -/// getTargetData - Get the target data object used to construct this node. -/// -const TargetData &DSNode::getTargetData() const { - return ParentGraph->getTargetData(); -} - -void DSNode::assertOK() const { - assert((Ty != Type::VoidTy || - Ty == Type::VoidTy && (Size == 0 || - (NodeType & DSNode::Array))) && - "Node not OK!"); - - assert(ParentGraph && "Node has no parent?"); - const DSScalarMap &SM = ParentGraph->getScalarMap(); - for (unsigned i = 0, e = Globals.size(); i != e; ++i) { - assert(SM.global_count(Globals[i])); - assert(SM.find(Globals[i])->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 = DEAD; - Size = 0; - Ty = Type::VoidTy; - - // 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(GlobalValue *GV) { - // First, check to make sure this is the leader if the global is in an - // equivalence class. - GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV); - - // Keep the list sorted. - std::vector::iterator I = - std::lower_bound(Globals.begin(), Globals.end(), GV); - - if (I == Globals.end() || *I != GV) { - Globals.insert(I, GV); - NodeType |= GlobalNode; - } -} - -// removeGlobal - Remove the specified global that is explicitly in the globals -// list. -void DSNode::removeGlobal(GlobalValue *GV) { - std::vector::iterator I = - std::lower_bound(Globals.begin(), Globals.end(), GV); - assert(I != Globals.end() && *I == GV && "Global not in node!"); - Globals.erase(I); -} - -/// 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... - - ++NumFolds; - - // If this node has a size that is <= 1, we don't need to create a forwarding - // node. - if (getSize() <= 1) { - NodeType |= DSNode::Array; - Ty = Type::VoidTy; - Size = 1; - assert(Links.size() <= 1 && "Size is 1, but has more links?"); - Links.resize(1); - } 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(0, ParentGraph); - DestNode->NodeType = NodeType|DSNode::Array; - DestNode->Ty = Type::VoidTy; - DestNode->Size = 1; - DestNode->Globals.swap(Globals); - - // Start forwarding to the destination node... - forwardNode(DestNode, 0); - - if (!Links.empty()) { - DestNode->Links.reserve(1); - - DSNodeHandle NH(DestNode); - DestNode->Links.push_back(Links[0]); - - // If we have links, merge all of our outgoing links together... - for (unsigned i = Links.size()-1; i != 0; --i) - NH.getNode()->Links[0].mergeWith(Links[i]); - Links.clear(); - } else { - DestNode->Links.resize(1); - } - } -} - -/// 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 getSize() == 1 && Ty == Type::VoidTy && isArray(); -} - -/// addFullGlobalsList - 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::addFullGlobalsList(std::vector &List) const { - if (globals_begin() == globals_end()) return; - - EquivalenceClasses &EC = getParentGraph()->getGlobalECs(); - - for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) { - EquivalenceClasses::iterator ECI = EC.findValue(*I); - if (ECI == EC.end()) - List.push_back(*I); - else - List.insert(List.end(), EC.member_begin(ECI), EC.member_end()); - } -} - -/// addFullFunctionList - Identical to addFullGlobalsList, but only return the -/// functions in the full list. -void DSNode::addFullFunctionList(std::vector &List) const { - if (globals_begin() == globals_end()) return; - - EquivalenceClasses &EC = getParentGraph()->getGlobalECs(); - - for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) { - EquivalenceClasses::iterator ECI = EC.findValue(*I); - if (ECI == EC.end()) { - if (Function *F = dyn_cast(*I)) - List.push_back(F); - } else { - for (EquivalenceClasses::member_iterator MI = - EC.member_begin(ECI), E = EC.member_end(); MI != E; ++MI) - if (Function *F = dyn_cast(*MI)) - List.push_back(F); - } - } -} - -namespace { - /// TypeElementWalker Class - Used for implementation of physical subtyping... - /// - class TypeElementWalker { - struct StackState { - const Type *Ty; - unsigned Offset; - unsigned Idx; - StackState(const Type *T, unsigned Off = 0) - : Ty(T), Offset(Off), Idx(0) {} - }; - - std::vector Stack; - const TargetData &TD; - public: - TypeElementWalker(const Type *T, const TargetData &td) : TD(td) { - Stack.push_back(T); - StepToLeaf(); - } - - bool isDone() const { return Stack.empty(); } - const Type *getCurrentType() const { return Stack.back().Ty; } - unsigned getCurrentOffset() const { return Stack.back().Offset; } - - void StepToNextType() { - PopStackAndAdvance(); - StepToLeaf(); - } - - private: - /// PopStackAndAdvance - Pop the current element off of the stack and - /// advance the underlying element to the next contained member. - void PopStackAndAdvance() { - assert(!Stack.empty() && "Cannot pop an empty stack!"); - Stack.pop_back(); - while (!Stack.empty()) { - StackState &SS = Stack.back(); - if (const StructType *ST = dyn_cast(SS.Ty)) { - ++SS.Idx; - if (SS.Idx != ST->getNumElements()) { - const StructLayout *SL = TD.getStructLayout(ST); - SS.Offset += - unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]); - return; - } - Stack.pop_back(); // At the end of the structure - } else { - const ArrayType *AT = cast(SS.Ty); - ++SS.Idx; - if (SS.Idx != AT->getNumElements()) { - SS.Offset += unsigned(TD.getTypeSize(AT->getElementType())); - return; - } - Stack.pop_back(); // At the end of the array - } - } - } - - /// StepToLeaf - Used by physical subtyping to move to the first leaf node - /// on the type stack. - void StepToLeaf() { - if (Stack.empty()) return; - while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) { - StackState &SS = Stack.back(); - if (const StructType *ST = dyn_cast(SS.Ty)) { - if (ST->getNumElements() == 0) { - assert(SS.Idx == 0); - PopStackAndAdvance(); - } else { - // Step into the structure... - assert(SS.Idx < ST->getNumElements()); - const StructLayout *SL = TD.getStructLayout(ST); - Stack.push_back(StackState(ST->getElementType(SS.Idx), - SS.Offset+unsigned(SL->MemberOffsets[SS.Idx]))); - } - } else { - const ArrayType *AT = cast(SS.Ty); - if (AT->getNumElements() == 0) { - assert(SS.Idx == 0); - PopStackAndAdvance(); - } else { - // Step into the array... - assert(SS.Idx < AT->getNumElements()); - Stack.push_back(StackState(AT->getElementType(), - SS.Offset+SS.Idx* - unsigned(TD.getTypeSize(AT->getElementType())))); - } - } - } - } - }; -} // end anonymous namespace - -/// ElementTypesAreCompatible - Check to see if the specified types are -/// "physically" compatible. If so, return true, else return false. We only -/// have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1 -/// is true, then we also allow a larger T1. -/// -static bool ElementTypesAreCompatible(const Type *T1, const Type *T2, - bool AllowLargerT1, const TargetData &TD){ - TypeElementWalker T1W(T1, TD), T2W(T2, TD); - - while (!T1W.isDone() && !T2W.isDone()) { - if (T1W.getCurrentOffset() != T2W.getCurrentOffset()) - return false; - - const Type *T1 = T1W.getCurrentType(); - const Type *T2 = T2W.getCurrentType(); - if (T1 != T2 && !T1->canLosslesslyBitCastTo(T2)) - return false; - - T1W.StepToNextType(); - T2W.StepToNextType(); - } - - return AllowLargerT1 || T1W.isDone(); -} - - -/// 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. -/// -bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, - bool FoldIfIncompatible) { - DOUT << "merging " << *NewTy << " at " << Offset << " with " << *Ty << "\n"; - const TargetData &TD = getTargetData(); - // Check to make sure the Size member is up-to-date. Size can be one of the - // following: - // Size = 0, Ty = Void: Nothing is known about this node. - // Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero - // Size = 1, Ty = Void, Array = 1: The node is collapsed - // Otherwise, sizeof(Ty) = Size - // - assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) || - (Size == 0 && !Ty->isSized() && !isArray()) || - (Size == 1 && Ty == Type::VoidTy && isArray()) || - (Size == 0 && !Ty->isSized() && !isArray()) || - (TD.getTypeSize(Ty) == Size)) && - "Size member of DSNode doesn't match the type structure!"); - assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!"); - - if (Offset == 0 && NewTy == Ty) - return false; // This should be a common case, handle it efficiently - - // Return true immediately if the node is completely folded. - if (isNodeCompletelyFolded()) return true; - - // If this is an array type, eliminate the outside arrays because they won't - // be used anyway. This greatly reduces the size of large static arrays used - // as global variables, for example. - // - bool WillBeArray = false; - while (const ArrayType *AT = dyn_cast(NewTy)) { - // FIXME: we might want to keep small arrays, but must be careful about - // things like: [2 x [10000 x int*]] - NewTy = AT->getElementType(); - WillBeArray = true; - } - - // Figure out how big the new type we're merging in is... - unsigned NewTySize = NewTy->isSized() ? (unsigned)TD.getTypeSize(NewTy) : 0; - - // Otherwise check to see if we can fold this type into the current node. If - // we can't, we fold the node completely, if we can, we potentially update our - // internal state. - // - if (Ty == Type::VoidTy) { - // If this is the first type that this node has seen, just accept it without - // question.... - assert(Offset == 0 && !isArray() && - "Cannot have an offset into a void node!"); - - // If this node would have to have an unreasonable number of fields, just - // collapse it. This can occur for fortran common blocks, which have stupid - // things like { [100000000 x double], [1000000 x double] }. - unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift; - if (NumFields > DSAFieldLimit) { - foldNodeCompletely(); - return true; - } - - Ty = NewTy; - NodeType &= ~Array; - if (WillBeArray) NodeType |= Array; - Size = NewTySize; - - // Calculate the number of outgoing links from this node. - Links.resize(NumFields); - return false; - } - - // Handle node expansion case here... - if (Offset+NewTySize > Size) { - // It is illegal to grow this node if we have treated it as an array of - // objects... - if (isArray()) { - if (FoldIfIncompatible) foldNodeCompletely(); - return true; - } - - // If this node would have to have an unreasonable number of fields, just - // collapse it. This can occur for fortran common blocks, which have stupid - // things like { [100000000 x double], [1000000 x double] }. - unsigned NumFields = (NewTySize+Offset+DS::PointerSize-1) >> DS::PointerShift; - if (NumFields > DSAFieldLimit) { - foldNodeCompletely(); - return true; - } - - if (Offset) { - //handle some common cases: - // Ty: struct { t1, t2, t3, t4, ..., tn} - // NewTy: struct { offset, stuff...} - // try merge with NewTy: struct {t1, t2, stuff...} if offset lands exactly - // on a field in Ty - if (isa(NewTy) && isa(Ty)) { - DOUT << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n"; - const StructType *STy = cast(Ty); - const StructLayout &SL = *TD.getStructLayout(STy); - unsigned i = SL.getElementContainingOffset(Offset); - //Either we hit it exactly or give up - if (SL.MemberOffsets[i] != Offset) { - if (FoldIfIncompatible) foldNodeCompletely(); - return true; - } - std::vector nt; - for (unsigned x = 0; x < i; ++x) - nt.push_back(STy->getElementType(x)); - STy = cast(NewTy); - nt.insert(nt.end(), STy->element_begin(), STy->element_end()); - //and merge - STy = StructType::get(nt); - DOUT << "Trying with: " << *STy << "\n"; - return mergeTypeInfo(STy, 0); - } - - //Ty: struct { t1, t2, t3 ... tn} - //NewTy T offset x - //try merge with NewTy: struct : {t1, t2, T} if offset lands on a field - //in Ty - if (isa(Ty)) { - DOUT << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n"; - const StructType *STy = cast(Ty); - const StructLayout &SL = *TD.getStructLayout(STy); - unsigned i = SL.getElementContainingOffset(Offset); - //Either we hit it exactly or give up - if (SL.MemberOffsets[i] != Offset) { - if (FoldIfIncompatible) foldNodeCompletely(); - return true; - } - std::vector nt; - for (unsigned x = 0; x < i; ++x) - nt.push_back(STy->getElementType(x)); - nt.push_back(NewTy); - //and merge - STy = StructType::get(nt); - DOUT << "Trying with: " << *STy << "\n"; - return mergeTypeInfo(STy, 0); - } - - assert(0 && - "UNIMP: Trying to merge a growth type into " - "offset != 0: Collapsing!"); - abort(); - if (FoldIfIncompatible) foldNodeCompletely(); - return true; - - } - - - // Okay, the situation is nice and simple, we are trying to merge a type in - // at offset 0 that is bigger than our current type. Implement this by - // switching to the new type and then merge in the smaller one, which should - // hit the other code path here. If the other code path decides it's not - // ok, it will collapse the node as appropriate. - // - - const Type *OldTy = Ty; - Ty = NewTy; - NodeType &= ~Array; - if (WillBeArray) NodeType |= Array; - Size = NewTySize; - - // Must grow links to be the appropriate size... - Links.resize(NumFields); - - // Merge in the old type now... which is guaranteed to be smaller than the - // "current" type. - return mergeTypeInfo(OldTy, 0); - } - - assert(Offset <= Size && - "Cannot merge something into a part of our type that doesn't exist!"); - - // Find the section of Ty that NewTy overlaps with... first we find the - // type that starts at offset Offset. - // - unsigned O = 0; - const Type *SubType = Ty; - while (O < Offset) { - assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!"); - - switch (SubType->getTypeID()) { - case Type::StructTyID: { - const StructType *STy = cast(SubType); - const StructLayout &SL = *TD.getStructLayout(STy); - unsigned i = SL.getElementContainingOffset(Offset-O); - - // The offset we are looking for must be in the i'th element... - SubType = STy->getElementType(i); - O += (unsigned)SL.MemberOffsets[i]; - break; - } - case Type::ArrayTyID: { - SubType = cast(SubType)->getElementType(); - unsigned ElSize = (unsigned)TD.getTypeSize(SubType); - unsigned Remainder = (Offset-O) % ElSize; - O = Offset-Remainder; - break; - } - default: - if (FoldIfIncompatible) foldNodeCompletely(); - return true; - } - } - - assert(O == Offset && "Could not achieve the correct offset!"); - - // If we found our type exactly, early exit - if (SubType == NewTy) return false; - - // Differing function types don't require us to merge. They are not values - // anyway. - if (isa(SubType) && - isa(NewTy)) return false; - - unsigned SubTypeSize = SubType->isSized() ? - (unsigned)TD.getTypeSize(SubType) : 0; - - // Ok, we are getting desperate now. Check for physical subtyping, where we - // just require each element in the node to be compatible. - if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 && - SubTypeSize && SubTypeSize < 256 && - ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD)) - return false; - - // Okay, so we found the leader type at the offset requested. Search the list - // of types that starts at this offset. If SubType is currently an array or - // structure, the type desired may actually be the first element of the - // composite type... - // - unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored - while (SubType != NewTy) { - const Type *NextSubType = 0; - unsigned NextSubTypeSize = 0; - unsigned NextPadSize = 0; - switch (SubType->getTypeID()) { - case Type::StructTyID: { - const StructType *STy = cast(SubType); - const StructLayout &SL = *TD.getStructLayout(STy); - if (SL.MemberOffsets.size() > 1) - NextPadSize = (unsigned)SL.MemberOffsets[1]; - else - NextPadSize = SubTypeSize; - NextSubType = STy->getElementType(0); - NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType); - break; - } - case Type::ArrayTyID: - NextSubType = cast(SubType)->getElementType(); - NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType); - NextPadSize = NextSubTypeSize; - break; - default: ; - // fall out - } - - if (NextSubType == 0) - break; // In the default case, break out of the loop - - if (NextPadSize < NewTySize) - break; // Don't allow shrinking to a smaller type than NewTySize - SubType = NextSubType; - SubTypeSize = NextSubTypeSize; - PadSize = NextPadSize; - } - - // If we found the type exactly, return it... - if (SubType == NewTy) - return false; - - // Check to see if we have a compatible, but different type... - if (NewTySize == SubTypeSize) { - // Check to see if this type is obviously convertible... int -> uint f.e. - if (NewTy->canLosslesslyBitCastTo(SubType)) - return false; - - // Check to see if we have a pointer & integer mismatch going on here, - // loading a pointer as a long, for example. - // - if (SubType->isInteger() && isa(NewTy) || - NewTy->isInteger() && isa(SubType)) - return false; - } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) { - // We are accessing the field, plus some structure padding. Ignore the - // structure padding. - return false; - } - - Module *M = 0; - if (getParentGraph()->retnodes_begin() != getParentGraph()->retnodes_end()) - M = getParentGraph()->retnodes_begin()->first->getParent(); - - DOUT << "MergeTypeInfo Folding OrigTy: "; - DEBUG(WriteTypeSymbolic(*cerr.stream(), Ty, M) << "\n due to:"; - WriteTypeSymbolic(*cerr.stream(), NewTy, M) << " @ " << Offset << "!\n" - << "SubType: "; - WriteTypeSymbolic(*cerr.stream(), SubType, M) << "\n\n"); - - if (FoldIfIncompatible) foldNodeCompletely(); - return true; -} - - - -/// 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... - } -} - - -/// MergeSortedVectors - Efficiently merge a vector into another vector where -/// duplicates are not allowed and both are sorted. This assumes that 'T's are -/// efficiently copyable and have sane comparison semantics. -/// -static void MergeSortedVectors(std::vector &Dest, - const std::vector &Src) { - // By far, the most common cases will be the simple ones. In these cases, - // avoid having to allocate a temporary vector... - // - if (Src.empty()) { // Nothing to merge in... - return; - } else if (Dest.empty()) { // Just copy the result in... - Dest = Src; - } else if (Src.size() == 1) { // Insert a single element... - const GlobalValue *V = Src[0]; - std::vector::iterator I = - std::lower_bound(Dest.begin(), Dest.end(), V); - if (I == Dest.end() || *I != Src[0]) // If not already contained... - Dest.insert(I, Src[0]); - } else if (Dest.size() == 1) { - GlobalValue *Tmp = Dest[0]; // Save value in temporary... - Dest = Src; // Copy over list... - std::vector::iterator I = - std::lower_bound(Dest.begin(), Dest.end(), Tmp); - if (I == Dest.end() || *I != Tmp) // If not already contained... - Dest.insert(I, Tmp); - - } else { - // Make a copy to the side of Dest... - std::vector Old(Dest); - - // Make space for all of the type entries now... - Dest.resize(Dest.size()+Src.size()); - - // Merge the two sorted ranges together... into Dest. - std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin()); - - // Now erase any duplicate entries that may have accumulated into the - // vectors (because they were in both of the input sets) - Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end()); - } -} - -void DSNode::mergeGlobals(const std::vector &RHS) { - MergeSortedVectors(Globals, RHS); -} - -// 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()->isArray()) - NH.getNode()->foldNodeCompletely(); - } else if (CurNodeH.getNode()->isArray()) { - NH.getNode()->foldNodeCompletely(); - } -#endif - } - - // Merge the type entries of the two nodes together... - if (NH.getNode()->Ty != Type::VoidTy) - CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset); - assert(!CurNodeH.getNode()->isDeadNode()); - - // 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); - } - - DSNode *N = NH.getNode(); - if (CurNodeH.getNode() == N || N == 0) return; - 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 (unsigned i = 0; i < N->getNumLinks(); ++i) { - DSNodeHandle &Link = N->getLink(i << DS::PointerShift); - if (Link.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 = ((i << DS::PointerShift)+NOffset) % CN->getSize(); - CN->addEdgeTo(MergeOffset, Link); - } - } - - // Now that there are no outgoing edges, all of the Links are dead. - N->Links.clear(); - - // Merge the globals list... - if (!N->Globals.empty()) { - CurNodeH.getNode()->mergeGlobals(N->Globals); - - // Delete the globals from the old node... - std::vector().swap(N->Globals); - } -} - - -/// 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. - DOUT << "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); -} - - -//===----------------------------------------------------------------------===// -// 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(); - return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); - } - - // 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) { - 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(); - return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); - } - } - } - - 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 (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { - const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); - 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 = ((i << DS::PointerShift)+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) { - 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->getGlobalsList()); - - return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); -} - -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->isArray()) { - DN->foldNodeCompletely(); - DN = NH.getNode(); - } - } else if (DN->isArray()) { - DN->foldNodeCompletely(); - DN = NH.getNode(); - } -#endif - } - - // Merge the type entries of the two nodes together... - if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) { - DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset()); - DN = NH.getNode(); - } - } - - 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->getGlobalsList()); - - // 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) { - 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->getGlobalsList()); - } - } 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); - - unsigned NHOffset = NH.getOffset(); - NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset())); - - assert(NH.getNode() && - (NH.getOffset() > NHOffset || - (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) && - "Merging did not adjust the offset!"); - - // 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) { - 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())); - } - } - - - // 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 (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { - const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); - 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 = - ((i << DS::PointerShift)+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 = ((i << DS::PointerShift)+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()); - 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) - DestCS.addPtrArg(getClonedNH(SrcCS.getPtrArg(a))); -} - - -//===----------------------------------------------------------------------===// -// DSCallSite Implementation -//===----------------------------------------------------------------------===// - -// Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h -Function &DSCallSite::getCaller() const { - return *Site.getInstruction()->getParent()->getParent(); -} - -void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, - ReachabilityCloner &RC) { - NH = RC.getClonedNH(Src); -} - -//===----------------------------------------------------------------------===// -// DSGraph Implementation -//===----------------------------------------------------------------------===// - -/// getFunctionNames - Return a space separated list of the name of the -/// functions in this graph (if any) -std::string DSGraph::getFunctionNames() const { - switch (getReturnNodes().size()) { - case 0: return "Globals graph"; - case 1: return retnodes_begin()->first->getName(); - default: - std::string Return; - for (DSGraph::retnodes_iterator I = retnodes_begin(); - I != retnodes_end(); ++I) - Return += I->first->getName() + " "; - Return.erase(Return.end()-1, Return.end()); // Remove last space character - return Return; - } -} - - -DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses &ECs, - unsigned CloneFlags) - : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) { - PrintAuxCalls = false; - cloneInto(G, CloneFlags); -} - -DSGraph::~DSGraph() { - FunctionCalls.clear(); - AuxFunctionCalls.clear(); - ScalarMap.clear(); - ReturnNodes.clear(); - - // Drop all intra-node references, so that assertions don't fail... - for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) - NI->dropAllReferences(); - - // Free all of the nodes. - Nodes.clear(); -} - -// dump - Allow inspection of graph in a debugger. -void DSGraph::dump() const { print(cerr); } - - -/// remapLinks - Change all of the Links in the current node according to the -/// specified mapping. -/// -void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { - for (unsigned i = 0, e = Links.size(); i != e; ++i) - if (DSNode *N = Links[i].getNode()) { - DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N); - if (ONMI != OldNodeMap.end()) { - DSNode *ONMIN = ONMI->second.getNode(); - Links[i].setTo(ONMIN, Links[i].getOffset()+ONMI->second.getOffset()); - } - } -} - -/// addObjectToGraph - This method can be used to add global, stack, and heap -/// objects to the graph. This can be used when updating DSGraphs due to the -/// introduction of new temporary objects. The new object is not pointed to -/// and does not point to any other objects in the graph. -DSNode *DSGraph::addObjectToGraph(Value *Ptr, bool UseDeclaredType) { - assert(isa(Ptr->getType()) && "Ptr is not a pointer!"); - const Type *Ty = cast(Ptr->getType())->getElementType(); - DSNode *N = new DSNode(UseDeclaredType ? Ty : 0, this); - assert(ScalarMap[Ptr].isNull() && "Object already in this graph!"); - ScalarMap[Ptr] = N; - - if (GlobalValue *GV = dyn_cast(Ptr)) { - N->addGlobal(GV); - } else if (isa(Ptr)) { - N->setHeapNodeMarker(); - } else if (isa(Ptr)) { - N->setAllocaNodeMarker(); - } else { - assert(0 && "Illegal memory object input!"); - } - return N; -} - - -/// cloneInto - Clone the specified DSGraph into the current graph. The -/// translated ScalarMap for the old function is filled into the ScalarMap -/// for the graph, and the translated ReturnNodes map is returned into -/// ReturnNodes. -/// -/// The CloneFlags member controls various aspects of the cloning process. -/// -void DSGraph::cloneInto(const DSGraph &G, unsigned CloneFlags) { - TIME_REGION(X, "cloneInto"); - assert(&G != this && "Cannot clone graph into itself!"); - - NodeMapTy OldNodeMap; - - // Remove alloca or mod/ref bits as specified... - unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0) - | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0) - | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0); - BitsToClear |= DSNode::DEAD; // Clear dead flag... - - for (node_const_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) { - assert(!I->isForwarding() && - "Forward nodes shouldn't be in node list!"); - DSNode *New = new DSNode(*I, this); - New->maskNodeTypes(~BitsToClear); - OldNodeMap[I] = New; - } - -#ifndef NDEBUG - Timer::addPeakMemoryMeasurement(); -#endif - - // Rewrite the links in the new nodes to point into the current graph now. - // Note that we don't loop over the node's list to do this. The problem is - // that remaping links can cause recursive merging to happen, which means - // that node_iterator's can get easily invalidated! Because of this, we - // loop over the OldNodeMap, which contains all of the new nodes as the - // .second element of the map elements. Also note that if we remap a node - // more than once, we won't break anything. - for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end(); - I != E; ++I) - I->second.getNode()->remapLinks(OldNodeMap); - - // Copy the scalar map... merging all of the global nodes... - for (DSScalarMap::const_iterator I = G.ScalarMap.begin(), - E = G.ScalarMap.end(); I != E; ++I) { - DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; - DSNodeHandle &H = ScalarMap.getRawEntryRef(I->first); - DSNode *MappedNodeN = MappedNode.getNode(); - H.mergeWith(DSNodeHandle(MappedNodeN, - I->second.getOffset()+MappedNode.getOffset())); - } - - if (!(CloneFlags & DontCloneCallNodes)) { - // Copy the function calls list. - for (fc_iterator I = G.fc_begin(), E = G.fc_end(); I != E; ++I) - FunctionCalls.push_back(DSCallSite(*I, OldNodeMap)); - } - - if (!(CloneFlags & DontCloneAuxCallNodes)) { - // Copy the auxiliary function calls list. - for (afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I) - AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap)); - } - - // Map the return node pointers over... - for (retnodes_iterator I = G.retnodes_begin(), - E = G.retnodes_end(); I != E; ++I) { - const DSNodeHandle &Ret = I->second; - DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()]; - DSNode *MappedRetN = MappedRet.getNode(); - ReturnNodes.insert(std::make_pair(I->first, - DSNodeHandle(MappedRetN, - MappedRet.getOffset()+Ret.getOffset()))); - } -} - -/// spliceFrom - Logically perform the operation of cloning the RHS graph into -/// this graph, then clearing the RHS graph. Instead of performing this as -/// two seperate operations, do it as a single, much faster, one. -/// -void DSGraph::spliceFrom(DSGraph &RHS) { - // Change all of the nodes in RHS to think we are their parent. - for (NodeListTy::iterator I = RHS.Nodes.begin(), E = RHS.Nodes.end(); - I != E; ++I) - I->setParentGraph(this); - // Take all of the nodes. - Nodes.splice(Nodes.end(), RHS.Nodes); - - // Take all of the calls. - FunctionCalls.splice(FunctionCalls.end(), RHS.FunctionCalls); - AuxFunctionCalls.splice(AuxFunctionCalls.end(), RHS.AuxFunctionCalls); - - // Take all of the return nodes. - if (ReturnNodes.empty()) { - ReturnNodes.swap(RHS.ReturnNodes); - } else { - ReturnNodes.insert(RHS.ReturnNodes.begin(), RHS.ReturnNodes.end()); - RHS.ReturnNodes.clear(); - } - - // Merge the scalar map in. - ScalarMap.spliceFrom(RHS.ScalarMap); -} - -/// 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(); - } -} - - -/// getFunctionArgumentsForCall - Given a function that is currently in this -/// graph, return the DSNodeHandles that correspond to the pointer-compatible -/// function arguments. The vector is filled in with the return value (or -/// null if it is not pointer compatible), followed by all of the -/// pointer-compatible arguments. -void DSGraph::getFunctionArgumentsForCall(Function *F, - std::vector &Args) const { - Args.push_back(getReturnNodeFor(*F)); - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI) - if (isPointerType(AI->getType())) { - Args.push_back(getNodeForValue(AI)); - assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?"); - } -} - -namespace { - // HackedGraphSCCFinder - This is used to find nodes that have a path from the - // node to a node cloned by the ReachabilityCloner object contained. To be - // extra obnoxious it ignores edges from nodes that are globals, and truncates - // search at RC marked nodes. This is designed as an object so that - // intermediate results can be memoized across invocations of - // PathExistsToClonedNode. - struct HackedGraphSCCFinder { - ReachabilityCloner &RC; - unsigned CurNodeId; - std::vector SCCStack; - std::map > NodeInfo; - - HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) { - // Remove null pointer as a special case. - NodeInfo[0] = std::make_pair(0, false); - } - - std::pair &VisitForSCCs(const DSNode *N); - - bool PathExistsToClonedNode(const DSNode *N) { - return VisitForSCCs(N).second; - } - - bool PathExistsToClonedNode(const DSCallSite &CS) { - if (PathExistsToClonedNode(CS.getRetVal().getNode())) - return true; - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) - if (PathExistsToClonedNode(CS.getPtrArg(i).getNode())) - return true; - return false; - } - }; -} - -std::pair &HackedGraphSCCFinder:: -VisitForSCCs(const DSNode *N) { - std::map >::iterator - NodeInfoIt = NodeInfo.lower_bound(N); - if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N) - return NodeInfoIt->second; - - unsigned Min = CurNodeId++; - unsigned MyId = Min; - std::pair &ThisNodeInfo = - NodeInfo.insert(NodeInfoIt, - std::make_pair(N, std::make_pair(MyId, false)))->second; - - // Base case: if we find a global, this doesn't reach the cloned graph - // portion. - if (N->isGlobalNode()) { - ThisNodeInfo.second = false; - return ThisNodeInfo; - } - - // Base case: if this does reach the cloned graph portion... it does. :) - if (RC.hasClonedNode(N)) { - ThisNodeInfo.second = true; - return ThisNodeInfo; - } - - SCCStack.push_back(N); - - // Otherwise, check all successors. - bool AnyDirectSuccessorsReachClonedNodes = false; - for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end(); - EI != EE; ++EI) - if (DSNode *Succ = EI->getNode()) { - std::pair &SuccInfo = VisitForSCCs(Succ); - if (SuccInfo.first < Min) Min = SuccInfo.first; - AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second; - } - - if (Min != MyId) - return ThisNodeInfo; // Part of a large SCC. Leave self on stack. - - if (SCCStack.back() == N) { // Special case single node SCC. - SCCStack.pop_back(); - ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes; - return ThisNodeInfo; - } - - // Find out if any direct successors of any node reach cloned nodes. - if (!AnyDirectSuccessorsReachClonedNodes) - for (unsigned i = SCCStack.size()-1; SCCStack[i] != N; --i) - for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end(); - EI != EE; ++EI) - if (DSNode *N = EI->getNode()) - if (NodeInfo[N].second) { - AnyDirectSuccessorsReachClonedNodes = true; - goto OutOfLoop; - } -OutOfLoop: - // If any successor reaches a cloned node, mark all nodes in this SCC as - // reaching the cloned node. - if (AnyDirectSuccessorsReachClonedNodes) - while (SCCStack.back() != N) { - NodeInfo[SCCStack.back()].second = true; - SCCStack.pop_back(); - } - SCCStack.pop_back(); - ThisNodeInfo.second = true; - return ThisNodeInfo; -} - -/// mergeInCallFromOtherGraph - This graph merges in the minimal number of -/// nodes from G2 into 'this' graph, merging the bindings specified by the -/// call site (in this graph) with the bindings specified by the vector in G2. -/// The two DSGraphs must be different. -/// -void DSGraph::mergeInGraph(const DSCallSite &CS, - std::vector &Args, - const DSGraph &Graph, unsigned CloneFlags) { - TIME_REGION(X, "mergeInGraph"); - - assert((CloneFlags & DontCloneCallNodes) && - "Doesn't support copying of call nodes!"); - - // If this is not a recursive call, clone the graph into this graph... - if (&Graph == this) { - // Merge the return value with the return value of the context. - Args[0].mergeWith(CS.getRetVal()); - - // Resolve all of the function arguments. - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { - if (i == Args.size()-1) - break; - - // Add the link from the argument scalar to the provided value. - Args[i+1].mergeWith(CS.getPtrArg(i)); - } - return; - } - - // Clone the callee's graph into the current graph, keeping track of where - // scalars in the old graph _used_ to point, and of the new nodes matching - // nodes of the old graph. - ReachabilityCloner RC(*this, Graph, CloneFlags); - - // Map the return node pointer over. - if (!CS.getRetVal().isNull()) - RC.merge(CS.getRetVal(), Args[0]); - - // Map over all of the arguments. - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { - if (i == Args.size()-1) - break; - - // Add the link from the argument scalar to the provided value. - RC.merge(CS.getPtrArg(i), Args[i+1]); - } - - // We generally don't want to copy global nodes or aux calls from the callee - // graph to the caller graph. However, we have to copy them if there is a - // path from the node to a node we have already copied which does not go - // through another global. Compute the set of node that can reach globals and - // aux call nodes to copy over, then do it. - std::vector AuxCallToCopy; - std::vector GlobalsToCopy; - - // NodesReachCopiedNodes - Memoize results for efficiency. Contains a - // true/false value for every visited node that reaches a copied node without - // going through a global. - HackedGraphSCCFinder SCCFinder(RC); - - if (!(CloneFlags & DontCloneAuxCallNodes)) - for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I) - if (SCCFinder.PathExistsToClonedNode(*I)) - AuxCallToCopy.push_back(&*I); -// else if (I->isIndirectCall()){ -// //If the call node doesn't have any callees, clone it -// std::vector< Function *> List; -// I->getCalleeNode()->addFullFunctionList(List); -// if (!List.size()) -// AuxCallToCopy.push_back(&*I); -// } - - const DSScalarMap &GSM = Graph.getScalarMap(); - for (DSScalarMap::global_iterator GI = GSM.global_begin(), - E = GSM.global_end(); GI != E; ++GI) { - DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode(); - for (DSNode::edge_iterator EI = GlobalNode->edge_begin(), - EE = GlobalNode->edge_end(); EI != EE; ++EI) - if (SCCFinder.PathExistsToClonedNode(EI->getNode())) { - GlobalsToCopy.push_back(*GI); - break; - } - } - - // Copy aux calls that are needed. - for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i) - AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC)); - - // Copy globals that are needed. - for (unsigned i = 0, e = GlobalsToCopy.size(); i != e; ++i) - RC.getClonedNH(Graph.getNodeForValue(GlobalsToCopy[i])); -} - - - -/// mergeInGraph - The method is used for merging graphs together. If the -/// argument graph is not *this, it makes a clone of the specified graph, then -/// merges the nodes specified in the call site with the formal arguments in the -/// graph. -/// -void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F, - const DSGraph &Graph, unsigned CloneFlags) { - // Set up argument bindings. - std::vector Args; - Graph.getFunctionArgumentsForCall(&F, Args); - - mergeInGraph(CS, Args, Graph, CloneFlags); -} - -/// getCallSiteForArguments - Get the arguments and return value bindings for -/// the specified function in the current graph. -/// -DSCallSite DSGraph::getCallSiteForArguments(Function &F) const { - std::vector Args; - - for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) - if (isPointerType(I->getType())) - Args.push_back(getNodeForValue(I)); - - return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args); -} - -/// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in -/// the context of this graph, return the DSCallSite for it. -DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const { - DSNodeHandle RetVal; - Instruction *I = CS.getInstruction(); - if (isPointerType(I->getType())) - RetVal = getNodeForValue(I); - - std::vector Args; - Args.reserve(CS.arg_end()-CS.arg_begin()); - - // Calculate the arguments vector... - for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) - if (isPointerType((*I)->getType())) - if (isa(*I)) - Args.push_back(DSNodeHandle()); - else - Args.push_back(getNodeForValue(*I)); - - // Add a new function call entry... - if (Function *F = CS.getCalledFunction()) - return DSCallSite(CS, RetVal, F, Args); - else - return DSCallSite(CS, RetVal, - getNodeForValue(CS.getCalledValue()).getNode(), Args); -} - - - -// markIncompleteNodes - Mark the specified node as having contents that are not -// known with the current analysis we have performed. Because a node makes all -// of the nodes it can reach incomplete if the node itself is incomplete, we -// must recursively traverse the data structure graph, marking all reachable -// nodes as incomplete. -// -static void markIncompleteNode(DSNode *N) { - // Stop recursion if no node, or if node already marked... - if (N == 0 || N->isIncomplete()) return; - - // Actually mark the node - N->setIncompleteMarker(); - - // Recursively process children... - for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I) - if (DSNode *DSN = I->getNode()) - markIncompleteNode(DSN); -} - -static void markIncomplete(DSCallSite &Call) { - // Then the return value is certainly incomplete! - markIncompleteNode(Call.getRetVal().getNode()); - - // All objects pointed to by function arguments are incomplete! - for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) - markIncompleteNode(Call.getPtrArg(i).getNode()); -} - -// markIncompleteNodes - Traverse the graph, identifying nodes that may be -// modified by other functions that have not been resolved yet. This marks -// nodes that are reachable through three sources of "unknownness": -// -// Global Variables, Function Calls, and Incoming Arguments -// -// For any node that may have unknown components (because something outside the -// scope of current analysis may have modified it), the 'Incomplete' flag is -// added to the NodeType. -// -void DSGraph::markIncompleteNodes(unsigned Flags) { - // Mark any incoming arguments as incomplete. - if (Flags & DSGraph::MarkFormalArgs) - for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); - FI != E; ++FI) { - Function &F = *FI->first; - for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); - I != E; ++I) - if (isPointerType(I->getType())) - markIncompleteNode(getNodeForValue(I).getNode()); - markIncompleteNode(FI->second.getNode()); - } - - // Mark stuff passed into functions calls as being incomplete. - if (!shouldPrintAuxCalls()) - for (std::list::iterator I = FunctionCalls.begin(), - E = FunctionCalls.end(); I != E; ++I) - markIncomplete(*I); - else - for (std::list::iterator I = AuxFunctionCalls.begin(), - E = AuxFunctionCalls.end(); I != E; ++I) - markIncomplete(*I); - - // Mark all global nodes as incomplete. - for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), - E = ScalarMap.global_end(); I != E; ++I) - if (GlobalVariable *GV = dyn_cast(*I)) - if (!GV->hasInitializer() || // Always mark external globals incomp. - (!GV->isConstant() && (Flags & DSGraph::IgnoreGlobals) == 0)) - markIncompleteNode(ScalarMap[GV].getNode()); -} - -static inline void killIfUselessEdge(DSNodeHandle &Edge) { - if (DSNode *N = Edge.getNode()) // Is there an edge? - if (N->getNumReferrers() == 1) // Does it point to a lonely node? - // No interesting info? - if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 && - N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) - Edge.setTo(0, 0); // Kill the edge! -} - -static inline bool nodeContainsExternalFunction(const DSNode *N) { - std::vector Funcs; - N->addFullFunctionList(Funcs); - for (unsigned i = 0, e = Funcs.size(); i != e; ++i) - if (Funcs[i]->isExternal()) return true; - return false; -} - -static void removeIdenticalCalls(std::list &Calls) { - // Remove trivially identical function calls - Calls.sort(); // Sort by callee as primary key! - - // Scan the call list cleaning it up as necessary... - DSNodeHandle LastCalleeNode; -#if 0 - Function *LastCalleeFunc = 0; - unsigned NumDuplicateCalls = 0; -#endif - bool LastCalleeContainsExternalFunction = false; - - unsigned NumDeleted = 0; - for (std::list::iterator I = Calls.begin(), E = Calls.end(); - I != E;) { - DSCallSite &CS = *I; - std::list::iterator OldIt = I++; - - if (!CS.isIndirectCall()) { - LastCalleeNode = 0; - } else { - DSNode *Callee = CS.getCalleeNode(); - - // If the Callee is a useless edge, this must be an unreachable call site, - // eliminate it. - if (Callee->getNumReferrers() == 1 && Callee->isComplete() && - Callee->getGlobalsList().empty()) { // No useful info? - DOUT << "WARNING: Useless call site found.\n"; - Calls.erase(OldIt); - ++NumDeleted; - continue; - } - - // If the last call site in the list has the same callee as this one, and - // if the callee contains an external function, it will never be - // resolvable, just merge the call sites. - if (!LastCalleeNode.isNull() && LastCalleeNode.getNode() == Callee) { - LastCalleeContainsExternalFunction = - nodeContainsExternalFunction(Callee); - - std::list::iterator PrevIt = OldIt; - --PrevIt; - PrevIt->mergeWith(CS); - - // No need to keep this call anymore. - Calls.erase(OldIt); - ++NumDeleted; - continue; - } else { - LastCalleeNode = Callee; - } - } - - // If the return value or any arguments point to a void node with no - // information at all in it, and the call node is the only node to point - // to it, remove the edge to the node (killing the node). - // - killIfUselessEdge(CS.getRetVal()); - for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a) - killIfUselessEdge(CS.getPtrArg(a)); - -#if 0 - // If this call site calls the same function as the last call site, and if - // the function pointer contains an external function, this node will - // never be resolved. Merge the arguments of the call node because no - // information will be lost. - // - if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) || - (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) { - ++NumDuplicateCalls; - if (NumDuplicateCalls == 1) { - if (LastCalleeNode) - LastCalleeContainsExternalFunction = - nodeContainsExternalFunction(LastCalleeNode); - else - LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); - } - - // It is not clear why, but enabling this code makes DSA really - // sensitive to node forwarding. Basically, with this enabled, DSA - // performs different number of inlinings based on which nodes are - // forwarding or not. This is clearly a problem, so this code is - // disabled until this can be resolved. -#if 1 - if (LastCalleeContainsExternalFunction -#if 0 - || - // This should be more than enough context sensitivity! - // FIXME: Evaluate how many times this is tripped! - NumDuplicateCalls > 20 -#endif - ) { - - std::list::iterator PrevIt = OldIt; - --PrevIt; - PrevIt->mergeWith(CS); - - // No need to keep this call anymore. - Calls.erase(OldIt); - ++NumDeleted; - continue; - } -#endif - } else { - if (CS.isDirectCall()) { - LastCalleeFunc = CS.getCalleeFunc(); - LastCalleeNode = 0; - } else { - LastCalleeNode = CS.getCalleeNode(); - LastCalleeFunc = 0; - } - NumDuplicateCalls = 0; - } -#endif - - if (I != Calls.end() && CS == *I) { - LastCalleeNode = 0; - Calls.erase(OldIt); - ++NumDeleted; - continue; - } - } - - // Resort now that we simplified things. - Calls.sort(); - - // Now that we are in sorted order, eliminate duplicates. - std::list::iterator CI = Calls.begin(), CE = Calls.end(); - if (CI != CE) - while (1) { - std::list::iterator OldIt = CI++; - if (CI == CE) break; - - // If this call site is now the same as the previous one, we can delete it - // as a duplicate. - if (*OldIt == *CI) { - Calls.erase(CI); - CI = OldIt; - ++NumDeleted; - } - } - - //Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end()); - - // Track the number of call nodes merged away... - NumCallNodesMerged += NumDeleted; - - if (NumDeleted) - DOUT << "Merged " << NumDeleted << " call nodes.\n"; -} - - -// removeTriviallyDeadNodes - After the graph has been constructed, this method -// removes all unreachable nodes that are created because they got merged with -// other nodes in the graph. These nodes will all be trivially unreachable, so -// we don't have to perform any non-trivial analysis here. -// -void DSGraph::removeTriviallyDeadNodes() { - TIME_REGION(X, "removeTriviallyDeadNodes"); - -#if 0 - /// NOTE: This code is disabled. This slows down DSA on 177.mesa - /// substantially! - - // Loop over all of the nodes in the graph, calling getNode on each field. - // This will cause all nodes to update their forwarding edges, causing - // forwarded nodes to be delete-able. - { TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate"); - for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) { - DSNode &N = *NI; - for (unsigned l = 0, e = N.getNumLinks(); l != e; ++l) - N.getLink(l*N.getPointerSize()).getNode(); - } - } - - // NOTE: This code is disabled. Though it should, in theory, allow us to - // remove more nodes down below, the scan of the scalar map is incredibly - // expensive for certain programs (with large SCCs). In the future, if we can - // make the scalar map scan more efficient, then we can reenable this. - { TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap"); - - // Likewise, forward any edges from the scalar nodes. While we are at it, - // clean house a bit. - for (DSScalarMap::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){ - I->second.getNode(); - ++I; - } - } -#endif - bool isGlobalsGraph = !GlobalsGraph; - - for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) { - DSNode &Node = *NI; - - // Do not remove *any* global nodes in the globals graph. - // This is a special case because such nodes may not have I, M, R flags set. - if (Node.isGlobalNode() && isGlobalsGraph) { - ++NI; - continue; - } - - if (Node.isComplete() && !Node.isModified() && !Node.isRead()) { - // This is a useless node if it has no mod/ref info (checked above), - // outgoing edges (which it cannot, as it is not modified in this - // context), and it has no incoming edges. If it is a global node it may - // have all of these properties and still have incoming edges, due to the - // scalar map, so we check those now. - // - if (Node.getNumReferrers() == Node.getGlobalsList().size()) { - const std::vector &Globals = Node.getGlobalsList(); - - // Loop through and make sure all of the globals are referring directly - // to the node... - for (unsigned j = 0, e = Globals.size(); j != e; ++j) { - DSNode *N = getNodeForValue(Globals[j]).getNode(); - assert(N == &Node && "ScalarMap doesn't match globals list!"); - } - - // Make sure NumReferrers still agrees, if so, the node is truly dead. - if (Node.getNumReferrers() == Globals.size()) { - for (unsigned j = 0, e = Globals.size(); j != e; ++j) - ScalarMap.erase(Globals[j]); - Node.makeNodeDead(); - ++NumTrivialGlobalDNE; - } - } - } - - if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) { - // This node is dead! - NI = Nodes.erase(NI); // Erase & remove from node list. - ++NumTrivialDNE; - } else { - ++NI; - } - } - - removeIdenticalCalls(FunctionCalls); - removeIdenticalCalls(AuxFunctionCalls); -} - - -/// 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(hash_set &ReachableNodes) const { - if (this == 0) return; - assert(getForwardNode() == 0 && "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->getNode()->markReachableNodes(ReachableNodes); -} - -void DSCallSite::markReachableNodes(hash_set &Nodes) const { - getRetVal().getNode()->markReachableNodes(Nodes); - if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); - - for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) - getPtrArg(i).getNode()->markReachableNodes(Nodes); -} - -// CanReachAliveNodes - Simple graph walker that recursively traverses the graph -// looking for a node that is marked alive. If an alive node is found, return -// true, otherwise return false. If an alive node is reachable, this node is -// marked as alive... -// -static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, - hash_set &Visited, - bool IgnoreGlobals) { - if (N == 0) return false; - assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!"); - - // If this is a global node, it will end up in the globals graph anyway, so we - // don't need to worry about it. - if (IgnoreGlobals && N->isGlobalNode()) return false; - - // If we know that this node is alive, return so! - if (Alive.count(N)) return true; - - // Otherwise, we don't think the node is alive yet, check for infinite - // recursion. - if (Visited.count(N)) return false; // Found a cycle - Visited.insert(N); // No recursion, insert into Visited... - - for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I) - if (CanReachAliveNodes(I->getNode(), Alive, Visited, IgnoreGlobals)) { - N->markReachableNodes(Alive); - return true; - } - return false; -} - -// CallSiteUsesAliveArgs - Return true if the specified call site can reach any -// alive nodes. -// -static bool CallSiteUsesAliveArgs(const DSCallSite &CS, - hash_set &Alive, - hash_set &Visited, - bool IgnoreGlobals) { - if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, - IgnoreGlobals)) - return true; - if (CS.isIndirectCall() && - CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals)) - return true; - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) - if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited, - IgnoreGlobals)) - return true; - return false; -} - -// removeDeadNodes - Use a more powerful reachability analysis to eliminate -// subgraphs that are unreachable. This often occurs because the data -// structure doesn't "escape" into it's caller, and thus should be eliminated -// from the caller's graph entirely. This is only appropriate to use when -// inlining graphs. -// -void DSGraph::removeDeadNodes(unsigned Flags) { - DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK()); - - // Reduce the amount of work we have to do... remove dummy nodes left over by - // merging... - removeTriviallyDeadNodes(); - - TIME_REGION(X, "removeDeadNodes"); - - // FIXME: Merge non-trivially identical call nodes... - - // Alive - a set that holds all nodes found to be reachable/alive. - hash_set Alive; - std::vector > GlobalNodes; - - // Copy and merge all information about globals to the GlobalsGraph if this is - // not a final pass (where unreachable globals are removed). - // - // Strip all alloca bits since the current function is only for the BU pass. - // Strip all incomplete bits since they are short-lived properties and they - // will be correctly computed when rematerializing nodes into the functions. - // - ReachabilityCloner GGCloner(*GlobalsGraph, *this, DSGraph::StripAllocaBit | - DSGraph::StripIncompleteBit); - - // Mark all nodes reachable by (non-global) scalar nodes as alive... -{ TIME_REGION(Y, "removeDeadNodes:scalarscan"); - for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); - I != E; ++I) - if (isa(I->first)) { // Keep track of global nodes - assert(!I->second.isNull() && "Null global node?"); - assert(I->second.getNode()->isGlobalNode() && "Should be a global node!"); - GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); - - // Make sure that all globals are cloned over as roots. - if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) { - DSGraph::ScalarMapTy::iterator SMI = - GlobalsGraph->getScalarMap().find(I->first); - if (SMI != GlobalsGraph->getScalarMap().end()) - GGCloner.merge(SMI->second, I->second); - else - GGCloner.getClonedNH(I->second); - } - } else { - I->second.getNode()->markReachableNodes(Alive); - } -} - - // The return values are alive as well. - for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end(); - I != E; ++I) - I->second.getNode()->markReachableNodes(Alive); - - // Mark any nodes reachable by primary calls as alive... - for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I) - I->markReachableNodes(Alive); - - - // Now find globals and aux call nodes that are already live or reach a live - // value (which makes them live in turn), and continue till no more are found. - // - bool Iterate; - hash_set Visited; - hash_set AuxFCallsAlive; - do { - Visited.clear(); - // If any global node points to a non-global that is "alive", the global is - // "alive" as well... Remove it from the GlobalNodes list so we only have - // unreachable globals in the list. - // - Iterate = false; - if (!(Flags & DSGraph::RemoveUnreachableGlobals)) - for (unsigned i = 0; i != GlobalNodes.size(); ++i) - if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited, - Flags & DSGraph::RemoveUnreachableGlobals)) { - std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to... - GlobalNodes.pop_back(); // erase efficiently - Iterate = true; - } - - // Mark only unresolvable call nodes for moving to the GlobalsGraph since - // call nodes that get resolved will be difficult to remove from that graph. - // The final unresolved call nodes must be handled specially at the end of - // the BU pass (i.e., in main or other roots of the call graph). - for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI) - if (!AuxFCallsAlive.count(&*CI) && - (CI->isIndirectCall() - || CallSiteUsesAliveArgs(*CI, Alive, Visited, - Flags & DSGraph::RemoveUnreachableGlobals))) { - CI->markReachableNodes(Alive); - AuxFCallsAlive.insert(&*CI); - Iterate = true; - } - } while (Iterate); - - // Move dead aux function calls to the end of the list - for (std::list::iterator CI = AuxFunctionCalls.begin(), - E = AuxFunctionCalls.end(); CI != E; ) - if (AuxFCallsAlive.count(&*CI)) - ++CI; - else { - // Copy and merge global nodes and dead aux call nodes into the - // GlobalsGraph, and all nodes reachable from those nodes. Update their - // target pointers using the GGCloner. - // - if (!(Flags & DSGraph::RemoveUnreachableGlobals)) - GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner)); - - AuxFunctionCalls.erase(CI++); - } - - // We are finally done with the GGCloner so we can destroy it. - GGCloner.destroy(); - - // At this point, any nodes which are visited, but not alive, are nodes - // which can be removed. Loop over all nodes, eliminating completely - // unreachable nodes. - // - std::vector DeadNodes; - DeadNodes.reserve(Nodes.size()); - for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) { - DSNode *N = NI++; - assert(!N->isForwarding() && "Forwarded node in nodes list?"); - - if (!Alive.count(N)) { - Nodes.remove(N); - assert(!N->isForwarding() && "Cannot remove a forwarding node!"); - DeadNodes.push_back(N); - N->dropAllReferences(); - ++NumDNE; - } - } - - // Remove all unreachable globals from the ScalarMap. - // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes. - // In either case, the dead nodes will not be in the set Alive. - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) - if (!Alive.count(GlobalNodes[i].second)) - ScalarMap.erase(GlobalNodes[i].first); - else - assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global"); - - // Delete all dead nodes now since their referrer counts are zero. - for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) - delete DeadNodes[i]; - - DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); -} - -void DSGraph::AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const { - assert(std::find(N->globals_begin(),N->globals_end(), GV) != - N->globals_end() && "Global value not in node!"); -} - -void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const { - if (CS.isIndirectCall()) { - AssertNodeInGraph(CS.getCalleeNode()); -#if 0 - if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() && - CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty()) - DOUT << "WARNING: WEIRD CALL SITE FOUND!\n"; -#endif - } - AssertNodeInGraph(CS.getRetVal().getNode()); - for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) - AssertNodeInGraph(CS.getPtrArg(j).getNode()); -} - -void DSGraph::AssertCallNodesInGraph() const { - for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I) - AssertCallSiteInGraph(*I); -} -void DSGraph::AssertAuxCallNodesInGraph() const { - for (afc_iterator I = afc_begin(), E = afc_end(); I != E; ++I) - AssertCallSiteInGraph(*I); -} - -void DSGraph::AssertGraphOK() const { - for (node_const_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) - NI->assertOK(); - - for (ScalarMapTy::const_iterator I = ScalarMap.begin(), - E = ScalarMap.end(); I != E; ++I) { - assert(!I->second.isNull() && "Null node in scalarmap!"); - AssertNodeInGraph(I->second.getNode()); - if (GlobalValue *GV = dyn_cast(I->first)) { - assert(I->second.getNode()->isGlobalNode() && - "Global points to node, but node isn't global?"); - AssertNodeContainsGlobal(I->second.getNode(), GV); - } - } - AssertCallNodesInGraph(); - AssertAuxCallNodesInGraph(); - - // Check that all pointer arguments to any functions in this graph have - // destinations. - for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(), - E = ReturnNodes.end(); - RI != E; ++RI) { - Function &F = *RI->first; - for (Function::arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI) - if (isPointerType(AI->getType())) - assert(!getNodeForValue(AI).isNull() && - "Pointer argument must be in the scalar map!"); - } -} - -/// computeNodeMapping - Given roots in two different DSGraphs, traverse the -/// nodes reachable from the two graphs, computing the mapping of nodes from the -/// first to the second graph. This mapping may be many-to-one (i.e. the first -/// graph may have multiple nodes representing one node in the second graph), -/// but it will not work if there is a one-to-many or many-to-many mapping. -/// -void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, - const DSNodeHandle &NH2, NodeMapTy &NodeMap, - bool StrictChecking) { - DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode(); - if (N1 == 0 || N2 == 0) return; - - DSNodeHandle &Entry = NodeMap[N1]; - if (!Entry.isNull()) { - // Termination of recursion! - if (StrictChecking) { - assert(Entry.getNode() == N2 && "Inconsistent mapping detected!"); - assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) || - Entry.getNode()->isNodeCompletelyFolded()) && - "Inconsistent mapping detected!"); - } - return; - } - - Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); - - // Loop over all of the fields that N1 and N2 have in common, recursively - // mapping the edges together now. - int N2Idx = NH2.getOffset()-NH1.getOffset(); - unsigned N2Size = N2->getSize(); - if (N2Size == 0) return; // No edges to map to. - - for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) { - const DSNodeHandle &N1NH = N1->getLink(i); - // Don't call N2->getLink if not needed (avoiding crash if N2Idx is not - // aligned right). - if (!N1NH.isNull()) { - if (unsigned(N2Idx)+i < N2Size) - computeNodeMapping(N1NH, N2->getLink(N2Idx+i), NodeMap); - else - computeNodeMapping(N1NH, - N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap); - } - } -} - - -/// computeGToGGMapping - Compute the mapping of nodes in the global graph to -/// nodes in this graph. -void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) { - DSGraph &GG = *getGlobalsGraph(); - - DSScalarMap &SM = getScalarMap(); - for (DSScalarMap::global_iterator I = SM.global_begin(), - E = SM.global_end(); I != E; ++I) - DSGraph::computeNodeMapping(SM[*I], GG.getNodeForValue(*I), NodeMap); -} - -/// computeGGToGMapping - Compute the mapping of nodes in the global graph to -/// nodes in this graph. Note that any uses of this method are probably bugs, -/// unless it is known that the globals graph has been merged into this graph! -void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) { - NodeMapTy NodeMap; - computeGToGGMapping(NodeMap); - - while (!NodeMap.empty()) { - InvNodeMap.insert(std::make_pair(NodeMap.begin()->second, - NodeMap.begin()->first)); - NodeMap.erase(NodeMap.begin()); - } -} - - -/// computeCalleeCallerMapping - Given a call from a function in the current -/// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the -/// mapping of nodes from the callee to nodes in the caller. -void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee, - DSGraph &CalleeGraph, - NodeMapTy &NodeMap) { - - DSCallSite CalleeArgs = - CalleeGraph.getCallSiteForArguments(const_cast(Callee)); - - computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap); - - unsigned NumArgs = CS.getNumPtrArgs(); - if (NumArgs > CalleeArgs.getNumPtrArgs()) - NumArgs = CalleeArgs.getNumPtrArgs(); - - for (unsigned i = 0; i != NumArgs; ++i) - computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap); - - // Map the nodes that are pointed to by globals. - DSScalarMap &CalleeSM = CalleeGraph.getScalarMap(); - DSScalarMap &CallerSM = getScalarMap(); - - if (CalleeSM.global_size() >= CallerSM.global_size()) { - for (DSScalarMap::global_iterator GI = CallerSM.global_begin(), - E = CallerSM.global_end(); GI != E; ++GI) - if (CalleeSM.global_count(*GI)) - computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap); - } else { - for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(), - E = CalleeSM.global_end(); GI != E; ++GI) - if (CallerSM.global_count(*GI)) - computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap); - } -} - -/// updateFromGlobalGraph - This function rematerializes global nodes and -/// nodes reachable from them from the globals graph into the current graph. -/// -void DSGraph::updateFromGlobalGraph() { - TIME_REGION(X, "updateFromGlobalGraph"); - ReachabilityCloner RC(*this, *GlobalsGraph, 0); - - // Clone the non-up-to-date global nodes into this graph. - for (DSScalarMap::global_iterator I = getScalarMap().global_begin(), - E = getScalarMap().global_end(); I != E; ++I) { - DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I); - if (It != GlobalsGraph->ScalarMap.end()) - RC.merge(getNodeForValue(*I), It->second); - } -} diff --git a/lib/Analysis/DataStructure/DataStructureAA.cpp b/lib/Analysis/DataStructure/DataStructureAA.cpp deleted file mode 100644 index 6e9f07bdd20..00000000000 --- a/lib/Analysis/DataStructure/DataStructureAA.cpp +++ /dev/null @@ -1,300 +0,0 @@ -//===- DataStructureAA.cpp - Data Structure Based Alias 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 pass uses the top-down data structure graphs to implement a simple -// context sensitive alias analysis. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Module.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -using namespace llvm; - -namespace { - class DSAA : public ModulePass, public AliasAnalysis { - TDDataStructures *TD; - BUDataStructures *BU; - - // These members are used to cache mod/ref information to make us return - // results faster, particularly for aa-eval. On the first request of - // mod/ref information for a particular call site, we compute and store the - // calculated nodemap for the call site. Any time DSA info is updated we - // free this information, and when we move onto a new call site, this - // information is also freed. - CallSite MapCS; - std::multimap CallerCalleeMap; - public: - DSAA() : TD(0) {} - ~DSAA() { - InvalidateCache(); - } - - void InvalidateCache() { - MapCS = CallSite(); - CallerCalleeMap.clear(); - } - - //------------------------------------------------ - // Implement the Pass API - // - - // run - Build up the result graph, representing the pointer graph for the - // program. - // - bool runOnModule(Module &M) { - InitializeAliasAnalysis(this); - TD = &getAnalysis(); - BU = &getAnalysis(); - return false; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.setPreservesAll(); // Does not transform code - AU.addRequiredTransitive(); // Uses TD Datastructures - AU.addRequiredTransitive(); // Uses BU Datastructures - } - - //------------------------------------------------ - // Implement the AliasAnalysis API - // - - AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); - - ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); - ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { - return AliasAnalysis::getModRefInfo(CS1,CS2); - } - - virtual void deleteValue(Value *V) { - InvalidateCache(); - BU->deleteValue(V); - TD->deleteValue(V); - } - - virtual void copyValue(Value *From, Value *To) { - if (From == To) return; - InvalidateCache(); - BU->copyValue(From, To); - TD->copyValue(From, To); - } - - private: - DSGraph *getGraphForValue(const Value *V); - }; - - // Register the pass... - RegisterPass X("ds-aa", "Data Structure Graph Based Alias Analysis"); - - // Register as an implementation of AliasAnalysis - RegisterAnalysisGroup Y(X); -} - -ModulePass *llvm::createDSAAPass() { return new DSAA(); } - -// getGraphForValue - Return the DSGraph to use for queries about the specified -// value... -// -DSGraph *DSAA::getGraphForValue(const Value *V) { - if (const Instruction *I = dyn_cast(V)) - return &TD->getDSGraph(*I->getParent()->getParent()); - else if (const Argument *A = dyn_cast(V)) - return &TD->getDSGraph(*A->getParent()); - else if (const BasicBlock *BB = dyn_cast(V)) - return &TD->getDSGraph(*BB->getParent()); - return 0; -} - -AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - if (V1 == V2) return MustAlias; - - DSGraph *G1 = getGraphForValue(V1); - DSGraph *G2 = getGraphForValue(V2); - assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?"); - - // Get the graph to use... - DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph())); - - const DSGraph::ScalarMapTy &GSM = G.getScalarMap(); - DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1); - if (I == GSM.end()) return NoAlias; - - DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2); - if (J == GSM.end()) return NoAlias; - - DSNode *N1 = I->second.getNode(), *N2 = J->second.getNode(); - unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); - if (N1 == 0 || N2 == 0) - // Can't tell whether anything aliases null. - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); - - // We can only make a judgment if one of the nodes is complete. - if (N1->isComplete() || N2->isComplete()) { - if (N1 != N2) - return NoAlias; // Completely different nodes. - - // See if they point to different offsets... if so, we may be able to - // determine that they do not alias... - if (O1 != O2) { - if (O2 < O1) { // Ensure that O1 <= O2 - std::swap(V1, V2); - std::swap(O1, O2); - std::swap(V1Size, V2Size); - } - - if (O1+V1Size <= O2) - return NoAlias; - } - } - - // FIXME: we could improve on this by checking the globals graph for aliased - // global queries... - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); -} - -/// getModRefInfo - does a callsite modify or reference a value? -/// -AliasAnalysis::ModRefResult -DSAA::getModRefInfo(CallSite CS, Value *P, unsigned Size) { - DSNode *N = 0; - // First step, check our cache. - if (CS.getInstruction() == MapCS.getInstruction()) { - { - const Function *Caller = CS.getInstruction()->getParent()->getParent(); - DSGraph &CallerTDGraph = TD->getDSGraph(*Caller); - - // Figure out which node in the TD graph this pointer corresponds to. - DSScalarMap &CallerSM = CallerTDGraph.getScalarMap(); - DSScalarMap::iterator NI = CallerSM.find(P); - if (NI == CallerSM.end()) { - InvalidateCache(); - return DSAA::getModRefInfo(CS, P, Size); - } - N = NI->second.getNode(); - } - - HaveMappingInfo: - assert(N && "Null pointer in scalar map??"); - - typedef std::multimap::iterator NodeMapIt; - std::pair Range = CallerCalleeMap.equal_range(N); - - // Loop over all of the nodes in the callee that correspond to "N", keeping - // track of aggregate mod/ref info. - bool NeverReads = true, NeverWrites = true; - for (; Range.first != Range.second; ++Range.first) { - if (Range.first->second->isModified()) - NeverWrites = false; - if (Range.first->second->isRead()) - NeverReads = false; - if (NeverReads == false && NeverWrites == false) - return AliasAnalysis::getModRefInfo(CS, P, Size); - } - - ModRefResult Result = ModRef; - if (NeverWrites) // We proved it was not modified. - Result = ModRefResult(Result & ~Mod); - if (NeverReads) // We proved it was not read. - Result = ModRefResult(Result & ~Ref); - - return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); - } - - // Any cached info we have is for the wrong function. - InvalidateCache(); - - Function *F = CS.getCalledFunction(); - - if (!F) return AliasAnalysis::getModRefInfo(CS, P, Size); - - if (F->isExternal()) { - // If we are calling an external function, and if this global doesn't escape - // the portion of the program we have analyzed, we can draw conclusions - // based on whether the global escapes the program. - Function *Caller = CS.getInstruction()->getParent()->getParent(); - DSGraph *G = &TD->getDSGraph(*Caller); - DSScalarMap::iterator NI = G->getScalarMap().find(P); - if (NI == G->getScalarMap().end()) { - // If it wasn't in the local function graph, check the global graph. This - // can occur for globals who are locally reference but hoisted out to the - // globals graph despite that. - G = G->getGlobalsGraph(); - NI = G->getScalarMap().find(P); - if (NI == G->getScalarMap().end()) - return AliasAnalysis::getModRefInfo(CS, P, Size); - } - - // If we found a node and it's complete, it cannot be passed out to the - // called function. - if (NI->second.getNode()->isComplete()) - return NoModRef; - return AliasAnalysis::getModRefInfo(CS, P, Size); - } - - // Get the graphs for the callee and caller. Note that we want the BU graph - // for the callee because we don't want all caller's effects incorporated! - const Function *Caller = CS.getInstruction()->getParent()->getParent(); - DSGraph &CallerTDGraph = TD->getDSGraph(*Caller); - DSGraph &CalleeBUGraph = BU->getDSGraph(*F); - - // Figure out which node in the TD graph this pointer corresponds to. - DSScalarMap &CallerSM = CallerTDGraph.getScalarMap(); - DSScalarMap::iterator NI = CallerSM.find(P); - if (NI == CallerSM.end()) { - ModRefResult Result = ModRef; - if (isa(P) || isa(P)) - return NoModRef; // null is never modified :) - else { - assert(isa(P) && - cast(P)->getType()->getElementType()->isFirstClassType() && - "This isn't a global that DSA inconsiderately dropped " - "from the graph?"); - - DSGraph &GG = *CallerTDGraph.getGlobalsGraph(); - DSScalarMap::iterator NI = GG.getScalarMap().find(P); - if (NI != GG.getScalarMap().end() && !NI->second.isNull()) { - // Otherwise, if the node is only M or R, return this. This can be - // useful for globals that should be marked const but are not. - DSNode *N = NI->second.getNode(); - if (!N->isModified()) - Result = (ModRefResult)(Result & ~Mod); - if (!N->isRead()) - Result = (ModRefResult)(Result & ~Ref); - } - } - - if (Result == NoModRef) return Result; - return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); - } - - // Compute the mapping from nodes in the callee graph to the nodes in the - // caller graph for this call site. - DSGraph::NodeMapTy CalleeCallerMap; - DSCallSite DSCS = CallerTDGraph.getDSCallSiteForCallSite(CS); - CallerTDGraph.computeCalleeCallerMapping(DSCS, *F, CalleeBUGraph, - CalleeCallerMap); - - // Remember the mapping and the call site for future queries. - MapCS = CS; - - // Invert the mapping into CalleeCallerInvMap. - for (DSGraph::NodeMapTy::iterator I = CalleeCallerMap.begin(), - E = CalleeCallerMap.end(); I != E; ++I) - CallerCalleeMap.insert(std::make_pair(I->second.getNode(), I->first)); - - N = NI->second.getNode(); - goto HaveMappingInfo; -} diff --git a/lib/Analysis/DataStructure/DataStructureOpt.cpp b/lib/Analysis/DataStructure/DataStructureOpt.cpp deleted file mode 100644 index 85da1763ac2..00000000000 --- a/lib/Analysis/DataStructure/DataStructureOpt.cpp +++ /dev/null @@ -1,102 +0,0 @@ -//===- DataStructureOpt.cpp - Data Structure Analysis Based Optimizations -===// -// -// 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 uses DSA to a series of simple optimizations, like marking -// unwritten global variables 'constant'. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Module.h" -#include "llvm/Constant.h" -#include "llvm/Type.h" -#include "llvm/ADT/Statistic.h" -using namespace llvm; - -namespace { - Statistic - NumGlobalsConstanted("ds-opt", "Number of globals marked constant"); - Statistic - NumGlobalsIsolated("ds-opt", "Number of globals with references dropped"); - - class DSOpt : public ModulePass { - TDDataStructures *TD; - public: - bool runOnModule(Module &M) { - TD = &getAnalysis(); - bool Changed = OptimizeGlobals(M); - return Changed; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); // Uses TD Datastructures - AU.addPreserved(); // Preserves local... - AU.addPreserved(); // Preserves bu... - AU.addPreserved(); // Preserves td... - } - - private: - bool OptimizeGlobals(Module &M); - }; - - RegisterPass X("ds-opt", "DSA-based simple optimizations"); -} - -ModulePass *llvm::createDSOptPass() { return new DSOpt(); } - -/// OptimizeGlobals - This method uses information taken from DSA to optimize -/// global variables. -/// -bool DSOpt::OptimizeGlobals(Module &M) { - DSGraph &GG = TD->getGlobalsGraph(); - const DSGraph::ScalarMapTy &SM = GG.getScalarMap(); - bool Changed = false; - - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) - if (!I->isExternal()) { // Loop over all of the non-external globals... - // Look up the node corresponding to this global, if it exists. - DSNode *GNode = 0; - DSGraph::ScalarMapTy::const_iterator SMI = SM.find(I); - if (SMI != SM.end()) GNode = SMI->second.getNode(); - - if (GNode == 0 && I->hasInternalLinkage()) { - // If there is no entry in the scalar map for this global, it was never - // referenced in the program. If it has internal linkage, that means we - // can delete it. We don't ACTUALLY want to delete the global, just - // remove anything that references the global: later passes will take - // care of nuking it. - if (!I->use_empty()) { - I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType())); - ++NumGlobalsIsolated; - } - } else if (GNode && GNode->isComplete()) { - - // If the node has not been read or written, and it is not externally - // visible, kill any references to it so it can be DCE'd. - if (!GNode->isModified() && !GNode->isRead() &&I->hasInternalLinkage()){ - if (!I->use_empty()) { - I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType())); - ++NumGlobalsIsolated; - } - } - - // We expect that there will almost always be a node for this global. - // If there is, and the node doesn't have the M bit set, we can set the - // 'constant' bit on the global. - if (!GNode->isModified() && !I->isConstant()) { - I->setConstant(true); - ++NumGlobalsConstanted; - Changed = true; - } - } - } - return Changed; -} diff --git a/lib/Analysis/DataStructure/DataStructureStats.cpp b/lib/Analysis/DataStructure/DataStructureStats.cpp deleted file mode 100644 index 1357a334eb1..00000000000 --- a/lib/Analysis/DataStructure/DataStructureStats.cpp +++ /dev/null @@ -1,150 +0,0 @@ -//===- DataStructureStats.cpp - Various statistics for DS Graphs ----------===// -// -// 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 defines a little pass that prints out statistics for DS Graphs. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/InstVisitor.h" -#include "llvm/Support/Streams.h" -#include "llvm/ADT/Statistic.h" -#include -using namespace llvm; - -namespace { - Statistic TotalNumCallees("totalcallees", - "Total number of callee functions at all indirect call sites"); - Statistic NumIndirectCalls("numindirect", - "Total number of indirect call sites in the program"); - Statistic NumPoolNodes("numpools", - "Number of allocation nodes that could be pool allocated"); - - // Typed/Untyped memory accesses: If DSA can infer that the types the loads - // and stores are accessing are correct (ie, the node has not been collapsed), - // increment the appropriate counter. - Statistic NumTypedMemAccesses("numtypedmemaccesses", - "Number of loads/stores which are fully typed"); - Statistic NumUntypedMemAccesses("numuntypedmemaccesses", - "Number of loads/stores which are untyped"); - - class DSGraphStats : public FunctionPass, public InstVisitor { - void countCallees(const Function &F); - const DSGraph *TDGraph; - - DSNode *getNodeForValue(Value *V); - bool isNodeForValueCollapsed(Value *V); - public: - /// Driver functions to compute the Load/Store Dep. Graph per function. - bool runOnFunction(Function& F); - - /// getAnalysisUsage - This modify nothing, and uses the Top-Down Graph. - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - } - - void visitLoad(LoadInst &LI); - void visitStore(StoreInst &SI); - - /// Debugging support methods - void print(std::ostream &O, const Module* = 0) const { } - }; - - static RegisterPass Z("dsstats", "DS Graph Statistics"); -} - -FunctionPass *llvm::createDataStructureStatsPass() { - return new DSGraphStats(); -} - - -static bool isIndirectCallee(Value *V) { - if (isa(V)) return false; - - if (CastInst *CI = dyn_cast(V)) - return isIndirectCallee(CI->getOperand(0)); - return true; -} - - -void DSGraphStats::countCallees(const Function& F) { - unsigned numIndirectCalls = 0, totalNumCallees = 0; - - for (DSGraph::fc_iterator I = TDGraph->fc_begin(), E = TDGraph->fc_end(); - I != E; ++I) - if (isIndirectCallee(I->getCallSite().getCalledValue())) { - // This is an indirect function call - std::vector Callees; - I->getCalleeNode()->addFullFunctionList(Callees); - - if (Callees.size() > 0) { - totalNumCallees += Callees.size(); - ++numIndirectCalls; - } else - cerr << "WARNING: No callee in Function '" << F.getName() - << "' at call: \n" - << *I->getCallSite().getInstruction(); - } - - TotalNumCallees += totalNumCallees; - NumIndirectCalls += numIndirectCalls; - - if (numIndirectCalls) - cout << " In function " << F.getName() << ": " - << (totalNumCallees / (double) numIndirectCalls) - << " average callees per indirect call\n"; -} - -DSNode *DSGraphStats::getNodeForValue(Value *V) { - const DSGraph *G = TDGraph; - if (isa(V)) - G = TDGraph->getGlobalsGraph(); - - const DSGraph::ScalarMapTy &ScalarMap = G->getScalarMap(); - DSGraph::ScalarMapTy::const_iterator I = ScalarMap.find(V); - if (I != ScalarMap.end()) - return I->second.getNode(); - return 0; -} - -bool DSGraphStats::isNodeForValueCollapsed(Value *V) { - if (DSNode *N = getNodeForValue(V)) - return N->isNodeCompletelyFolded() || N->isIncomplete(); - return false; -} - -void DSGraphStats::visitLoad(LoadInst &LI) { - if (isNodeForValueCollapsed(LI.getOperand(0))) { - NumUntypedMemAccesses++; - } else { - NumTypedMemAccesses++; - } -} - -void DSGraphStats::visitStore(StoreInst &SI) { - if (isNodeForValueCollapsed(SI.getOperand(1))) { - NumUntypedMemAccesses++; - } else { - NumTypedMemAccesses++; - } -} - - - -bool DSGraphStats::runOnFunction(Function& F) { - TDGraph = &getAnalysis().getDSGraph(F); - countCallees(F); - visit(F); - return true; -} diff --git a/lib/Analysis/DataStructure/EquivClassGraphs.cpp b/lib/Analysis/DataStructure/EquivClassGraphs.cpp deleted file mode 100644 index 2813b943ad2..00000000000 --- a/lib/Analysis/DataStructure/EquivClassGraphs.cpp +++ /dev/null @@ -1,477 +0,0 @@ -//===- 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 -// with functions partitioned into equivalence classes and a single merged -// DS graph for all functions in an equivalence class. After this merging, -// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "ECGraphs" -#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/Support/CallSite.h" -#include "llvm/Support/Debug.h" -#include "llvm/ADT/SCCIterator.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/EquivalenceClasses.h" -#include "llvm/ADT/STLExtras.h" -using namespace llvm; - -namespace { - RegisterPass X("eqdatastructure", - "Equivalence-class Bottom-up Data Structure Analysis"); - Statistic NumEquivBUInlines("equivdatastructures", - "Number of graphs inlined"); - Statistic NumFoldGraphInlines("Inline equiv-class graphs bottom up", - "Number of graphs inlined"); -} - -#ifndef NDEBUG -template -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; - 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?"); - DSGraph &DSG = getDSGraph(*thisFunc); - DSNode *calleeNode = DSG.getNodeForValue(CS.getCalledValue()).getNode(); - std::map::const_iterator I = - OneCalledFunction.find(calleeNode); - return (I == OneCalledFunction.end())? NULL : I->second; -} - -// runOnModule - Calculate the bottom up data structure graphs for each function -// in the program. -// -bool EquivClassGraphs::runOnModule(Module &M) { - CBU = &getAnalysis(); - GlobalECs = CBU->getGlobalECs(); - DEBUG(CheckAllGraphs(&M, *CBU)); - - GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs); - GlobalsGraph->setPrintAuxCalls(); - - ActualCallees = CBU->getActualCallees(); - - // Find equivalence classes of functions called from common call sites. - // Fold the CBU graphs for all functions in an equivalence class. - buildIndirectFunctionSets(M); - - // Stack of functions used for Tarjan's SCC-finding algorithm. - std::vector Stack; - std::map ValMap; - unsigned NextID = 1; - - Function *MainFunc = M.getMainFunction(); - if (MainFunc && !MainFunc->isExternal()) { - processSCC(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap); - } else { - 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); - - 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 && !MainFunc->isExternal()) { - DSGraph &MainGraph = getOrCreateGraph(*MainFunc); - const DSGraph &GG = *MainGraph.getGlobalsGraph(); - ReachabilityCloner RC(MainGraph, GG, - DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - - // Clone the global nodes into this graph. - for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), - E = GG.getScalarMap().global_end(); I != E; ++I) - if (isa(*I)) - RC.getClonedNH(GG.getNodeForValue(*I)); - - MainGraph.maskIncompleteMarkers(); - 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(*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; -} - - -// buildIndirectFunctionSets - Iterate over the module looking for indirect -// calls to functions. If a call site can invoke any functions [F1, F2... FN], -// unify the N functions together in the FuncECs set. -// -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. - Instruction *LastInst = 0; - Function *FirstFunc = 0; - for (ActualCalleesTy::const_iterator I=AC.begin(), E=AC.end(); I != E; ++I) { - if (I->second->isExternal()) - continue; // Ignore functions we cannot modify - - CallSite CS = CallSite::get(I->first); - - if (CS.getCalledFunction()) { // Direct call: - FuncECs.insert(I->second); // -- Make sure function has equiv class - FirstFunc = I->second; // -- First callee at this site - } else { // Else indirect call - // DOUT << "CALLEE: " << I->second->getName() - // << " from : " << I->first; - if (I->first != LastInst) { - // This is the first callee from this call site. - LastInst = I->first; - FirstFunc = I->second; - // Instead of storing the lastInst For Indirection call Sites we store - // the DSNode for the function ptr arguemnt - Function *thisFunc = LastInst->getParent()->getParent(); - DSGraph &TFG = CBU->getDSGraph(*thisFunc); - DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode(); - OneCalledFunction[calleeNode] = FirstFunc; - 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.unionSets(FirstFunc, I->second); -#ifndef NDEBUG - Function *thisFunc = LastInst->getParent()->getParent(); - DSGraph &TFG = CBU->getDSGraph(*thisFunc); - DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode(); - assert(OneCalledFunction.count(calleeNode) > 0 && "Missed a call?"); -#endif - } - } - - // Now include all functions that share a graph with any function in the - // 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); - 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. - // - DOUT << "\nIndirect Function Equivalence Sets:\n"; - for (EquivalenceClasses::iterator EQSI = FuncECs.begin(), E = - FuncECs.end(); EQSI != E; ++EQSI) { - if (!EQSI->isLeader()) continue; - - EquivalenceClasses::member_iterator SI = - FuncECs.member_begin(EQSI); - assert(SI != FuncECs.member_end() && "Empty equiv set??"); - EquivalenceClasses::member_iterator SN = SI; - ++SN; - if (SN == FuncECs.member_end()) - continue; // Single function equivalence set, no merging to do. - - Function* LF = *SI; - -#ifndef NDEBUG - DOUT <<" Equivalence set for leader " << LF->getName() <<" = "; - for (SN = SI; SN != FuncECs.member_end(); ++SN) - DOUT << " " << (*SN)->getName() << "," ; - DOUT << "\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 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 GraphsMerged; - GraphsMerged.insert(&CBU->getDSGraph(*LF)); - - for (++SI; SI != FuncECs.member_end(); ++SI) { - Function *F = *SI; - DSGraph &CBUGraph = CBU->getDSGraph(*F); - if (GraphsMerged.insert(&CBUGraph).second) { - // Record the "folded" graph for the function. - 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. - 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()); - } - } - DOUT << "\n"; -} - - -DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) { - // Has the graph already been created? - DSGraph *&Graph = DSInfo[&F]; - if (Graph) return *Graph; - - DSGraph &CBUGraph = CBU->getDSGraph(F); - - // Copy the CBU graph... - 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::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?"); - FG = Graph; - } - - return *Graph; -} - - -unsigned EquivClassGraphs:: -processSCC(DSGraph &FG, std::vector &Stack, unsigned &NextID, - std::map &ValMap) { - std::map::iterator It = ValMap.lower_bound(&FG); - if (It != ValMap.end() && It->first == &FG) - return It->second; - - DOUT << " ProcessSCC for function " << FG.getFunctionNames() << "\n"; - - unsigned Min = NextID++, MyID = Min; - ValMap[&FG] = Min; - Stack.push_back(&FG); - - // The edges out of the current node are the call site targets... - 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... - 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), - Stack, NextID, ValMap); - if (M < Min) Min = M; - } - } - - assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); - if (Min != MyID) - return Min; // This is part of a larger SCC! - - // If this is a new SCC, process it now. - bool MergedGraphs = false; - while (Stack.back() != &FG) { - DSGraph *NG = Stack.back(); - ValMap[NG] = ~0U; - - // If the SCC found is not the same as those found in CBU, make sure to - // merge the graphs as appropriate. - FG.cloneInto(*NG); - - // Update the DSInfo map and delete the old graph... - 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; - MergedGraphs = true; - Stack.pop_back(); - } - - // Clean up the graph before we start inlining a bunch again. - if (MergedGraphs) - FG.removeTriviallyDeadNodes(); - - Stack.pop_back(); - - processGraph(FG); - ValMap[&FG] = ~0U; - return MyID; -} - - -/// processGraph - Process the CBU graphs for the program in bottom-up order on -/// the SCC of the __ACTUAL__ call graph. This builds final folded CBU graphs. -void EquivClassGraphs::processGraph(DSGraph &G) { - DOUT << " ProcessGraph for function " << G.getFunctionNames() << "\n"; - - hash_set calls; - - // 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(), 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; - 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. - for (TNum = 0, Num = std::distance(I, E); I != E; ++I, ++TNum) - if (!I->second->isExternal()) - break; - - // 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::StripAllocaBit | - DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - DOUT << " Inlining graph [" << i << "/" - << G.getFunctionCalls().size()-1 - << ":" << TNum << "/" << Num-1 << "] for " - << CalleeFunc->getName() << "[" - << CalleeGraph->getGraphSize() << "+" - << CalleeGraph->getAuxFunctionCalls().size() - << "] into '" /*<< G.getFunctionNames()*/ << "' [" - << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() - << "]\n"; - } - } - -#ifndef NDEBUG - // Now loop over the rest of the callees and make sure they have the - // same graph as the one inlined above. - if (CalleeGraph) - for (++I, ++TNum; I != E; ++I, ++TNum) - if (!I->second->isExternal()) - assert(CalleeGraph == &getOrCreateGraph(*I->second) && - "Callees at a call site have different graphs?"); -#endif - } - - // Recompute the Incomplete markers. - 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); - - // When this graph is finalized, clone the globals in the graph into the - // globals graph to make sure it has everything, from all graphs. - ReachabilityCloner RC(*G.getGlobalsGraph(), G, DSGraph::StripAllocaBit); - - // Clone everything reachable from globals in the function graph into the - // globals graph. - DSScalarMap &MainSM = G.getScalarMap(); - for (DSScalarMap::global_iterator I = MainSM.global_begin(), - E = MainSM.global_end(); I != E; ++I) - RC.getClonedNH(MainSM[*I]); - - DOUT << " -- DONE ProcessGraph for function " << G.getFunctionNames() <<"\n"; -} diff --git a/lib/Analysis/DataStructure/GraphChecker.cpp b/lib/Analysis/DataStructure/GraphChecker.cpp deleted file mode 100644 index 8e4d3fce87d..00000000000 --- a/lib/Analysis/DataStructure/GraphChecker.cpp +++ /dev/null @@ -1,204 +0,0 @@ -//===- GraphChecker.cpp - Assert that various graph properties hold -------===// -// -// 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 used to test DSA with regression tests. It can be used to check -// that certain graph properties hold, such as two nodes being disjoint, whether -// or not a node is collapsed, etc. These are the command line arguments that -// it supports: -// -// --dsgc-dspass={local,bu,td} - Specify what flavor of graph to check -// --dsgc-abort-if-any-collapsed - Abort if any collapsed nodes are found -// --dsgc-abort-if-collapsed= - Abort if a node pointed to by an SSA -// value with name in is collapsed -// --dsgc-check-flags= - Abort if the specified nodes have flags -// that are not specified. -// --dsgc-abort-if-merged= - Abort if any of the named SSA values -// point to the same node. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Streams.h" -#include "llvm/Value.h" -#include -using namespace llvm; - -namespace { - enum DSPass { local, bu, td }; - cl::opt - DSPass("dsgc-dspass", cl::Hidden, - cl::desc("Specify which DSA pass the -datastructure-gc pass should use"), - cl::values(clEnumVal(local, "Local pass"), - clEnumVal(bu, "Bottom-up pass"), - clEnumVal(td, "Top-down pass"), - clEnumValEnd), cl::init(local)); - - cl::opt - AbortIfAnyCollapsed("dsgc-abort-if-any-collapsed", cl::Hidden, - cl::desc("Abort if any collapsed nodes are found")); - cl::list - AbortIfCollapsed("dsgc-abort-if-collapsed", cl::Hidden, cl::CommaSeparated, - cl::desc("Abort if any of the named symbols is collapsed")); - cl::list - CheckFlags("dsgc-check-flags", cl::Hidden, cl::CommaSeparated, - cl::desc("Check that flags are specified for nodes")); - cl::list - AbortIfMerged("dsgc-abort-if-merged", cl::Hidden, cl::CommaSeparated, - cl::desc("Abort if any of the named symbols are merged together")); - - struct DSGC : public FunctionPass { - DSGC(); - bool doFinalization(Module &M); - bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - switch (DSPass) { - case local: AU.addRequired(); break; - case bu: AU.addRequired(); break; - case td: AU.addRequired(); break; - } - AU.setPreservesAll(); - } - void print(std::ostream &O, const Module *M) const {} - - private: - void verify(const DSGraph &G); - }; - - RegisterPass X("datastructure-gc", "DSA Graph Checking Pass"); -} - -FunctionPass *llvm::createDataStructureGraphCheckerPass() { - return new DSGC(); -} - - -DSGC::DSGC() { - if (!AbortIfAnyCollapsed && AbortIfCollapsed.empty() && - CheckFlags.empty() && AbortIfMerged.empty()) { - cerr << "The -datastructure-gc is useless if you don't specify any" - << " -dsgc-* options. See the -help-hidden output for a list.\n"; - abort(); - } -} - - -/// doFinalization - Verify that the globals graph is in good shape... -/// -bool DSGC::doFinalization(Module &M) { - switch (DSPass) { - case local:verify(getAnalysis().getGlobalsGraph());break; - case bu: verify(getAnalysis().getGlobalsGraph()); break; - case td: verify(getAnalysis().getGlobalsGraph()); break; - } - return false; -} - -/// runOnFunction - Get the DSGraph for this function and verify that it is ok. -/// -bool DSGC::runOnFunction(Function &F) { - switch (DSPass) { - case local: verify(getAnalysis().getDSGraph(F)); break; - case bu: verify(getAnalysis().getDSGraph(F)); break; - case td: verify(getAnalysis().getDSGraph(F)); break; - } - - return false; -} - -/// verify - This is the function which checks to make sure that all of the -/// invariants established on the command line are true. -/// -void DSGC::verify(const DSGraph &G) { - // Loop over all of the nodes, checking to see if any are collapsed... - if (AbortIfAnyCollapsed) { - for (DSGraph::node_const_iterator I = G.node_begin(), E = G.node_end(); - I != E; ++I) - if (I->isNodeCompletelyFolded()) { - cerr << "Node is collapsed: "; - I->print(cerr, &G); - abort(); - } - } - - if (!AbortIfCollapsed.empty() || !CheckFlags.empty() || - !AbortIfMerged.empty()) { - // Convert from a list to a set, because we don't have cl::set's yet. FIXME - std::set AbortIfCollapsedS(AbortIfCollapsed.begin(), - AbortIfCollapsed.end()); - std::set AbortIfMergedS(AbortIfMerged.begin(), - AbortIfMerged.end()); - std::map CheckFlagsM; - - for (cl::list::iterator I = CheckFlags.begin(), - E = CheckFlags.end(); I != E; ++I) { - std::string::size_type ColonPos = I->rfind(':'); - if (ColonPos == std::string::npos) { - cerr << "Error: '" << *I - << "' is an invalid value for the --dsgc-check-flags option!\n"; - abort(); - } - - unsigned Flags = 0; - for (unsigned C = ColonPos+1; C != I->size(); ++C) - switch ((*I)[C]) { - case 'S': Flags |= DSNode::AllocaNode; break; - case 'H': Flags |= DSNode::HeapNode; break; - case 'G': Flags |= DSNode::GlobalNode; break; - case 'U': Flags |= DSNode::UnknownNode; break; - case 'I': Flags |= DSNode::Incomplete; break; - case 'M': Flags |= DSNode::Modified; break; - case 'R': Flags |= DSNode::Read; break; - case 'A': Flags |= DSNode::Array; break; - default: cerr << "Invalid DSNode flag!\n"; abort(); - } - CheckFlagsM[std::string(I->begin(), I->begin()+ColonPos)] = Flags; - } - - // Now we loop over all of the scalars, checking to see if any are collapsed - // that are not supposed to be, or if any are merged together. - const DSGraph::ScalarMapTy &SM = G.getScalarMap(); - std::map AbortIfMergedNodes; - - for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end(); - I != E; ++I) - if (I->first->hasName() && I->second.getNode()) { - const std::string &Name = I->first->getName(); - DSNode *N = I->second.getNode(); - - // Verify it is not collapsed if it is not supposed to be... - if (N->isNodeCompletelyFolded() && AbortIfCollapsedS.count(Name)) { - cerr << "Node for value '%" << Name << "' is collapsed: "; - N->print(cerr, &G); - abort(); - } - - if (CheckFlagsM.count(Name) && CheckFlagsM[Name] != N->getNodeFlags()) { - cerr << "Node flags are not as expected for node: " << Name - << " (" << CheckFlagsM[Name] << ":" <getNodeFlags() - << ")\n"; - N->print(cerr, &G); - abort(); - } - - // Verify that it is not merged if it is not supposed to be... - if (AbortIfMergedS.count(Name)) { - if (AbortIfMergedNodes.count(N)) { - cerr << "Nodes for values '%" << Name << "' and '%" - << AbortIfMergedNodes[N] << "' is merged: "; - N->print(cerr, &G); - abort(); - } - AbortIfMergedNodes[N] = Name; - } - } - } -} diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp deleted file mode 100644 index 66ca33d8765..00000000000 --- a/lib/Analysis/DataStructure/Local.cpp +++ /dev/null @@ -1,1333 +0,0 @@ -//===- Local.cpp - Compute a local data structure graph for a function ----===// -// -// 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. -// -//===----------------------------------------------------------------------===// -// -// Compute the local version of the data structure graph for a function. The -// external interface to this file is the DSGraph constructor. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Intrinsics.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" -#include "llvm/Support/InstVisitor.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Timer.h" - -// FIXME: This should eventually be a FunctionPass that is automatically -// aggregated into a Pass. -// -#include "llvm/Module.h" - -using namespace llvm; - -static RegisterPass -X("datastructure", "Local Data Structure Analysis"); - -static cl::opt -TrackIntegersAsPointers("dsa-track-integers", cl::Hidden, - cl::desc("If this is set, track integers as potential pointers")); - -static cl::opt -IgnoreSetCC("dsa-ignore-setcc", cl::Hidden, - cl::desc("If this is set, do nothing at pointer comparisons")); - -static cl::list -AllocList("dsa-alloc-list", - cl::value_desc("list"), - cl::desc("List of functions that allocate memory from the heap"), - cl::CommaSeparated, cl::Hidden); - -static cl::list -FreeList("dsa-free-list", - cl::value_desc("list"), - cl::desc("List of functions that free memory from the heap"), - cl::CommaSeparated, cl::Hidden); - -namespace llvm { -namespace DS { - // isPointerType - Return true if this type is big enough to hold a pointer. - bool isPointerType(const Type *Ty) { - if (isa(Ty)) - return true; - else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger()) - return Ty->getPrimitiveSize() >= PointerSize; - return false; - } -}} - -using namespace DS; - -namespace { - cl::opt - DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden, - cl::desc("Disable direct call optimization in " - "DSGraph construction")); - cl::opt - DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden, - cl::desc("Disable field sensitivity in DSGraphs")); - - //===--------------------------------------------------------------------===// - // GraphBuilder Class - //===--------------------------------------------------------------------===// - // - /// This class is the builder class that constructs the local data structure - /// graph by performing a single pass over the function in question. - /// - class GraphBuilder : InstVisitor { - DSGraph &G; - DSNodeHandle *RetNode; // Node that gets returned... - DSScalarMap &ScalarMap; - std::list *FunctionCalls; - - public: - GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode, - std::list &fc) - : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()), - FunctionCalls(&fc) { - - // Create scalar nodes for all pointer arguments... - for (Function::arg_iterator I = f.arg_begin(), E = f.arg_end(); - I != E; ++I) - if (isPointerType(I->getType())) - getValueDest(*I); - - visit(f); // Single pass over the function - } - - // GraphBuilder ctor for working on the globals graph - GraphBuilder(DSGraph &g) - : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) { - } - - void mergeInGlobalInitializer(GlobalVariable *GV); - - private: - // Visitor functions, used to handle each instruction type we encounter... - friend class InstVisitor; - void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); } - void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); } - void handleAlloc(AllocationInst &AI, bool isHeap); - - void visitPHINode(PHINode &PN); - void visitSelectInst(SelectInst &SI); - - void visitGetElementPtrInst(User &GEP); - void visitReturnInst(ReturnInst &RI); - void visitLoadInst(LoadInst &LI); - void visitStoreInst(StoreInst &SI); - void visitCallInst(CallInst &CI); - void visitInvokeInst(InvokeInst &II); - void visitSetCondInst(SetCondInst &SCI); - void visitFreeInst(FreeInst &FI); - void visitCastInst(CastInst &CI); - void visitInstruction(Instruction &I); - - bool visitIntrinsic(CallSite CS, Function* F); - bool visitExternal(CallSite CS, Function* F); - void visitCallSite(CallSite CS); - void visitVAArgInst(VAArgInst &I); - - void MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C); - private: - // Helper functions used to implement the visitation functions... - - /// createNode - Create a new DSNode, ensuring that it is properly added to - /// the graph. - /// - DSNode *createNode(const Type *Ty = 0) { - DSNode *N = new DSNode(Ty, &G); // Create the node - if (DisableFieldSensitivity) { - // Create node handle referring to the old node so that it is - // immediately removed from the graph when the node handle is destroyed. - DSNodeHandle OldNNH = N; - N->foldNodeCompletely(); - if (DSNode *FN = N->getForwardNode()) - N = FN; - } - return N; - } - - /// setDestTo - Set the ScalarMap entry for the specified value to point to - /// the specified destination. If the Value already points to a node, make - /// sure to merge the two destinations together. - /// - void setDestTo(Value &V, const DSNodeHandle &NH); - - /// getValueDest - Return the DSNode that the actual value points to. - /// - DSNodeHandle getValueDest(Value &V); - - /// getLink - This method is used to return the specified link in the - /// specified node if one exists. If a link does not already exist (it's - /// null), then we create a new node, link it, then return it. - /// - DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0); - }; -} - -using namespace DS; - -//===----------------------------------------------------------------------===// -// DSGraph constructor - Simply use the GraphBuilder to construct the local -// graph. -DSGraph::DSGraph(EquivalenceClasses &ECs, const TargetData &td, - Function &F, DSGraph *GG) - : GlobalsGraph(GG), ScalarMap(ECs), TD(td) { - PrintAuxCalls = false; - - DOUT << " [Loc] Calculating graph for: " << F.getName() << "\n"; - - // Use the graph builder to construct the local version of the graph - GraphBuilder B(F, *this, ReturnNodes[&F], FunctionCalls); -#ifndef NDEBUG - Timer::addPeakMemoryMeasurement(); -#endif - - // If there are any constant globals referenced in this function, merge their - // initializers into the local graph from the globals graph. - if (ScalarMap.global_begin() != ScalarMap.global_end()) { - ReachabilityCloner RC(*this, *GG, 0); - - for (DSScalarMap::global_iterator I = ScalarMap.global_begin(); - I != ScalarMap.global_end(); ++I) - if (GlobalVariable *GV = dyn_cast(*I)) - if (!GV->isExternal() && GV->isConstant()) - RC.merge(ScalarMap[GV], GG->ScalarMap[GV]); - } - - markIncompleteNodes(DSGraph::MarkFormalArgs); - - // Remove any nodes made dead due to merging... - removeDeadNodes(DSGraph::KeepUnreachableGlobals); -} - - -//===----------------------------------------------------------------------===// -// Helper method implementations... -// - -/// getValueDest - Return the DSNode that the actual value points to. -/// -DSNodeHandle GraphBuilder::getValueDest(Value &Val) { - Value *V = &Val; - if (isa(V) && cast(V)->isNullValue()) - return 0; // Null doesn't point to anything, don't add to ScalarMap! - - DSNodeHandle &NH = ScalarMap[V]; - if (!NH.isNull()) - return NH; // Already have a node? Just return it... - - // Otherwise we need to create a new node to point to. - // Check first for constant expressions that must be traversed to - // extract the actual value. - DSNode* N; - if (GlobalValue* GV = dyn_cast(V)) { - // Create a new global node for this global variable. - N = createNode(GV->getType()->getElementType()); - N->addGlobal(GV); - } else if (Constant *C = dyn_cast(V)) { - if (ConstantExpr *CE = dyn_cast(C)) { - if (CE->isCast()) { - if (isa(CE->getOperand(0)->getType())) - NH = getValueDest(*CE->getOperand(0)); - else - NH = createNode()->setUnknownNodeMarker(); - } else if (CE->getOpcode() == Instruction::GetElementPtr) { - visitGetElementPtrInst(*CE); - DSScalarMap::iterator I = ScalarMap.find(CE); - assert(I != ScalarMap.end() && "GEP didn't get processed right?"); - NH = I->second; - } else { - // This returns a conservative unknown node for any unhandled ConstExpr - return NH = createNode()->setUnknownNodeMarker(); - } - if (NH.isNull()) { // (getelementptr null, X) returns null - ScalarMap.erase(V); - return 0; - } - return NH; - } else if (isa(C)) { - ScalarMap.erase(V); - return 0; - } else { - assert(0 && "Unknown constant type!"); - } - N = createNode(); // just create a shadow node - } else { - // Otherwise just create a shadow node - N = createNode(); - } - - NH.setTo(N, 0); // Remember that we are pointing to it... - return NH; -} - - -/// getLink - This method is used to return the specified link in the -/// specified node if one exists. If a link does not already exist (it's -/// null), then we create a new node, link it, then return it. We must -/// specify the type of the Node field we are accessing so that we know what -/// type should be linked to if we need to create a new node. -/// -DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) { - DSNodeHandle &Node = const_cast(node); - DSNodeHandle &Link = Node.getLink(LinkNo); - if (Link.isNull()) { - // If the link hasn't been created yet, make and return a new shadow node - Link = createNode(); - } - return Link; -} - - -/// setDestTo - Set the ScalarMap entry for the specified value to point to the -/// specified destination. If the Value already points to a node, make sure to -/// merge the two destinations together. -/// -void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) { - ScalarMap[&V].mergeWith(NH); -} - - -//===----------------------------------------------------------------------===// -// Specific instruction type handler implementations... -// - -/// Alloca & Malloc instruction implementation - Simply create a new memory -/// object, pointing the scalar to it. -/// -void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) { - DSNode *N = createNode(); - if (isHeap) - N->setHeapNodeMarker(); - else - N->setAllocaNodeMarker(); - setDestTo(AI, N); -} - -// PHINode - Make the scalar for the PHI node point to all of the things the -// incoming values point to... which effectively causes them to be merged. -// -void GraphBuilder::visitPHINode(PHINode &PN) { - if (!isPointerType(PN.getType())) return; // Only pointer PHIs - - DSNodeHandle &PNDest = ScalarMap[&PN]; - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i))); -} - -void GraphBuilder::visitSelectInst(SelectInst &SI) { - if (!isPointerType(SI.getType())) return; // Only pointer Selects - - DSNodeHandle &Dest = ScalarMap[&SI]; - Dest.mergeWith(getValueDest(*SI.getOperand(1))); - Dest.mergeWith(getValueDest(*SI.getOperand(2))); -} - -void GraphBuilder::visitSetCondInst(SetCondInst &SCI) { - if (!isPointerType(SCI.getOperand(0)->getType()) || - isa(SCI.getOperand(1))) return; // Only pointers - if(!IgnoreSetCC) - ScalarMap[SCI.getOperand(0)].mergeWith(getValueDest(*SCI.getOperand(1))); -} - - -void GraphBuilder::visitGetElementPtrInst(User &GEP) { - DSNodeHandle Value = getValueDest(*GEP.getOperand(0)); - if (Value.isNull()) - Value = createNode(); - - // As a special case, if all of the index operands of GEP are constant zeros, - // handle this just like we handle casts (ie, don't do much). - bool AllZeros = true; - for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) - if (GEP.getOperand(i) != - Constant::getNullValue(GEP.getOperand(i)->getType())) { - AllZeros = false; - break; - } - - // If all of the indices are zero, the result points to the operand without - // applying the type. - if (AllZeros || (!Value.isNull() && - Value.getNode()->isNodeCompletelyFolded())) { - setDestTo(GEP, Value); - return; - } - - - const PointerType *PTy = cast(GEP.getOperand(0)->getType()); - const Type *CurTy = PTy->getElementType(); - - if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) { - // If the node had to be folded... exit quickly - setDestTo(GEP, Value); // GEP result points to folded node - return; - } - - const TargetData &TD = Value.getNode()->getTargetData(); - -#if 0 - // Handle the pointer index specially... - if (GEP.getNumOperands() > 1 && - (!isa(GEP.getOperand(1)) || - !cast(GEP.getOperand(1))->isNullValue())) { - - // If we already know this is an array being accessed, don't do anything... - if (!TopTypeRec.isArray) { - TopTypeRec.isArray = true; - - // If we are treating some inner field pointer as an array, fold the node - // up because we cannot handle it right. This can come because of - // something like this: &((&Pt->X)[1]) == &Pt->Y - // - if (Value.getOffset()) { - // Value is now the pointer we want to GEP to be... - Value.getNode()->foldNodeCompletely(); - setDestTo(GEP, Value); // GEP result points to folded node - return; - } else { - // This is a pointer to the first byte of the node. Make sure that we - // are pointing to the outter most type in the node. - // FIXME: We need to check one more case here... - } - } - } -#endif - - // All of these subscripts are indexing INTO the elements we have... - unsigned Offset = 0; - for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP); - I != E; ++I) - if (const StructType *STy = dyn_cast(*I)) { - const ConstantInt* CUI = cast(I.getOperand()); - unsigned FieldNo = - CUI->getType()->isSigned() ? CUI->getSExtValue() : CUI->getZExtValue(); - Offset += (unsigned)TD.getStructLayout(STy)->MemberOffsets[FieldNo]; - } else if (isa(*I)) { - if (!isa(I.getOperand()) || - !cast(I.getOperand())->isNullValue()) - Value.getNode()->setArrayMarker(); - } - - -#if 0 - if (const SequentialType *STy = cast(*I)) { - CurTy = STy->getElementType(); - if (ConstantInt *CS = dyn_cast(GEP.getOperand(i))) { - Offset += - (CS->getType()->isSigned() ? CS->getSExtValue() : CS->getZExtValue()) - * TD.getTypeSize(CurTy); - } else { - // Variable index into a node. We must merge all of the elements of the - // sequential type here. - if (isa(STy)) - cerr << "Pointer indexing not handled yet!\n"; - else { - const ArrayType *ATy = cast(STy); - unsigned ElSize = TD.getTypeSize(CurTy); - DSNode *N = Value.getNode(); - assert(N && "Value must have a node!"); - unsigned RawOffset = Offset+Value.getOffset(); - - // Loop over all of the elements of the array, merging them into the - // zeroth element. - for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i) - // Merge all of the byte components of this array element - for (unsigned j = 0; j != ElSize; ++j) - N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j); - } - } - } -#endif - - // Add in the offset calculated... - Value.setOffset(Value.getOffset()+Offset); - - // Check the offset - DSNode *N = Value.getNode(); - if (N && - !N->isNodeCompletelyFolded() && - (N->getSize() != 0 || Offset != 0) && - !N->isForwarding()) { - if ((Offset >= N->getSize()) || int(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 - - // Collapse the node since its size is now variable - N->foldNodeCompletely(); - } - } - - // Value is now the pointer we want to GEP to be... - setDestTo(GEP, Value); -} - -void GraphBuilder::visitLoadInst(LoadInst &LI) { - DSNodeHandle Ptr = getValueDest(*LI.getOperand(0)); - if (Ptr.isNull()) - Ptr = createNode(); - - // Make that the node is read from... - Ptr.getNode()->setReadMarker(); - - // Ensure a typerecord exists... - Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false); - - if (isPointerType(LI.getType())) - setDestTo(LI, getLink(Ptr)); -} - -void GraphBuilder::visitStoreInst(StoreInst &SI) { - const Type *StoredTy = SI.getOperand(0)->getType(); - DSNodeHandle Dest = getValueDest(*SI.getOperand(1)); - if (Dest.isNull()) return; - - // Mark that the node is written to... - Dest.getNode()->setModifiedMarker(); - - // Ensure a type-record exists... - Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset()); - - // Avoid adding edges from null, or processing non-"pointer" stores - if (isPointerType(StoredTy)) - Dest.addEdgeTo(getValueDest(*SI.getOperand(0))); -} - -void GraphBuilder::visitReturnInst(ReturnInst &RI) { - if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType())) - RetNode->mergeWith(getValueDest(*RI.getOperand(0))); -} - -void GraphBuilder::visitVAArgInst(VAArgInst &I) { - //FIXME: also updates the argument - DSNodeHandle Ptr = getValueDest(*I.getOperand(0)); - if (Ptr.isNull()) return; - - // Make that the node is read from. - Ptr.getNode()->setReadMarker(); - - // Ensure a type record exists. - DSNode *PtrN = Ptr.getNode(); - PtrN->mergeTypeInfo(I.getType(), Ptr.getOffset(), false); - - if (isPointerType(I.getType())) - setDestTo(I, getLink(Ptr)); -} - - -void GraphBuilder::visitCallInst(CallInst &CI) { - visitCallSite(&CI); -} - -void GraphBuilder::visitInvokeInst(InvokeInst &II) { - visitCallSite(&II); -} - -/// returns true if the intrinsic is handled -bool GraphBuilder::visitIntrinsic(CallSite CS, Function *F) { - switch (F->getIntrinsicID()) { - case Intrinsic::vastart: - getValueDest(*CS.getInstruction()).getNode()->setAllocaNodeMarker(); - return true; - case Intrinsic::vacopy: - getValueDest(*CS.getInstruction()). - mergeWith(getValueDest(**(CS.arg_begin()))); - return true; - case Intrinsic::vaend: - case Intrinsic::dbg_func_start: - case Intrinsic::dbg_region_end: - case Intrinsic::dbg_stoppoint: - return true; // noop - case Intrinsic::memcpy_i32: - case Intrinsic::memcpy_i64: - case Intrinsic::memmove_i32: - case Intrinsic::memmove_i64: { - // Merge the first & second arguments, and mark the memory read and - // modified. - DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); - RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); - if (DSNode *N = RetNH.getNode()) - N->setModifiedMarker()->setReadMarker(); - return true; - } - case Intrinsic::memset_i32: - case Intrinsic::memset_i64: - // Mark the memory modified. - if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) - N->setModifiedMarker(); - return true; - default: - DOUT << "[dsa:local] Unhandled intrinsic: " << F->getName() << "\n"; - return false; - } -} - -/// returns true if the external is a recognized libc function with a -/// known (and generated) graph -bool GraphBuilder::visitExternal(CallSite CS, Function *F) { - if (F->getName() == "calloc" - || F->getName() == "posix_memalign" - || F->getName() == "memalign" || F->getName() == "valloc") { - setDestTo(*CS.getInstruction(), - createNode()->setHeapNodeMarker()->setModifiedMarker()); - return true; - } else if (F->getName() == "realloc") { - DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); - if (CS.arg_begin() != CS.arg_end()) - RetNH.mergeWith(getValueDest(**CS.arg_begin())); - if (DSNode *N = RetNH.getNode()) - N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); - return true; - } else if (F->getName() == "memmove") { - // Merge the first & second arguments, and mark the memory read and - // modified. - DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); - RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); - if (DSNode *N = RetNH.getNode()) - N->setModifiedMarker()->setReadMarker(); - return true; - } else if (F->getName() == "free") { - // Mark that the node is written to... - if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) - N->setModifiedMarker()->setHeapNodeMarker(); - } else if (F->getName() == "atoi" || F->getName() == "atof" || - F->getName() == "atol" || F->getName() == "atoll" || - F->getName() == "remove" || F->getName() == "unlink" || - F->getName() == "rename" || F->getName() == "memcmp" || - F->getName() == "strcmp" || F->getName() == "strncmp" || - F->getName() == "execl" || F->getName() == "execlp" || - F->getName() == "execle" || F->getName() == "execv" || - F->getName() == "execvp" || F->getName() == "chmod" || - F->getName() == "puts" || F->getName() == "write" || - F->getName() == "open" || F->getName() == "create" || - F->getName() == "truncate" || F->getName() == "chdir" || - F->getName() == "mkdir" || F->getName() == "rmdir" || - F->getName() == "strlen") { - // These functions read all of their pointer operands. - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) { - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - } - return true; - } else if (F->getName() == "memchr") { - DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); - DSNodeHandle Result = getValueDest(*CS.getInstruction()); - RetNH.mergeWith(Result); - if (DSNode *N = RetNH.getNode()) - N->setReadMarker(); - return true; - } else if (F->getName() == "read" || F->getName() == "pipe" || - F->getName() == "wait" || F->getName() == "time" || - F->getName() == "getrusage") { - // These functions write all of their pointer operands. - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) { - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setModifiedMarker(); - } - return true; - } else if (F->getName() == "stat" || F->getName() == "fstat" || - F->getName() == "lstat") { - // These functions read their first operand if its a pointer. - CallSite::arg_iterator AI = CS.arg_begin(); - if (isPointerType((*AI)->getType())) { - DSNodeHandle Path = getValueDest(**AI); - if (DSNode *N = Path.getNode()) N->setReadMarker(); - } - - // Then they write into the stat buffer. - DSNodeHandle StatBuf = getValueDest(**++AI); - if (DSNode *N = StatBuf.getNode()) { - N->setModifiedMarker(); - const Type *StatTy = F->getFunctionType()->getParamType(1); - if (const PointerType *PTy = dyn_cast(StatTy)) - N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset()); - } - return true; - } else if (F->getName() == "strtod" || F->getName() == "strtof" || - F->getName() == "strtold") { - // These functions read the first pointer - if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) { - Str->setReadMarker(); - // If the second parameter is passed, it will point to the first - // argument node. - const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1)); - if (DSNode *End = EndPtrNH.getNode()) { - End->mergeTypeInfo(PointerType::get(Type::SByteTy), - EndPtrNH.getOffset(), false); - End->setModifiedMarker(); - DSNodeHandle &Link = getLink(EndPtrNH); - Link.mergeWith(getValueDest(**CS.arg_begin())); - } - } - return true; - } else if (F->getName() == "fopen" || F->getName() == "fdopen" || - F->getName() == "freopen") { - // These functions read all of their pointer operands. - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - - // fopen allocates in an unknown way and writes to the file - // descriptor. Also, merge the allocated type into the node. - DSNodeHandle Result = getValueDest(*CS.getInstruction()); - if (DSNode *N = Result.getNode()) { - N->setModifiedMarker()->setUnknownNodeMarker(); - const Type *RetTy = F->getFunctionType()->getReturnType(); - if (const PointerType *PTy = dyn_cast(RetTy)) - N->mergeTypeInfo(PTy->getElementType(), Result.getOffset()); - } - - // If this is freopen, merge the file descriptor passed in with the - // result. - if (F->getName() == "freopen") { - // ICC doesn't handle getting the iterator, decrementing and - // dereferencing it in one operation without error. Do it in 2 steps - CallSite::arg_iterator compit = CS.arg_end(); - Result.mergeWith(getValueDest(**--compit)); - } - return true; - } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){ - // fclose reads and deallocates the memory in an unknown way for the - // file descriptor. It merges the FILE type into the descriptor. - DSNodeHandle H = getValueDest(**CS.arg_begin()); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setUnknownNodeMarker(); - const Type *ArgTy = F->getFunctionType()->getParamType(0); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - return true; - } else if (CS.arg_end()-CS.arg_begin() == 1 && - (F->getName() == "fflush" || F->getName() == "feof" || - F->getName() == "fileno" || F->getName() == "clearerr" || - F->getName() == "rewind" || F->getName() == "ftell" || - F->getName() == "ferror" || F->getName() == "fgetc" || - F->getName() == "fgetc" || F->getName() == "_IO_getc")) { - // fflush reads and writes the memory for the file descriptor. It - // merges the FILE type into the descriptor. - DSNodeHandle H = getValueDest(**CS.arg_begin()); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setModifiedMarker(); - - const Type *ArgTy = F->getFunctionType()->getParamType(0); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - return true; - } else if (CS.arg_end()-CS.arg_begin() == 4 && - (F->getName() == "fwrite" || F->getName() == "fread")) { - // fread writes the first operand, fwrite reads it. They both - // read/write the FILE descriptor, and merges the FILE type. - CallSite::arg_iterator compit = CS.arg_end(); - DSNodeHandle H = getValueDest(**--compit); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setModifiedMarker(); - const Type *ArgTy = F->getFunctionType()->getParamType(3); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - - H = getValueDest(**CS.arg_begin()); - if (DSNode *N = H.getNode()) - if (F->getName() == "fwrite") - N->setReadMarker(); - else - N->setModifiedMarker(); - return true; - } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){ - // fgets reads and writes the memory for the file descriptor. It - // merges the FILE type into the descriptor, and writes to the - // argument. It returns the argument as well. - CallSite::arg_iterator AI = CS.arg_begin(); - DSNodeHandle H = getValueDest(**AI); - if (DSNode *N = H.getNode()) - N->setModifiedMarker(); // Writes buffer - H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer - ++AI; ++AI; - - // Reads and writes file descriptor, merge in FILE type. - H = getValueDest(**AI); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setModifiedMarker(); - const Type *ArgTy = F->getFunctionType()->getParamType(2); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - return true; - } else if (F->getName() == "ungetc" || F->getName() == "fputc" || - F->getName() == "fputs" || F->getName() == "putc" || - F->getName() == "ftell" || F->getName() == "rewind" || - F->getName() == "_IO_putc") { - // These functions read and write the memory for the file descriptor, - // which is passes as the last argument. - CallSite::arg_iterator compit = CS.arg_end(); - DSNodeHandle H = getValueDest(**--compit); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setModifiedMarker(); - FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); - const Type *ArgTy = *--compit2; - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - - // Any pointer arguments are read. - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - return true; - } else if (F->getName() == "fseek" || F->getName() == "fgetpos" || - F->getName() == "fsetpos") { - // These functions read and write the memory for the file descriptor, - // and read/write all other arguments. - DSNodeHandle H = getValueDest(**CS.arg_begin()); - if (DSNode *N = H.getNode()) { - FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); - const Type *ArgTy = *--compit2; - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - - // Any pointer arguments are read. - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker()->setModifiedMarker(); - return true; - } else if (F->getName() == "printf" || F->getName() == "fprintf" || - F->getName() == "sprintf") { - CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - - if (F->getName() == "fprintf") { - // fprintf reads and writes the FILE argument, and applies the type - // to it. - DSNodeHandle H = getValueDest(**AI); - if (DSNode *N = H.getNode()) { - N->setModifiedMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - } else if (F->getName() == "sprintf") { - // sprintf writes the first string argument. - DSNodeHandle H = getValueDest(**AI++); - if (DSNode *N = H.getNode()) { - N->setModifiedMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - } - - for (; AI != E; ++AI) { - // printf reads all pointer arguments. - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - } - return true; - } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" || - F->getName() == "vsprintf") { - CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - - if (F->getName() == "vfprintf") { - // ffprintf reads and writes the FILE argument, and applies the type - // to it. - DSNodeHandle H = getValueDest(**AI); - if (DSNode *N = H.getNode()) { - N->setModifiedMarker()->setReadMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - ++AI; - } else if (F->getName() == "vsprintf") { - // vsprintf writes the first string argument. - DSNodeHandle H = getValueDest(**AI++); - if (DSNode *N = H.getNode()) { - N->setModifiedMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - } - - // Read the format - if (AI != E) { - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - ++AI; - } - - // Read the valist, and the pointed-to objects. - if (AI != E && isPointerType((*AI)->getType())) { - const DSNodeHandle &VAList = getValueDest(**AI); - if (DSNode *N = VAList.getNode()) { - N->setReadMarker(); - N->mergeTypeInfo(PointerType::get(Type::SByteTy), - VAList.getOffset(), false); - - DSNodeHandle &VAListObjs = getLink(VAList); - VAListObjs.getNode()->setReadMarker(); - } - } - - return true; - } else if (F->getName() == "scanf" || F->getName() == "fscanf" || - F->getName() == "sscanf") { - CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - - if (F->getName() == "fscanf") { - // fscanf reads and writes the FILE argument, and applies the type - // to it. - DSNodeHandle H = getValueDest(**AI); - if (DSNode *N = H.getNode()) { - N->setReadMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - } else if (F->getName() == "sscanf") { - // sscanf reads the first string argument. - DSNodeHandle H = getValueDest(**AI++); - if (DSNode *N = H.getNode()) { - N->setReadMarker(); - const Type *ArgTy = (*AI)->getType(); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - } - - for (; AI != E; ++AI) { - // scanf writes all pointer arguments. - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setModifiedMarker(); - } - return true; - } else if (F->getName() == "strtok") { - // strtok reads and writes the first argument, returning it. It reads - // its second arg. FIXME: strtok also modifies some hidden static - // data. Someday this might matter. - CallSite::arg_iterator AI = CS.arg_begin(); - DSNodeHandle H = getValueDest(**AI++); - if (DSNode *N = H.getNode()) { - N->setReadMarker()->setModifiedMarker(); // Reads/Writes buffer - const Type *ArgTy = F->getFunctionType()->getParamType(0); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer - - H = getValueDest(**AI); // Reads delimiter - if (DSNode *N = H.getNode()) { - N->setReadMarker(); - const Type *ArgTy = F->getFunctionType()->getParamType(1); - if (const PointerType *PTy = dyn_cast(ArgTy)) - N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); - } - return true; - } else if (F->getName() == "strchr" || F->getName() == "strrchr" || - F->getName() == "strstr") { - // These read their arguments, and return the first one - DSNodeHandle H = getValueDest(**CS.arg_begin()); - H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer - - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - - if (DSNode *N = H.getNode()) - N->setReadMarker(); - return true; - } else if (F->getName() == "__assert_fail") { - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) - if (isPointerType((*AI)->getType())) - if (DSNode *N = getValueDest(**AI).getNode()) - N->setReadMarker(); - return true; - } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) { - // This writes its second argument, and forces it to double. - CallSite::arg_iterator compit = CS.arg_end(); - DSNodeHandle H = getValueDest(**--compit); - if (DSNode *N = H.getNode()) { - N->setModifiedMarker(); - N->mergeTypeInfo(Type::DoubleTy, H.getOffset()); - } - return true; - } else if (F->getName() == "strcat" || F->getName() == "strncat") { - //This might be making unsafe assumptions about usage - //Merge return and first arg - DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); - RetNH.mergeWith(getValueDest(**CS.arg_begin())); - if (DSNode *N = RetNH.getNode()) - N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); - //and read second pointer - if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) - N->setReadMarker(); - return true; - } else if (F->getName() == "strcpy" || F->getName() == "strncpy") { - //This might be making unsafe assumptions about usage - //Merge return and first arg - DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); - RetNH.mergeWith(getValueDest(**CS.arg_begin())); - if (DSNode *N = RetNH.getNode()) - N->setHeapNodeMarker()->setModifiedMarker(); - //and read second pointer - if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) - N->setReadMarker(); - return true; - } - return false; -} - -void GraphBuilder::visitCallSite(CallSite CS) { - Value *Callee = CS.getCalledValue(); - - // Special case handling of certain libc allocation functions here. - if (Function *F = dyn_cast(Callee)) - if (F->isExternal()) - if (F->isIntrinsic() && visitIntrinsic(CS, F)) - return; - else { - // Determine if the called function is one of the specified heap - // allocation functions - if (AllocList.end() != std::find(AllocList.begin(), AllocList.end(), F->getName())) { - setDestTo(*CS.getInstruction(), - createNode()->setHeapNodeMarker()->setModifiedMarker()); - return; - } - - // Determine if the called function is one of the specified heap - // free functions - if (FreeList.end() != std::find(FreeList.begin(), FreeList.end(), F->getName())) { - // Mark that the node is written to... - if (DSNode *N = getValueDest(*(CS.getArgument(0))).getNode()) - N->setModifiedMarker()->setHeapNodeMarker(); - return; - } - if (visitExternal(CS,F)) - return; - // Unknown function, warn if it returns a pointer type or takes a - // pointer argument. - bool Warn = isPointerType(CS.getInstruction()->getType()); - if (!Warn) - for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); - I != E; ++I) - if (isPointerType((*I)->getType())) { - Warn = true; - break; - } - if (Warn) { - DOUT << "WARNING: Call to unknown external function '" - << F->getName() << "' will cause pessimistic results!\n"; - } - } - - // Set up the return value... - DSNodeHandle RetVal; - Instruction *I = CS.getInstruction(); - if (isPointerType(I->getType())) - RetVal = getValueDest(*I); - - DSNode *CalleeNode = 0; - if (DisableDirectCallOpt || !isa(Callee)) { - CalleeNode = getValueDest(*Callee).getNode(); - if (CalleeNode == 0) { - cerr << "WARNING: Program is calling through a null pointer?\n"<< *I; - return; // Calling a null pointer? - } - } - - std::vector Args; - Args.reserve(CS.arg_end()-CS.arg_begin()); - - // Calculate the arguments vector... - for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) - if (isPointerType((*I)->getType())) - Args.push_back(getValueDest(**I)); - - // Add a new function call entry... - if (CalleeNode) - FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args)); - else - FunctionCalls->push_back(DSCallSite(CS, RetVal, cast(Callee), - Args)); -} - -void GraphBuilder::visitFreeInst(FreeInst &FI) { - // Mark that the node is written to... - if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode()) - N->setModifiedMarker()->setHeapNodeMarker(); -} - -/// Handle casts... -void GraphBuilder::visitCastInst(CastInst &CI) { - // Pointers can only be cast with BitCast so check that the instruction - // is a BitConvert. If not, its guaranteed not to involve any pointers so - // we don't do anything. - switch (CI.getOpcode()) { - default: break; - case Instruction::BitCast: - case Instruction::IntToPtr: - if (isPointerType(CI.getType())) - if (isPointerType(CI.getOperand(0)->getType())) { - DSNodeHandle Ptr = getValueDest(*CI.getOperand(0)); - if (Ptr.getNode() == 0) return; - // Cast one pointer to the other, just act like a copy instruction - setDestTo(CI, Ptr); - } else { - // Cast something (floating point, small integer) to a pointer. We - // need to track the fact that the node points to SOMETHING, just - // something we don't know about. Make an "Unknown" node. - setDestTo(CI, createNode()->setUnknownNodeMarker()); - } - break; - } -} - - -// visitInstruction - For all other instruction types, if we have any arguments -// that are of pointer type, make them have unknown composition bits, and merge -// the nodes together. -void GraphBuilder::visitInstruction(Instruction &Inst) { - DSNodeHandle CurNode; - if (isPointerType(Inst.getType())) - CurNode = getValueDest(Inst); - for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I) - if (isPointerType((*I)->getType())) - CurNode.mergeWith(getValueDest(**I)); - - if (DSNode *N = CurNode.getNode()) - N->setUnknownNodeMarker(); -} - - - -//===----------------------------------------------------------------------===// -// LocalDataStructures Implementation -//===----------------------------------------------------------------------===// - -// MergeConstantInitIntoNode - Merge the specified constant into the node -// pointed to by NH. -void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) { - // Ensure a type-record exists... - DSNode *NHN = NH.getNode(); - NHN->mergeTypeInfo(C->getType(), NH.getOffset()); - - if (C->getType()->isFirstClassType()) { - if (isPointerType(C->getType())) - // Avoid adding edges from null, or processing non-"pointer" stores - NH.addEdgeTo(getValueDest(*C)); - return; - } - - const TargetData &TD = NH.getNode()->getTargetData(); - - if (ConstantArray *CA = dyn_cast(C)) { - for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) - // We don't currently do any indexing for arrays... - MergeConstantInitIntoNode(NH, cast(CA->getOperand(i))); - } else if (ConstantStruct *CS = dyn_cast(C)) { - const StructLayout *SL = TD.getStructLayout(CS->getType()); - for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { - DSNode *NHN = NH.getNode(); - //Some programmers think ending a structure with a [0 x sbyte] is cute - if (SL->MemberOffsets[i] < SL->StructSize) { - DSNodeHandle NewNH(NHN, NH.getOffset()+(unsigned)SL->MemberOffsets[i]); - MergeConstantInitIntoNode(NewNH, cast(CS->getOperand(i))); - } else if (SL->MemberOffsets[i] == SL->StructSize) { - DOUT << "Zero size element at end of struct\n"; - NHN->foldNodeCompletely(); - } else { - assert(0 && "type was smaller than offsets of of struct layout indicate"); - } - } - } else if (isa(C) || isa(C)) { - // Noop - } else { - assert(0 && "Unknown constant type!"); - } -} - -void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) { - assert(!GV->isExternal() && "Cannot merge in external global!"); - // Get a node handle to the global node and merge the initializer into it. - DSNodeHandle NH = getValueDest(*GV); - MergeConstantInitIntoNode(NH, GV->getInitializer()); -} - - -/// 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. -static void BuildGlobalECs(DSGraph &GG, std::set &ECGlobals) { - DSScalarMap &SM = GG.getScalarMap(); - EquivalenceClasses &GlobalECs = SM.getGlobalECs(); - for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); - I != E; ++I) { - if (I->getGlobalsList().size() <= 1) continue; - - // First, build up the equivalence set for this block of globals. - const std::vector &GVs = I->getGlobalsList(); - GlobalValue *First = GVs[0]; - for (unsigned i = 1, e = GVs.size(); i != e; ++i) - GlobalECs.unionSets(First, GVs[i]); - - // Next, get the leader element. - assert(First == GlobalECs.getLeaderValue(First) && - "First did not end up being the leader?"); - - // Next, remove all globals from the scalar map that are not the leader. - assert(GVs[0] == First && "First had to be at the front!"); - for (unsigned i = 1, e = GVs.size(); i != e; ++i) { - ECGlobals.insert(GVs[i]); - SM.erase(SM.find(GVs[i])); - } - - // Finally, change the global node to only contain the leader. - I->clearGlobals(); - I->addGlobal(First); - } - - DEBUG(GG.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. -static void EliminateUsesOfECGlobals(DSGraph &G, - const std::set &ECGlobals) { - DSScalarMap &SM = G.getScalarMap(); - EquivalenceClasses &GlobalECs = SM.getGlobalECs(); - - bool MadeChange = false; - for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); - GI != E; ) { - GlobalValue *GV = *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. - 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); - MadeChange = true; - } - - DEBUG(if(MadeChange) G.AssertGraphOK()); -} - -bool LocalDataStructures::runOnModule(Module &M) { - const TargetData &TD = getAnalysis(); - - // First step, build the globals graph. - GlobalsGraph = new DSGraph(GlobalECs, TD); - { - GraphBuilder GGB(*GlobalsGraph); - - // Add initializers for all of the globals to the globals graph. - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) - if (!I->isExternal()) - GGB.mergeInGlobalInitializer(I); - } - - // Next step, iterate through the nodes in the globals graph, unioning - // together the globals into equivalence classes. - std::set ECGlobals; - BuildGlobalECs(*GlobalsGraph, ECGlobals); - DOUT << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; - ECGlobals.clear(); - - // Calculate all of the graphs... - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal()) - DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I, - GlobalsGraph))); - - GlobalsGraph->removeTriviallyDeadNodes(); - GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs); - - // Now that we've computed all of the graphs, and merged all of the info into - // the globals graph, see if we have further constrained the globals in the - // program if so, update GlobalECs and remove the extraneous globals from the - // program. - BuildGlobalECs(*GlobalsGraph, ECGlobals); - if (!ECGlobals.empty()) { - DOUT << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; - for (hash_map::iterator I = DSInfo.begin(), - E = DSInfo.end(); I != E; ++I) - EliminateUsesOfECGlobals(*I->second, ECGlobals); - } - - return false; -} - -// releaseMemory - If the pass pipeline is done with this pass, we can release -// our memory... here... -// -void LocalDataStructures::releaseMemory() { - for (hash_map::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; -} - diff --git a/lib/Analysis/DataStructure/Makefile b/lib/Analysis/DataStructure/Makefile deleted file mode 100644 index 0f1986fe74d..00000000000 --- a/lib/Analysis/DataStructure/Makefile +++ /dev/null @@ -1,14 +0,0 @@ -##===- lib/Analysis/DataStructure/Makefile -----------------*- Makefile -*-===## -# -# 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. -# -##===----------------------------------------------------------------------===## - -LEVEL = ../../.. -LIBRARYNAME = LLVMDataStructure - -include $(LEVEL)/Makefile.common - diff --git a/lib/Analysis/DataStructure/Printer.cpp b/lib/Analysis/DataStructure/Printer.cpp deleted file mode 100644 index 21d75c08bc0..00000000000 --- a/lib/Analysis/DataStructure/Printer.cpp +++ /dev/null @@ -1,356 +0,0 @@ -//===- Printer.cpp - Code for printing data structure graphs nicely -------===// -// -// 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 'dot' graph printer. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Analysis/DataStructure/DSGraphTraits.h" -#include "llvm/Module.h" -#include "llvm/Constants.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/GraphWriter.h" -#include "llvm/Support/Streams.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Config/config.h" -#include -#include -#include -using namespace llvm; - -// OnlyPrintMain - The DataStructure printer exposes this option to allow -// printing of only the graph for "main". -// -namespace { - cl::opt OnlyPrintMain("only-print-main-ds", cl::ReallyHidden); - cl::opt DontPrintAnything("dont-print-ds", cl::ReallyHidden); - Statistic MaxGraphSize ("dsa", "Maximum graph size"); - Statistic NumFoldedNodes ("dsa", "Number of folded nodes (in final graph)"); -} - -void DSNode::dump() const { print(cerr, 0); } - -static std::string getCaption(const DSNode *N, const DSGraph *G) { - std::stringstream OS; - Module *M = 0; - - if (!G) G = N->getParentGraph(); - - // Get the module from ONE of the functions in the graph it is available. - if (G && G->retnodes_begin() != G->retnodes_end()) - M = G->retnodes_begin()->first->getParent(); - if (M == 0 && G) { - // If there is a global in the graph, we can use it to find the module. - const DSScalarMap &SM = G->getScalarMap(); - if (SM.global_begin() != SM.global_end()) - M = (*SM.global_begin())->getParent(); - } - - if (N->isNodeCompletelyFolded()) - OS << "COLLAPSED"; - else { - WriteTypeSymbolic(OS, N->getType(), M); - if (N->isArray()) - OS << " array"; - } - if (unsigned NodeType = N->getNodeFlags()) { - OS << ": "; - if (NodeType & DSNode::AllocaNode ) OS << "S"; - if (NodeType & DSNode::HeapNode ) OS << "H"; - if (NodeType & DSNode::GlobalNode ) OS << "G"; - if (NodeType & DSNode::UnknownNode) OS << "U"; - if (NodeType & DSNode::Incomplete ) OS << "I"; - if (NodeType & DSNode::Modified ) OS << "M"; - if (NodeType & DSNode::Read ) OS << "R"; -#ifndef NDEBUG - if (NodeType & DSNode::DEAD ) OS << ""; -#endif - OS << "\n"; - } - - EquivalenceClasses *GlobalECs = 0; - if (G) GlobalECs = &G->getGlobalECs(); - - for (unsigned i = 0, e = N->getGlobalsList().size(); i != e; ++i) { - WriteAsOperand(OS, N->getGlobalsList()[i], false, M); - - // Figure out how many globals are equivalent to this one. - if (GlobalECs) { - EquivalenceClasses::iterator I = - GlobalECs->findValue(N->getGlobalsList()[i]); - if (I != GlobalECs->end()) { - unsigned NumMembers = - std::distance(GlobalECs->member_begin(I), GlobalECs->member_end()); - if (NumMembers != 1) OS << " + " << (NumMembers-1) << " EC"; - } - } - OS << "\n"; - } - - return OS.str(); -} - -namespace llvm { -template<> -struct DOTGraphTraits : public DefaultDOTGraphTraits { - static std::string getGraphName(const DSGraph *G) { - switch (G->getReturnNodes().size()) { - case 0: return G->getFunctionNames(); - case 1: return "Function " + G->getFunctionNames(); - default: return "Functions: " + G->getFunctionNames(); - } - } - - static std::string getNodeLabel(const DSNode *Node, const DSGraph *Graph) { - return getCaption(Node, Graph); - } - - static std::string getNodeAttributes(const DSNode *N, const DSGraph *Graph) { - return "shape=Mrecord"; - } - - static bool edgeTargetsEdgeSource(const void *Node, - DSNode::const_iterator I) { - unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); - return (O >> DS::PointerShift) != 0; - } - - static DSNode::const_iterator getEdgeTarget(const DSNode *Node, - DSNode::const_iterator I) { - unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); - unsigned LinkNo = O >> DS::PointerShift; - const DSNode *N = *I; - DSNode::const_iterator R = N->begin(); - for (; LinkNo; --LinkNo) - ++R; - return R; - } - - - /// addCustomGraphFeatures - Use this graph writing hook to emit call nodes - /// and the return node. - /// - static void addCustomGraphFeatures(const DSGraph *G, - GraphWriter &GW) { - Module *CurMod = 0; - if (G->retnodes_begin() != G->retnodes_end()) - CurMod = G->retnodes_begin()->first->getParent(); - else { - // If there is a global in the graph, we can use it to find the module. - const DSScalarMap &SM = G->getScalarMap(); - if (SM.global_begin() != SM.global_end()) - CurMod = (*SM.global_begin())->getParent(); - } - - - // Add scalar nodes to the graph... - const DSGraph::ScalarMapTy &VM = G->getScalarMap(); - for (DSGraph::ScalarMapTy::const_iterator I = VM.begin(); I != VM.end();++I) - if (!isa(I->first)) { - std::stringstream OS; - WriteAsOperand(OS, I->first, false, CurMod); - GW.emitSimpleNode(I->first, "", OS.str()); - - // Add edge from return node to real destination - DSNode *DestNode = I->second.getNode(); - int EdgeDest = I->second.getOffset() >> DS::PointerShift; - if (EdgeDest == 0) EdgeDest = -1; - GW.emitEdge(I->first, -1, DestNode, - EdgeDest, "arrowtail=tee,color=gray63"); - } - - - // Output the returned value pointer... - for (DSGraph::retnodes_iterator I = G->retnodes_begin(), - E = G->retnodes_end(); I != E; ++I) - if (I->second.getNode()) { - std::string Label; - if (G->getReturnNodes().size() == 1) - Label = "returning"; - else - Label = I->first->getName() + " ret node"; - // Output the return node... - GW.emitSimpleNode((void*)I->first, "plaintext=circle", Label); - - // Add edge from return node to real destination - DSNode *RetNode = I->second.getNode(); - int RetEdgeDest = I->second.getOffset() >> DS::PointerShift;; - if (RetEdgeDest == 0) RetEdgeDest = -1; - GW.emitEdge((void*)I->first, -1, RetNode, - RetEdgeDest, "arrowtail=tee,color=gray63"); - } - - // Output all of the call nodes... - const std::list &FCs = - G->shouldPrintAuxCalls() ? G->getAuxFunctionCalls() - : G->getFunctionCalls(); - for (std::list::const_iterator I = FCs.begin(), E = FCs.end(); - I != E; ++I) { - const DSCallSite &Call = *I; - std::vector EdgeSourceCaptions(Call.getNumPtrArgs()+2); - EdgeSourceCaptions[0] = "r"; - if (Call.isDirectCall()) - EdgeSourceCaptions[1] = Call.getCalleeFunc()->getName(); - else - EdgeSourceCaptions[1] = "f"; - - GW.emitSimpleNode(&Call, "shape=record", "call", Call.getNumPtrArgs()+2, - &EdgeSourceCaptions); - - if (DSNode *N = Call.getRetVal().getNode()) { - int EdgeDest = Call.getRetVal().getOffset() >> DS::PointerShift; - if (EdgeDest == 0) EdgeDest = -1; - GW.emitEdge(&Call, 0, N, EdgeDest, "color=gray63,tailclip=false"); - } - - // Print out the callee... - if (Call.isIndirectCall()) { - DSNode *N = Call.getCalleeNode(); - assert(N && "Null call site callee node!"); - GW.emitEdge(&Call, 1, N, -1, "color=gray63,tailclip=false"); - } - - for (unsigned j = 0, e = Call.getNumPtrArgs(); j != e; ++j) - if (DSNode *N = Call.getPtrArg(j).getNode()) { - int EdgeDest = Call.getPtrArg(j).getOffset() >> DS::PointerShift; - if (EdgeDest == 0) EdgeDest = -1; - GW.emitEdge(&Call, j+2, N, EdgeDest, "color=gray63,tailclip=false"); - } - } - } -}; -} // end namespace llvm - -void DSNode::print(std::ostream &O, const DSGraph *G) const { - GraphWriter W(O, G); - W.writeNode(this); -} - -void DSGraph::print(std::ostream &O) const { - WriteGraph(O, this, "DataStructures"); -} - -void DSGraph::writeGraphToFile(std::ostream &O, - const std::string &GraphName) const { - std::string Filename = GraphName + ".dot"; - O << "Writing '" << Filename << "'..."; - std::ofstream F(Filename.c_str()); - - if (F.good()) { - print(F); - unsigned NumCalls = shouldPrintAuxCalls() ? - getAuxFunctionCalls().size() : getFunctionCalls().size(); - O << " [" << getGraphSize() << "+" << NumCalls << "]\n"; - } else { - O << " error opening file for writing!\n"; - } -} - -/// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, -/// then cleanup. For use from the debugger. -/// -void DSGraph::viewGraph() const { - ViewGraph(this, "ds.tempgraph", "DataStructures"); -} - - -template -static void printCollection(const Collection &C, std::ostream &O, - const Module *M, const std::string &Prefix) { - if (M == 0) { - O << "Null Module pointer, cannot continue!\n"; - return; - } - - unsigned TotalNumNodes = 0, TotalCallNodes = 0; - for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) - if (C.hasGraph(*I)) { - DSGraph &Gr = C.getDSGraph((Function&)*I); - unsigned NumCalls = Gr.shouldPrintAuxCalls() ? - Gr.getAuxFunctionCalls().size() : Gr.getFunctionCalls().size(); - bool IsDuplicateGraph = false; - - if (I->getName() == "main" || !OnlyPrintMain) { - Function *SCCFn = Gr.retnodes_begin()->first; - if (&*I == SCCFn) { - Gr.writeGraphToFile(O, Prefix+I->getName()); - } else { - IsDuplicateGraph = true; // Don't double count node/call nodes. - O << "Didn't write '" << Prefix+I->getName() - << ".dot' - Graph already emitted to '" << Prefix+SCCFn->getName() - << "\n"; - } - } else { - Function *SCCFn = Gr.retnodes_begin()->first; - if (&*I == SCCFn) { - O << "Skipped Writing '" << Prefix+I->getName() << ".dot'... [" - << Gr.getGraphSize() << "+" << NumCalls << "]\n"; - } else { - IsDuplicateGraph = true; // Don't double count node/call nodes. - } - } - - if (!IsDuplicateGraph) { - unsigned GraphSize = Gr.getGraphSize(); - if (MaxGraphSize < GraphSize) MaxGraphSize = GraphSize; - - TotalNumNodes += Gr.getGraphSize(); - TotalCallNodes += NumCalls; - for (DSGraph::node_iterator NI = Gr.node_begin(), E = Gr.node_end(); - NI != E; ++NI) - if (NI->isNodeCompletelyFolded()) - ++NumFoldedNodes; - } - } - - DSGraph &GG = C.getGlobalsGraph(); - TotalNumNodes += GG.getGraphSize(); - TotalCallNodes += GG.getFunctionCalls().size(); - if (!OnlyPrintMain) { - GG.writeGraphToFile(O, Prefix+"GlobalsGraph"); - } else { - O << "Skipped Writing '" << Prefix << "GlobalsGraph.dot'... [" - << GG.getGraphSize() << "+" << GG.getFunctionCalls().size() << "]\n"; - } - - O << "\nGraphs contain [" << TotalNumNodes << "+" << TotalCallNodes - << "] nodes total" << std::endl; -} - - -// print - Print out the analysis results... -void LocalDataStructures::print(std::ostream &O, const Module *M) const { - if (DontPrintAnything) return; - printCollection(*this, O, M, "ds."); -} - -void BUDataStructures::print(std::ostream &O, const Module *M) const { - if (DontPrintAnything) return; - printCollection(*this, O, M, "bu."); -} - -void TDDataStructures::print(std::ostream &O, const Module *M) const { - if (DontPrintAnything) return; - printCollection(*this, O, M, "td."); -} - -void CompleteBUDataStructures::print(std::ostream &O, const Module *M) const { - if (DontPrintAnything) return; - printCollection(*this, O, M, "cbu."); -} - - -void EquivClassGraphs::print(std::ostream &O, const Module *M) const { - if (DontPrintAnything) return; - printCollection(*this, O, M, "eq."); -} - diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp deleted file mode 100644 index 5ff3c3f8522..00000000000 --- a/lib/Analysis/DataStructure/Steensgaard.cpp +++ /dev/null @@ -1,278 +0,0 @@ -//===- Steensgaard.cpp - Context Insensitive Alias 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 pass uses the data structure graphs to implement a simple context -// insensitive alias analysis. It does this by computing the local analysis -// graphs for all of the functions, then merging them together into a single big -// graph without cloning. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Module.h" -#include "llvm/Support/Debug.h" -#include -using namespace llvm; - -namespace { - class Steens : public ModulePass, public AliasAnalysis { - DSGraph *ResultGraph; - - EquivalenceClasses GlobalECs; // Always empty - public: - Steens() : ResultGraph(0) {} - ~Steens() { - releaseMyMemory(); - assert(ResultGraph == 0 && "releaseMemory not called?"); - } - - //------------------------------------------------ - // Implement the Pass API - // - - // run - Build up the result graph, representing the pointer graph for the - // program. - // - bool runOnModule(Module &M); - - virtual void releaseMyMemory() { delete ResultGraph; ResultGraph = 0; } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.setPreservesAll(); // Does not transform code... - AU.addRequired(); // Uses local dsgraph - } - - // print - Implement the Pass::print method... - void print(OStream O, const Module *M) const { - if (O.stream()) print(*O.stream(), M); - } - void print(std::ostream &O, const Module *M) const { - assert(ResultGraph && "Result graph has not yet been computed!"); - ResultGraph->writeGraphToFile(O, "steensgaards"); - } - - //------------------------------------------------ - // Implement the AliasAnalysis API - // - - AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); - - virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); - virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); - - private: - void ResolveFunctionCall(Function *F, const DSCallSite &Call, - DSNodeHandle &RetVal); - }; - - // Register the pass... - RegisterPass X("steens-aa", - "Steensgaard's alias analysis (DSGraph based)"); - - // Register as an implementation of AliasAnalysis - RegisterAnalysisGroup Y(X); -} - -ModulePass *llvm::createSteensgaardPass() { return new Steens(); } - -/// ResolveFunctionCall - Resolve the actual arguments of a call to function F -/// with the specified call site descriptor. This function links the arguments -/// and the return value for the call site context-insensitively. -/// -void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call, - DSNodeHandle &RetVal) { - assert(ResultGraph != 0 && "Result graph not allocated!"); - DSGraph::ScalarMapTy &ValMap = ResultGraph->getScalarMap(); - - // Handle the return value of the function... - if (Call.getRetVal().getNode() && RetVal.getNode()) - RetVal.mergeWith(Call.getRetVal()); - - // Loop over all pointer arguments, resolving them to their provided pointers - unsigned PtrArgIdx = 0; - for (Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); - AI != AE && PtrArgIdx < Call.getNumPtrArgs(); ++AI) { - DSGraph::ScalarMapTy::iterator I = ValMap.find(AI); - if (I != ValMap.end()) // If its a pointer argument... - I->second.mergeWith(Call.getPtrArg(PtrArgIdx++)); - } -} - - -/// run - Build up the result graph, representing the pointer graph for the -/// program. -/// -bool Steens::runOnModule(Module &M) { - InitializeAliasAnalysis(this); - assert(ResultGraph == 0 && "Result graph already allocated!"); - LocalDataStructures &LDS = getAnalysis(); - - // Create a new, empty, graph... - ResultGraph = new DSGraph(GlobalECs, getTargetData()); - ResultGraph->spliceFrom(LDS.getGlobalsGraph()); - - // Loop over the rest of the module, merging graphs for non-external functions - // into this graph. - // - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal()) - ResultGraph->spliceFrom(LDS.getDSGraph(*I)); - - ResultGraph->removeTriviallyDeadNodes(); - - // FIXME: Must recalculate and use the Incomplete markers!! - - // Now that we have all of the graphs inlined, we can go about eliminating - // call nodes... - // - std::list &Calls = ResultGraph->getAuxFunctionCalls(); - assert(Calls.empty() && "Aux call list is already in use??"); - - // Start with a copy of the original call sites. - Calls = ResultGraph->getFunctionCalls(); - - for (std::list::iterator CI = Calls.begin(), E = Calls.end(); - CI != E;) { - DSCallSite &CurCall = *CI++; - - // Loop over the called functions, eliminating as many as possible... - std::vector CallTargets; - if (CurCall.isDirectCall()) - CallTargets.push_back(CurCall.getCalleeFunc()); - else - CurCall.getCalleeNode()->addFullFunctionList(CallTargets); - - for (unsigned c = 0; c != CallTargets.size(); ) { - // If we can eliminate this function call, do so! - Function *F = CallTargets[c]; - if (!F->isExternal()) { - ResolveFunctionCall(F, CurCall, ResultGraph->getReturnNodes()[F]); - CallTargets[c] = CallTargets.back(); - CallTargets.pop_back(); - } else - ++c; // Cannot eliminate this call, skip over it... - } - - if (CallTargets.empty()) { // Eliminated all calls? - std::list::iterator I = CI; - Calls.erase(--I); // Remove entry - } - } - - // Remove our knowledge of what the return values of the functions are, except - // for functions that are externally visible from this module (e.g. main). We - // keep these functions so that their arguments are marked incomplete. - for (DSGraph::ReturnNodesTy::iterator I = - ResultGraph->getReturnNodes().begin(), - E = ResultGraph->getReturnNodes().end(); I != E; ) - if (I->first->hasInternalLinkage()) - ResultGraph->getReturnNodes().erase(I++); - else - ++I; - - // Update the "incomplete" markers on the nodes, ignoring unknownness due to - // incoming arguments... - ResultGraph->maskIncompleteMarkers(); - ResultGraph->markIncompleteNodes(DSGraph::IgnoreGlobals | - DSGraph::MarkFormalArgs); - - // Remove any nodes that are dead after all of the merging we have done... - // FIXME: We should be able to disable the globals graph for steens! - //ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); - - print(DOUT, &M); - return false; -} - -AliasAnalysis::AliasResult Steens::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - assert(ResultGraph && "Result graph has not been computed yet!"); - - DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap(); - - DSGraph::ScalarMapTy::iterator I = GSM.find(const_cast(V1)); - DSGraph::ScalarMapTy::iterator J = GSM.find(const_cast(V2)); - if (I != GSM.end() && !I->second.isNull() && - J != GSM.end() && !J->second.isNull()) { - DSNodeHandle &V1H = I->second; - DSNodeHandle &V2H = J->second; - - // If at least one of the nodes is complete, we can say something about - // this. If one is complete and the other isn't, then they are obviously - // different nodes. If they are both complete, we can't say anything - // useful. - if (I->second.getNode()->isComplete() || - J->second.getNode()->isComplete()) { - // If the two pointers point to different data structure graph nodes, they - // cannot alias! - if (V1H.getNode() != V2H.getNode()) - return NoAlias; - - // See if they point to different offsets... if so, we may be able to - // determine that they do not alias... - unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); - if (O1 != O2) { - if (O2 < O1) { // Ensure that O1 <= O2 - std::swap(V1, V2); - std::swap(O1, O2); - std::swap(V1Size, V2Size); - } - - if (O1+V1Size <= O2) - return NoAlias; - } - } - } - - // If we cannot determine alias properties based on our graph, fall back on - // some other AA implementation. - // - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); -} - -AliasAnalysis::ModRefResult -Steens::getModRefInfo(CallSite CS, Value *P, unsigned Size) { - AliasAnalysis::ModRefResult Result = ModRef; - - // Find the node in question. - DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap(); - DSGraph::ScalarMapTy::iterator I = GSM.find(P); - - if (I != GSM.end() && !I->second.isNull()) { - DSNode *N = I->second.getNode(); - if (N->isComplete()) { - // If this is a direct call to an external function, and if the pointer - // points to a complete node, the external function cannot modify or read - // the value (we know it's not passed out of the program!). - if (Function *F = CS.getCalledFunction()) - if (F->isExternal()) - return NoModRef; - - // Otherwise, if the node is complete, but it is only M or R, return this. - // This can be useful for globals that should be marked const but are not. - if (!N->isModified()) - Result = (ModRefResult)(Result & ~Mod); - if (!N->isRead()) - Result = (ModRefResult)(Result & ~Ref); - } - } - - return (ModRefResult)(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); -} - -AliasAnalysis::ModRefResult -Steens::getModRefInfo(CallSite CS1, CallSite CS2) -{ - return AliasAnalysis::getModRefInfo(CS1,CS2); -} diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp deleted file mode 100644 index 71bf271a6eb..00000000000 --- 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 // Register the pass - Y("tddatastructure", "Top-down Data Structure Analysis"); - - Statistic NumTDInlines("tddatastructures", "Number of graphs inlined"); -} - -void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N, - hash_set &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 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(); - 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 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 VisitedGraph; - std::vector 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().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 &Visited, - std::vector &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::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 EdgesFromCaller; - std::map >::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 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, 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 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(V)) - return I->getParent()->getParent(); - else if (const Argument *A = dyn_cast(V)) - return A->getParent(); - else if (const BasicBlock *BB = dyn_cast(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(V)) { - assert(getDSGraph(*F).getReturnNodes().size() == 1 && - "cannot handle scc's"); - delete DSInfo[F]; - DSInfo.erase(F); - return; - } - - assert(!isa(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(From)) { - Function *ToF = cast(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(); -} -- 2.34.1