diff options
Diffstat (limited to 'lib/Analysis')
| -rw-r--r-- | lib/Analysis/DataStructure/DependenceGraph.cpp | 87 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/DependenceGraph.h | 255 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/IPModRef.cpp | 445 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/IPModRef.h | 232 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/MemoryDepAnalysis.cpp | 502 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/MemoryDepAnalysis.h | 103 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/Parallelize.cpp | 498 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/PgmDependenceGraph.cpp | 258 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/PgmDependenceGraph.h | 301 |
9 files changed, 0 insertions, 2681 deletions
diff --git a/lib/Analysis/DataStructure/DependenceGraph.cpp b/lib/Analysis/DataStructure/DependenceGraph.cpp deleted file mode 100644 index de3f45a447..0000000000 --- a/lib/Analysis/DataStructure/DependenceGraph.cpp +++ /dev/null @@ -1,87 +0,0 @@ -//===- DependenceGraph.cpp - Dependence graph for a function ----*- 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 file implements an explicit representation for the dependence graph -// of a function, with one node per instruction and one edge per dependence. -// Dependences include both data and control dependences. -// -// Each dep. graph node (class DepGraphNode) keeps lists of incoming and -// outgoing dependence edges. -// -// Each dep. graph edge (class Dependence) keeps a pointer to one end-point -// of the dependence. This saves space and is important because dep. graphs -// can grow quickly. It works just fine because the standard idiom is to -// start with a known node and enumerate the dependences to or from that node. -//===----------------------------------------------------------------------===// - - -#include "DependenceGraph.h" -#include "llvm/Function.h" - -namespace llvm { - -//---------------------------------------------------------------------------- -// class Dependence: -// -// A representation of a simple (non-loop-related) dependence -//---------------------------------------------------------------------------- - -void Dependence::print(std::ostream &O) const -{ - assert(depType != NoDependence && "This dependence should never be created!"); - switch (depType) { - case TrueDependence: O << "TRUE dependence"; break; - case AntiDependence: O << "ANTI dependence"; break; - case OutputDependence: O << "OUTPUT dependence"; break; - case ControlDependence: O << "CONTROL dependence"; break; - default: assert(0 && "Invalid dependence type"); break; - } -} - - -//---------------------------------------------------------------------------- -// class DepGraphNode -//---------------------------------------------------------------------------- - -void DepGraphNode::print(std::ostream &O) const -{ - const_iterator DI = outDepBegin(), DE = outDepEnd(); - - O << "\nDeps. from instr:" << getInstr(); - - for ( ; DI != DE; ++DI) - { - O << "\t"; - DI->print(O); - O << " to instruction:"; - O << DI->getSink()->getInstr(); - } -} - -//---------------------------------------------------------------------------- -// class DependenceGraph -//---------------------------------------------------------------------------- - -DependenceGraph::~DependenceGraph() -{ - // Free all DepGraphNode objects created for this graph - for (map_iterator I = depNodeMap.begin(), E = depNodeMap.end(); I != E; ++I) - delete I->second; -} - -void DependenceGraph::print(const Function& func, std::ostream &O) const -{ - O << "DEPENDENCE GRAPH FOR FUNCTION " << func.getName() << ":\n"; - for (Function::const_iterator BB=func.begin(), FE=func.end(); BB != FE; ++BB) - for (BasicBlock::const_iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II) - if (const DepGraphNode* dgNode = this->getNode(*II)) - dgNode->print(O); -} - -} // End llvm namespace diff --git a/lib/Analysis/DataStructure/DependenceGraph.h b/lib/Analysis/DataStructure/DependenceGraph.h deleted file mode 100644 index 520b008528..0000000000 --- a/lib/Analysis/DataStructure/DependenceGraph.h +++ /dev/null @@ -1,255 +0,0 @@ -//===- DependenceGraph.h - Dependence graph for a function ------*- 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 file provides an explicit representation for the dependence graph -// of a function, with one node per instruction and one edge per dependence. -// Dependences include both data and control dependences. -// -// Each dep. graph node (class DepGraphNode) keeps lists of incoming and -// outgoing dependence edges. -// -// Each dep. graph edge (class Dependence) keeps a pointer to one end-point -// of the dependence. This saves space and is important because dep. graphs -// can grow quickly. It works just fine because the standard idiom is to -// start with a known node and enumerate the dependences to or from that node. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H -#define LLVM_ANALYSIS_DEPENDENCEGRAPH_H - -#include "llvm/ADT/hash_map" -#include <cassert> -#include <iosfwd> -#include <utility> -#include <vector> - -namespace llvm { - -class Instruction; -class Function; -class Dependence; -class DepGraphNode; -class DependenceGraph; - -//---------------------------------------------------------------------------- -/// enum DependenceType - The standard data dependence types -/// -enum DependenceType { - NoDependence = 0x0, - TrueDependence = 0x1, - AntiDependence = 0x2, - OutputDependence = 0x4, - ControlDependence = 0x8, // from a terminator to some other instr. - IncomingFlag = 0x10 // is this an incoming or outgoing dep? -}; - -//---------------------------------------------------------------------------- -/// Dependence Class - A representation of a simple (non-loop-related) -/// dependence. -/// -class Dependence { - DepGraphNode* toOrFromNode; - unsigned char depType; - -public: - Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming) - : toOrFromNode(toOrFromN), - depType(type | (isIncoming? IncomingFlag : 0x0)) { } - - Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode), - depType(D.depType) { } - - bool operator==(const Dependence& D) const { - return toOrFromNode == D.toOrFromNode && depType == D.depType; - } - - /// Get information about the type of dependence. - /// - unsigned getDepType() const { - return depType; - } - - /// Get source or sink depending on what type of node this is! - /// - DepGraphNode* getSrc() { - assert(depType & IncomingFlag); return toOrFromNode; - } - const DepGraphNode* getSrc() const { - assert(depType & IncomingFlag); return toOrFromNode; - } - - DepGraphNode* getSink() { - assert(! (depType & IncomingFlag)); return toOrFromNode; - } - const DepGraphNode* getSink() const { - assert(! (depType & IncomingFlag)); return toOrFromNode; - } - - /// Debugging support methods - /// - void print(std::ostream &O) const; - - // Default constructor: Do not use directly except for graph builder code - // - Dependence() : toOrFromNode(NULL), depType(NoDependence) { } -}; - -#ifdef SUPPORTING_LOOP_DEPENDENCES -struct LoopDependence: public Dependence { - DependenceDirection dir; - int distance; - short level; - LoopInfo* enclosingLoop; -}; -#endif - - -//---------------------------------------------------------------------------- -/// DepGraphNode Class - A representation of a single node in a dependence -/// graph, corresponding to a single instruction. -/// -class DepGraphNode { - Instruction* instr; - std::vector<Dependence> inDeps; - std::vector<Dependence> outDeps; - friend class DependenceGraph; - - typedef std::vector<Dependence>:: iterator iterator; - typedef std::vector<Dependence>::const_iterator const_iterator; - - iterator inDepBegin() { return inDeps.begin(); } - const_iterator inDepBegin() const { return inDeps.begin(); } - iterator inDepEnd() { return inDeps.end(); } - const_iterator inDepEnd() const { return inDeps.end(); } - - iterator outDepBegin() { return outDeps.begin(); } - const_iterator outDepBegin() const { return outDeps.begin(); } - iterator outDepEnd() { return outDeps.end(); } - const_iterator outDepEnd() const { return outDeps.end(); } - -public: - DepGraphNode(Instruction& I) : instr(&I) { } - - Instruction& getInstr() { return *instr; } - const Instruction& getInstr() const { return *instr; } - - /// Debugging support methods - /// - void print(std::ostream &O) const; -}; - - -//---------------------------------------------------------------------------- -/// DependenceGraph Class - A representation of a dependence graph for a -/// procedure. The primary query operation here is to look up a DepGraphNode for -/// a particular instruction, and then use the in/out dependence iterators -/// for the node. -/// -class DependenceGraph { - DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT - void operator=(const DependenceGraph&); // DO NOT IMPLEMENT - - typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType; - typedef DepNodeMapType:: iterator map_iterator; - typedef DepNodeMapType::const_iterator const_map_iterator; - - DepNodeMapType depNodeMap; - - inline DepGraphNode* getNodeInternal(Instruction& inst, - bool createIfMissing = false) { - map_iterator I = depNodeMap.find(&inst); - if (I == depNodeMap.end()) - return (!createIfMissing)? NULL : - depNodeMap.insert( - std::make_pair(&inst, new DepGraphNode(inst))).first->second; - else - return I->second; - } - -public: - typedef std::vector<Dependence>:: iterator iterator; - typedef std::vector<Dependence>::const_iterator const_iterator; - -public: - DependenceGraph() { } - ~DependenceGraph(); - - /// Get the graph node for an instruction. There will be one if and - /// only if there are any dependences incident on this instruction. - /// If there is none, these methods will return NULL. - /// - DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) { - return getNodeInternal(inst, createIfMissing); - } - const DepGraphNode* getNode(const Instruction& inst) const { - return const_cast<DependenceGraph*>(this) - ->getNodeInternal(const_cast<Instruction&>(inst)); - } - - iterator inDepBegin(DepGraphNode& T) { - return T.inDeps.begin(); - } - const_iterator inDepBegin (const DepGraphNode& T) const { - return T.inDeps.begin(); - } - - iterator inDepEnd(DepGraphNode& T) { - return T.inDeps.end(); - } - const_iterator inDepEnd(const DepGraphNode& T) const { - return T.inDeps.end(); - } - - iterator outDepBegin(DepGraphNode& F) { - return F.outDeps.begin(); - } - const_iterator outDepBegin(const DepGraphNode& F) const { - return F.outDeps.begin(); - } - - iterator outDepEnd(DepGraphNode& F) { - return F.outDeps.end(); - } - const_iterator outDepEnd(const DepGraphNode& F) const { - return F.outDeps.end(); - } - - /// Debugging support methods - /// - void print(const Function& func, std::ostream &O) const; - -public: - /// AddSimpleDependence - adding and modifying the dependence graph. - /// These should to be used only by dependence analysis implementations. - /// - void AddSimpleDependence(Instruction& fromI, Instruction& toI, - DependenceType depType) { - DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true); - DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true); - fromNode->outDeps.push_back(Dependence(toNode, depType, false)); - toNode-> inDeps. push_back(Dependence(fromNode, depType, true)); - } - -#ifdef SUPPORTING_LOOP_DEPENDENCES - // This interface is a placeholder to show what information is needed. - // It will probably change when it starts being used. - void AddLoopDependence(Instruction& fromI, - Instruction& toI, - DependenceType depType, - DependenceDirection dir, - int distance, - short level, - LoopInfo* enclosingLoop); -#endif // SUPPORTING_LOOP_DEPENDENCES -}; - -} // End llvm namespace - -#endif 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 diff --git a/lib/Analysis/DataStructure/IPModRef.h b/lib/Analysis/DataStructure/IPModRef.h deleted file mode 100644 index bb674a0591..0000000000 --- a/lib/Analysis/DataStructure/IPModRef.h +++ /dev/null @@ -1,232 +0,0 @@ -//===- IPModRef.h - 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. -// -//===----------------------------------------------------------------------===// -// -// class IPModRef: -// -// class IPModRef is an interprocedural analysis pass that computes -// flow-insensitive IP Mod and Ref information for every function -// (the GMOD and GREF problems) and for every call site (MOD and REF). -// -// In practice, this needs to do NO real interprocedural work because -// all that is needed is done by the data structure analysis. -// This uses the top-down DS graph for a function and the bottom-up DS graph -// for each callee (including the Mod/Ref flags in the bottom-up graph) -// to compute the set of nodes that are Mod and Ref for the function and -// for each of its call sites. -// -// -// class FunctionModRefInfo: -// -// The results of IPModRef are encapsulated in the class FunctionModRefInfo. -// The results are stored as bit vectors: bit i represents node i -// in the TD DSGraph for the current function. (This node numbering is -// implemented by class FunctionModRefInfo.) Each FunctionModRefInfo -// includes: -// -- 2 bit vectors for the function (GMOD and GREF), and -// -- 2 bit vectors for each call site (MOD and REF). -// -// -// IPModRef vs. Alias Analysis for Clients: -// -// The IPModRef pass does not provide simpler query interfaces for specific -// LLVM values, instructions, or pointers because those results should be -// obtained through alias analysis (e.g., class DSAliasAnalysis). -// class IPModRef is primarily meant for other analysis passes that need to -// use Mod/Ref information efficiently for more complicated purposes; -// the bit-vector representations make propagation very efficient. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_IPMODREF_H -#define LLVM_ANALYSIS_IPMODREF_H - -#include "llvm/Pass.h" -#include "llvm/ADT/BitSetVector.h" -#include "llvm/ADT/hash_map" - -namespace llvm { - -class Module; -class Function; -class CallSite; -class Instruction; -class CallInst; -class InvokeInst; -class DSNode; -class DSGraph; -class DSNodeHandle; -class ModRefInfo; // Result of IP Mod/Ref for one entity -class FunctionModRefInfo; // ModRefInfo for a func and all calls in it -class IPModRef; // Pass that computes IP Mod/Ref info - -//---------------------------------------------------------------------------- -/// ModRefInfo Class - Representation of Mod/Ref information for a single -/// function or callsite. This is represented as a pair of bit vectors, one each -/// for Mod and Ref. Each bit vector is indexed by the node id of the DS graph -/// node index. -/// -class ModRefInfo { - BitSetVector modNodeSet; // set of modified nodes - BitSetVector refNodeSet; // set of referenced nodes - -public: - // Methods to construct ModRefInfo objects. - ModRefInfo(unsigned int numNodes) - : modNodeSet(numNodes), - refNodeSet(numNodes) { } - - unsigned getSize() const { - assert(modNodeSet.size() == refNodeSet.size() && - "Mod & Ref different size?"); - return modNodeSet.size(); - } - - void setNodeIsMod (unsigned nodeId) { modNodeSet[nodeId] = true; } - void setNodeIsRef (unsigned nodeId) { refNodeSet[nodeId] = true; } - - // Methods to query the mod/ref info - bool nodeIsMod (unsigned nodeId) const { return modNodeSet.test(nodeId); } - bool nodeIsRef (unsigned nodeId) const { return refNodeSet.test(nodeId); } - bool nodeIsKill(unsigned nodeId) const { return false; } - - const BitSetVector& getModSet() const { return modNodeSet; } - BitSetVector& getModSet() { return modNodeSet; } - - const BitSetVector& getRefSet() const { return refNodeSet; } - BitSetVector& getRefSet() { return refNodeSet; } - - // Debugging support methods - void print(std::ostream &O, const std::string& prefix=std::string("")) const; - void dump() const; -}; - - -//---------------------------------------------------------------------------- -/// FunctionModRefInfo Class - Representation of the results of IP Mod/Ref -/// analysis for a function and for each of the call sites within the function. -/// Each of these are represented as bit vectors of size = the number of nodes -/// in the top-dwon DS graph of the function. Nodes are identified by their -/// nodeId, in the range [0 .. funcTDGraph.size()-1]. -/// -class FunctionModRefInfo { - const Function& F; // The function - IPModRef& IPModRefObj; // The IPModRef Object owning this - DSGraph* funcTDGraph; // Top-down DS graph for function - ModRefInfo funcModRefInfo; // ModRefInfo for the function body - std::map<const Instruction*, ModRefInfo*> - callSiteModRefInfo; // ModRefInfo for each callsite - std::map<const DSNode*, unsigned&g |