diff options
Diffstat (limited to 'lib/Analysis/DataStructure/IPModRef.cpp')
| -rw-r--r-- | lib/Analysis/DataStructure/IPModRef.cpp | 445 |
1 files changed, 0 insertions, 445 deletions
diff --git a/lib/Analysis/DataStructure/IPModRef.cpp b/lib/Analysis/DataStructure/IPModRef.cpp deleted file mode 100644 index e1217bd091..0000000000 --- a/lib/Analysis/DataStructure/IPModRef.cpp +++ /dev/null @@ -1,445 +0,0 @@ -//===- IPModRef.cpp - Compute IP Mod/Ref information ------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// See high-level comments in IPModRef.h -// -//===----------------------------------------------------------------------===// - -#include "IPModRef.h" -#include "llvm/Analysis/DataStructure/DataStructure.h" -#include "llvm/Analysis/DataStructure/DSGraph.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringExtras.h" -#include <vector> - -namespace llvm { - -//---------------------------------------------------------------------------- -// Private constants and data -//---------------------------------------------------------------------------- - -static RegisterAnalysis<IPModRef> -Z("ipmodref", "Interprocedural mod/ref analysis"); - - -//---------------------------------------------------------------------------- -// class ModRefInfo -//---------------------------------------------------------------------------- - -void ModRefInfo::print(std::ostream &O, - const std::string& sprefix) const -{ - O << sprefix << "Modified nodes = " << modNodeSet; - O << sprefix << "Referenced nodes = " << refNodeSet; -} - -void ModRefInfo::dump() const -{ - print(std::cerr); -} - -//---------------------------------------------------------------------------- -// class FunctionModRefInfo -//---------------------------------------------------------------------------- - - -// This constructor computes a node numbering for the TD graph. -// -FunctionModRefInfo::FunctionModRefInfo(const Function& func, - IPModRef& ipmro, - DSGraph* tdgClone) - : F(func), IPModRefObj(ipmro), - funcTDGraph(tdgClone), - funcModRefInfo(tdgClone->getGraphSize()) -{ - unsigned i = 0; - for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), - E = funcTDGraph->node_end(); NI != E; ++NI) - NodeIds[*NI] = i++; -} - - -FunctionModRefInfo::~FunctionModRefInfo() -{ - for(std::map<const Instruction*, ModRefInfo*>::iterator - I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I) - delete(I->second); - - // Empty map just to make problems easier to track down - callSiteModRefInfo.clear(); - - delete funcTDGraph; -} - -unsigned FunctionModRefInfo::getNodeId(const Value* value) const { - return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value)) - .getNode()); -} - - - -// Compute Mod/Ref bit vectors for the entire function. -// These are simply copies of the Read/Write flags from the nodes of -// the top-down DS graph. -// -void FunctionModRefInfo::computeModRef(const Function &func) -{ - // Mark all nodes in the graph that are marked MOD as being mod - // and all those marked REF as being ref. - unsigned i = 0; - for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), - E = funcTDGraph->node_end(); NI != E; ++NI, ++i) { - if ((*NI)->isModified()) funcModRefInfo.setNodeIsMod(i); - if ((*NI)->isRead()) funcModRefInfo.setNodeIsRef(i); - } - - // Compute the Mod/Ref info for all call sites within the function. - // The call sites are recorded in the TD graph. - const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls(); - for (unsigned i = 0, N = callSites.size(); i < N; ++i) - computeModRef(callSites[i].getCallSite()); -} - - -// ResolveCallSiteModRefInfo - This method performs the following actions: -// -// 1. It clones the top-down graph for the current function -// 2. It clears all of the mod/ref bits in the cloned graph -// 3. It then merges the bottom-up graph(s) for the specified call-site into -// the clone (bringing new mod/ref bits). -// 4. It returns the clone, and a mapping of nodes from the original TDGraph to -// the cloned graph with Mod/Ref info for the callsite. -// -// NOTE: Because this clones a dsgraph and returns it, the caller is responsible -// for deleting the returned graph! -// NOTE: This method may return a null pointer if it is unable to determine the -// requested information (because the call site calls an external -// function or we cannot determine the complete set of functions invoked). -// -DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallSite CS, - hash_map<const DSNode*, DSNodeHandle> &NodeMap) -{ - // Step #0: Quick check if we are going to fail anyway: avoid - // all the graph cloning and map copying in steps #1 and #2. - // - if (const Function *F = CS.getCalledFunction()) { - if (F->isExternal()) - return 0; // We cannot compute Mod/Ref info for this callsite... - } else { - // Eventually, should check here if any callee is external. - // For now we are not handling this case anyway. - std::cerr << "IP Mod/Ref indirect call not implemented yet: " - << "Being conservative\n"; - return 0; // We cannot compute Mod/Ref info for this callsite... - } - - // Step #1: Clone the top-down graph... - DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap); - - // Step #2: Clear Mod/Ref information... - Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read)); - - // Step #3: clone the bottom up graphs for the callees into the caller graph - if (Function *F = CS.getCalledFunction()) - { - assert(!F->isExternal()); - - // Build up a DSCallSite for our invocation point here... - - // If the call returns a value, make sure to merge the nodes... - DSNodeHandle RetVal; - if (DS::isPointerType(CS.getInstruction()->getType())) - RetVal = Result->getNodeForValue(CS.getInstruction()); - - // Populate the arguments list... - std::vector<DSNodeHandle> Args; - for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); - I != E; ++I) - if (DS::isPointerType((*I)->getType())) - Args.push_back(Result->getNodeForValue(*I)); - - // Build the call site... - DSCallSite NCS(CS, RetVal, F, Args); - - // Perform the merging now of the graph for the callee, which will - // come with mod/ref bits set... - Result->mergeInGraph(NCS, *F, IPModRefObj.getBUDSGraph(*F), - DSGraph::StripAllocaBit - | DSGraph::DontCloneCallNodes - | DSGraph::DontCloneAuxCallNodes); - } - else - assert(0 && "See error message"); - - // Remove dead nodes aggressively to match the caller's original graph. - Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals); - - // Step #4: Return the clone + the mapping (by ref) - return Result; -} - -// Compute Mod/Ref bit vectors for a single call site. -// These are copies of the Read/Write flags from the nodes of -// the graph produced by clearing all flags in the caller's TD graph -// and then inlining the callee's BU graph into the caller's TD graph. -// -void -FunctionModRefInfo::computeModRef(CallSite CS) -{ - // Allocate the mod/ref info for the call site. Bits automatically cleared. - ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize()); - callSiteModRefInfo[CS.getInstruction()] = callModRefInfo; - - // Get a copy of the graph for the callee with the callee inlined - hash_map<const DSNode*, DSNodeHandle> NodeMap; - DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap); - if (!csgp) - { // Callee's side effects are unknown: mark all nodes Mod and Ref. - // Eventually this should only mark nodes visible to the callee, i.e., - // exclude stack variables not reachable from any outgoing argument - // or any global. - callModRefInfo->getModSet().set(); - callModRefInfo->getRefSet().set(); - return; - } - - // For all nodes in the graph, extract the mod/ref information - for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), - E = funcTDGraph->node_end(); NI != E; ++NI) { - DSNode* csgNode = NodeMap[*NI].getNode(); - assert(csgNode && "Inlined and original graphs do not correspond!"); - if (csgNode->isModified()) - callModRefInfo->setNodeIsMod(getNodeId(*NI)); - if (csgNode->isRead()) - callModRefInfo->setNodeIsRef(getNodeId(*NI)); - } - - // Drop nodemap before we delete the graph... - NodeMap.clear(); - delete csgp; -} - - -class DSGraphPrintHelper { - const DSGraph& tdGraph; - std::vector<std::vector<const Value*> > knownValues; // identifiable objects - -public: - /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo) - : tdGraph(fmrInfo.getFuncGraph()) - { - knownValues.resize(tdGraph.getGraphSize()); - - // For every identifiable value, save Value pointer in knownValues[i] - for (hash_map<Value*, DSNodeHandle>::const_iterator - I = tdGraph.getScalarMap().begin(), - E = tdGraph.getScalarMap().end(); I != E; ++I) - if (isa<GlobalValue>(I->first) || - isa<Argument>(I->first) || - isa<LoadInst>(I->first) || - isa<AllocaInst>(I->first) || - isa<MallocInst>(I->first)) - { - unsigned nodeId = fmrInfo.getNodeId(I->second.getNode()); - knownValues[nodeId].push_back(I->first); - } - } - - void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const - { - assert(bv.size() == knownValues.size()); - - if (bv.none()) - { // No bits are set: just say so and return - O << "\tNONE.\n"; - return; - } - - if (bv.all()) - { // All bits are set: just say so and return - O << "\tALL GRAPH NODES.\n"; - return; - } - - for (unsigned i=0, N=bv.size(); i < N; ++i) - if (bv.test(i)) - { - O << "\tNode# " << i << " : "; - if (! knownValues[i].empty()) - for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++) - { - const Value* V = knownValues[i][j]; - - if (isa<GlobalValue>(V)) O << "(Global) "; - else if (isa<Argument>(V)) O << "(Target of FormalParm) "; - else if (isa<LoadInst>(V)) O << "(Target of LoadInst ) "; - else if (isa<AllocaInst>(V)) O << "(Target of AllocaInst) "; - else if (isa<MallocInst>(V)) O << "(Target of MallocInst) "; - - if (V->hasName()) O << V->getName(); - else if (isa<Instruction>(V)) O << *V; - else O << "(Value*) 0x" << (void*) V; - - O << std::string((j < NV-1)? "; " : "\n"); - } -#if 0 - else - tdGraph.getNodes()[i]->print(O, /*graph*/ NULL); -#endif - } - } -}; - - -// Print the results of the pass. -// Currently this just prints bit-vectors and is not very readable. -// -void FunctionModRefInfo::print(std::ostream &O) const -{ - DSGraphPrintHelper DPH(*this); - - O << "========== Mod/ref information for function " - << F.getName() << "========== \n\n"; - - // First: Print Globals and Locals modified anywhere in the function. - // - O << " -----Mod/Ref in the body of function " << F.getName()<< ":\n"; - - O << " --Objects modified in the function body:\n"; - DPH.printValuesInBitVec(O, funcModRefInfo.getModSet()); - - O << " --Objects referenced in the function body:\n"; - DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet()); - - O << " --Mod and Ref vectors for the nodes listed above:\n"; - funcModRefInfo.print(O, "\t"); - - O << "\n"; - - // Second: Print Globals and Locals modified at each call site in function - // - for (std::map<const Instruction *, ModRefInfo*>::const_iterator - CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end(); - CI != CE; ++CI) - { - O << " ----Mod/Ref information for call site\n" << *CI->first; - - O << " --Objects modified at call site:\n"; - DPH.printValuesInBitVec(O, CI->second->getModSet()); - - O << " --Objects referenced at call site:\n"; - DPH.printValuesInBitVec(O, CI->second->getRefSet()); - - O << " --Mod and Ref vectors for the nodes listed above:\n"; - CI->second->print(O, "\t"); - - O << "\n"; - } - - O << "\n"; -} - -void FunctionModRefInfo::dump() const -{ - print(std::cerr); -} - - -//---------------------------------------------------------------------------- -// class IPModRef: An interprocedural pass that computes IP Mod/Ref info. -//---------------------------------------------------------------------------- - -// Free the FunctionModRefInfo objects cached in funcToModRefInfoMap. -// -void IPModRef::releaseMemory() -{ - for(std::map<const Function*, FunctionModRefInfo*>::iterator - I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I) - delete(I->second); - - // Clear map so memory is not re-released if we are called again - funcToModRefInfoMap.clear(); -} - -// Run the "interprocedural" pass on each function. This needs to do -// NO real interprocedural work because all that has been done the -// data structure analysis. -// -bool IPModRef::runOnModule(Module &theModule) -{ - M = &theModule; - - for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI) - if (! FI->isExternal()) - getFuncInfo(*FI, /*computeIfMissing*/ true); - return true; -} - - -FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func, - bool computeIfMissing) -{ - FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func]; - assert (funcInfo != NULL || computeIfMissing); - if (funcInfo == NULL) - { // Create a new FunctionModRefInfo object. - // Clone the top-down graph and remove any dead nodes first, because - // otherwise original and merged graphs will not match. - // The memory for this graph clone will be freed by FunctionModRefInfo. - DSGraph* funcTDGraph = - new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func)); - funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); - - funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert - funcInfo->computeModRef(func); // computes the mod/ref info - } - return *funcInfo; -} - -/// getBUDSGraph - This method returns the BU data structure graph for F through -/// the use of the BUDataStructures object. -/// -const DSGraph &IPModRef::getBUDSGraph(const Function &F) { - return getAnalysis<BUDataStructures>().getDSGraph(F); -} - - -// getAnalysisUsage - This pass requires top-down data structure graphs. -// It modifies nothing. -// -void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<LocalDataStructures>(); - AU.addRequired<BUDataStructures>(); - AU.addRequired<TDDataStructures>(); -} - - -void IPModRef::print(std::ostream &O, const Module*) const -{ - O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n"; - - for (std::map<const Function*, FunctionModRefInfo*>::const_iterator - mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end(); - mapI != mapE; ++mapI) - mapI->second->print(O); - - O << "\n"; -} - - -void IPModRef::dump() const -{ - print(std::cerr); -} - -} // End llvm namespace |