-//===- MemoryDepAnalysis.cpp - Compute dep graph for memory ops --*-C++-*--===//
+//===- MemoryDepAnalysis.cpp - Compute dep graph for memory ops -----------===//
+//
+// 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 a pass (MemoryDepAnalysis) that computes memory-based
// data dependences between instructions for each function in a module.
//
// The result of this pass is a DependenceGraph for each function
// representing the memory-based data dependences between instructions.
+//
//===----------------------------------------------------------------------===//
-#include "llvm/Analysis/MemoryDepAnalysis.h"
-#include "llvm/Analysis/IPModRef.h"
-#include "llvm/Analysis/DataStructure.h"
-#include "llvm/Analysis/DSGraph.h"
+#include "MemoryDepAnalysis.h"
+#include "IPModRef.h"
+#include "llvm/Instructions.h"
#include "llvm/Module.h"
-#include "llvm/iMemory.h"
-#include "llvm/iOther.h"
+#include "llvm/Analysis/DataStructure/DataStructure.h"
+#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/CFG.h"
-#include "Support/TarjanSCCIterator.h"
-#include "Support/Statistic.h"
-#include "Support/STLExtras.h"
-#include "Support/hash_map"
-#include "Support/hash_set"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/hash_map"
+#include "llvm/ADT/hash_set"
+namespace llvm {
///--------------------------------------------------------------------------
/// struct ModRefTable:
/// not copied over from one table to another since it is no longer useful.
///--------------------------------------------------------------------------
-struct ModRefTable
-{
+struct ModRefTable {
typedef hash_map<Instruction*, ModRefInfo> ModRefMap;
typedef ModRefMap::const_iterator const_map_iterator;
- typedef ModRefMap:: iterator map_iterator;
+ typedef ModRefMap:: iterator map_iterator;
typedef std::vector<Instruction*>::const_iterator const_ref_iterator;
typedef std::vector<Instruction*>:: iterator ref_iterator;
class ModRefInfoBuilder : public InstVisitor<ModRefInfoBuilder> {
const DSGraph& funcGraph;
const FunctionModRefInfo& funcModRef;
- ModRefTable& modRefTable;
+ struct ModRefTable& modRefTable;
ModRefInfoBuilder(); // DO NOT IMPLEMENT
ModRefInfoBuilder(const ModRefInfoBuilder&); // DO NOT IMPLEMENT
void operator=(const ModRefInfoBuilder&); // DO NOT IMPLEMENT
public:
- /*ctor*/ ModRefInfoBuilder(const DSGraph& _funcGraph,
- const FunctionModRefInfo& _funcModRef,
- ModRefTable& _modRefTable)
+ ModRefInfoBuilder(const DSGraph& _funcGraph,
+ const FunctionModRefInfo& _funcModRef,
+ ModRefTable& _modRefTable)
: funcGraph(_funcGraph), funcModRef(_funcModRef), modRefTable(_modRefTable)
{
}
// Add the call to the defs list if it modifies any nodes and to the uses
// list if it refs any nodes.
//
- void visitCallInst (CallInst& callInst) {
+ void visitCallInst(CallInst& callInst) {
ModRefInfo safeModRef(funcGraph.getGraphSize());
const ModRefInfo* callModRef = funcModRef.getModRefInfo(callInst);
- if (callModRef == NULL)
- { // call to external/unknown function: mark all nodes as Mod and Ref
- safeModRef.getModSet().set();
- safeModRef.getRefSet().set();
- callModRef = &safeModRef;
- }
+ if (callModRef == NULL) {
+ // call to external/unknown function: mark all nodes as Mod and Ref
+ safeModRef.getModSet().set();
+ safeModRef.getRefSet().set();
+ callModRef = &safeModRef;
+ }
modRefTable.modRefMap.insert(std::make_pair(&callInst,
ModRefInfo(*callModRef)));
// At a store instruction, add to the mod set the single node pointed to
// by the pointer argument of the store. Interestingly, if there is no
// such node, that would be a null pointer reference!
- void visitStoreInst (StoreInst& storeInst) {
+ void visitStoreInst(StoreInst& storeInst) {
const DSNodeHandle& ptrNode =
funcGraph.getNodeForValue(storeInst.getPointerOperand());
- if (const DSNode* target = ptrNode.getNode())
- {
- unsigned nodeId = funcModRef.getNodeId(target);
- ModRefInfo& minfo =
- modRefTable.modRefMap.insert(
- std::make_pair(&storeInst,
- ModRefInfo(funcGraph.getGraphSize()))).first->second;
- minfo.setNodeIsMod(nodeId);
- modRefTable.AddDef(&storeInst);
- }
- else
+ if (const DSNode* target = ptrNode.getNode()) {
+ unsigned nodeId = funcModRef.getNodeId(target);
+ ModRefInfo& minfo =
+ modRefTable.modRefMap.insert(
+ std::make_pair(&storeInst,
+ ModRefInfo(funcGraph.getGraphSize()))).first->second;
+ minfo.setNodeIsMod(nodeId);
+ modRefTable.AddDef(&storeInst);
+ } else
std::cerr << "Warning: Uninitialized pointer reference!\n";
}
// At a load instruction, add to the ref set the single node pointed to
// by the pointer argument of the load. Interestingly, if there is no
// such node, that would be a null pointer reference!
- void visitLoadInst (LoadInst& loadInst) {
+ void visitLoadInst(LoadInst& loadInst) {
const DSNodeHandle& ptrNode =
funcGraph.getNodeForValue(loadInst.getPointerOperand());
- if (const DSNode* target = ptrNode.getNode())
- {
- unsigned nodeId = funcModRef.getNodeId(target);
- ModRefInfo& minfo =
- modRefTable.modRefMap.insert(
- std::make_pair(&loadInst,
- ModRefInfo(funcGraph.getGraphSize()))).first->second;
- minfo.setNodeIsRef(nodeId);
- modRefTable.AddUse(&loadInst);
- }
- else
+ if (const DSNode* target = ptrNode.getNode()) {
+ unsigned nodeId = funcModRef.getNodeId(target);
+ ModRefInfo& minfo =
+ modRefTable.modRefMap.insert(
+ std::make_pair(&loadInst,
+ ModRefInfo(funcGraph.getGraphSize()))).first->second;
+ minfo.setNodeIsRef(nodeId);
+ modRefTable.AddUse(&loadInst);
+ } else
std::cerr << "Warning: Uninitialized pointer reference!\n";
}
};
// class MemoryDepAnalysis: A dep. graph for load/store/call instructions
//----------------------------------------------------------------------------
-/// Basic dependence gathering algorithm, using TarjanSCCIterator on CFG:
+
+/// getAnalysisUsage - This does not modify anything. It uses the Top-Down DS
+/// Graph and IPModRef.
+///
+void MemoryDepAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<TDDataStructures>();
+ AU.addRequired<IPModRef>();
+}
+
+
+/// Basic dependence gathering algorithm, using scc_iterator on CFG:
///
/// for every SCC S in the CFG in PostOrder on the SCC DAG
/// {
/// }
///
///
-void MemoryDepAnalysis::ProcessSCC(SCC<Function*>& S,
- ModRefTable& ModRefAfter) {
+void MemoryDepAnalysis::ProcessSCC(std::vector<BasicBlock*> &S,
+ ModRefTable& ModRefAfter, bool hasLoop) {
ModRefTable ModRefCurrent;
ModRefTable::ModRefMap& mapCurrent = ModRefCurrent.modRefMap;
ModRefTable::ModRefMap& mapAfter = ModRefAfter.modRefMap;
- bool hasLoop = S.HasLoop();
-
// Builder class fills out a ModRefTable one instruction at a time.
// To use it, we just invoke it's visit function for each basic block:
//
// : Add I to ModRefCurrent.users if it uses any node
//
ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent);
- for (SCC<Function*>::iterator BI=S.begin(), BE=S.end(); BI != BE; ++BI)
- // Note: BBs in the SCC<> created by TarjanSCCIterator are in postorder.
+ for (std::vector<BasicBlock*>::iterator BI = S.begin(), BE = S.end();
+ BI != BE; ++BI)
+ // Note: BBs in the SCC<> created by scc_iterator are in postorder.
for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend();
II != IE; ++II)
builder.visit(*II);
ModRefTable ModRefAfter;
- SCC<Function*>* nextSCC;
- for (TarjanSCC_iterator<Function*> I = tarj_begin(&F), E = tarj_end(&F);
- I != E; ++I)
- ProcessSCC(**I, ModRefAfter);
+ for (scc_iterator<Function*> I = scc_begin(&F), E = scc_end(&F); I != E; ++I)
+ ProcessSCC(*I, ModRefAfter, I.hasLoop());
return true;
}
static RegisterAnalysis<MemoryDepAnalysis>
Z("memdep", "Memory Dependence Analysis");
+
+} // End llvm namespace
projects / oota-llvm.git / blobdiff