/// getTargetData - Every alias analysis implementation depends on the size of
/// data items in the current Target. This provides a uniform way to handle
/// it.
+ ///
const TargetData &getTargetData() const { return *TD; }
//===--------------------------------------------------------------------===//
/// replaceScalar - When an instruction needs to be modified, this method can
/// be used to update the scalar map to remove the old and insert the new.
+ ///
void replaceScalar(Value *Old, Value *New) {
iterator I = find(Old);
assert(I != end() && "Old value is not in the map!");
/// getFunctionNames - Return a space separated list of the name of the
/// functions in this graph (if any)
+ ///
std::string getFunctionNames() const;
/// addNode - Add a new node to the graph.
/// getReturnNodes - Return the mapping of functions to their return nodes for
/// this graph.
+ ///
const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; }
ReturnNodesTy &getReturnNodes() { return ReturnNodes; }
/// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
/// then cleanup. For use from the debugger.
+ ///
void viewGraph() const;
void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
void mergeInGraph(const DSCallSite &CS, Function &F, const DSGraph &Graph,
unsigned CloneFlags);
-
/// getCallSiteForArguments - Get the arguments and return value bindings for
/// the specified function in the current graph.
///
};
- /// ReachabilityCloner - This class is used to incrementally clone and merge
- /// nodes from a non-changing source graph into a potentially mutating
- /// destination graph. Nodes are only cloned over on demand, either in
- /// responds to a merge() or getClonedNH() call. When a node is cloned over,
- /// all of the nodes reachable from it are automatically brought over as well.
- class ReachabilityCloner {
- DSGraph &Dest;
- const DSGraph &Src;
-
- /// BitsToKeep - These bits are retained from the source node when the
- /// source nodes are merged into the destination graph.
- unsigned BitsToKeep;
- unsigned CloneFlags;
-
- // NodeMap - A mapping from nodes in the source graph to the nodes that
- // represent them in the destination graph.
- DSGraph::NodeMapTy NodeMap;
- public:
- ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
- : Dest(dest), Src(src), CloneFlags(cloneFlags) {
- assert(&Dest != &Src && "Cannot clone from graph to same graph!");
- BitsToKeep = ~DSNode::DEAD;
- if (CloneFlags & DSGraph::StripAllocaBit)
- BitsToKeep &= ~DSNode::AllocaNode;
- if (CloneFlags & DSGraph::StripModRefBits)
- BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
- if (CloneFlags & DSGraph::StripIncompleteBit)
- BitsToKeep &= ~DSNode::Incomplete;
- }
-
- DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
+/// ReachabilityCloner - This class is used to incrementally clone and merge
+/// nodes from a non-changing source graph into a potentially mutating
+/// destination graph. Nodes are only cloned over on demand, either in
+/// responds to a merge() or getClonedNH() call. When a node is cloned over,
+/// all of the nodes reachable from it are automatically brought over as well.
+///
+class ReachabilityCloner {
+ DSGraph &Dest;
+ const DSGraph &Src;
+
+ /// BitsToKeep - These bits are retained from the source node when the
+ /// source nodes are merged into the destination graph.
+ unsigned BitsToKeep;
+ unsigned CloneFlags;
+
+ // NodeMap - A mapping from nodes in the source graph to the nodes that
+ // represent them in the destination graph.
+ DSGraph::NodeMapTy NodeMap;
+public:
+ ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
+ : Dest(dest), Src(src), CloneFlags(cloneFlags) {
+ assert(&Dest != &Src && "Cannot clone from graph to same graph!");
+ BitsToKeep = ~DSNode::DEAD;
+ if (CloneFlags & DSGraph::StripAllocaBit)
+ BitsToKeep &= ~DSNode::AllocaNode;
+ if (CloneFlags & DSGraph::StripModRefBits)
+ BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
+ if (CloneFlags & DSGraph::StripIncompleteBit)
+ BitsToKeep &= ~DSNode::Incomplete;
+ }
+
+ DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
- void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
+ void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
- /// mergeCallSite - Merge the nodes reachable from the specified src call
- /// site into the nodes reachable from DestCS.
- void mergeCallSite(const DSCallSite &DestCS, const DSCallSite &SrcCS);
+ /// mergeCallSite - Merge the nodes reachable from the specified src call
+ /// site into the nodes reachable from DestCS.
+ ///
+ void mergeCallSite(const DSCallSite &DestCS, const DSCallSite &SrcCS);
- bool clonedAnyNodes() const { return !NodeMap.empty(); }
+ bool clonedAnyNodes() const { return !NodeMap.empty(); }
- /// hasClonedNode - Return true if the specified node has been cloned from
- /// the source graph into the destination graph.
- bool hasClonedNode(const DSNode *N) {
- return NodeMap.count(N);
- }
+ /// hasClonedNode - Return true if the specified node has been cloned from
+ /// the source graph into the destination graph.
+ bool hasClonedNode(const DSNode *N) {
+ return NodeMap.count(N);
+ }
+
+ void destroy() { NodeMap.clear(); }
+};
- void destroy() { NodeMap.clear(); }
- };
} // End llvm namespace
#endif
/// that this node really is. When nodes get folded together, the node to be
/// eliminated has these fields filled in, otherwise ForwardNH.getNode() is
/// null.
+ ///
DSNodeHandle ForwardNH;
/// Next, Prev - These instance variables are used to keep the node on a
/// doubly-linked ilist in the DSGraph.
+ ///
DSNode *Next, *Prev;
friend class ilist_traits<DSNode>;
/// DSNode ctor - Create a node of the specified type, inserting it into the
/// specified graph.
+ ///
DSNode(const Type *T, DSGraph *G);
/// DSNode "copy ctor" - Copy the specified node, inserting it into the
/// specified graph. If NullLinks is true, then null out all of the links,
/// but keep the same number of them. This can be used for efficiency if the
/// links are just going to be clobbered anyway.
+ ///
DSNode(const DSNode &, DSGraph *G, bool NullLinks = false);
~DSNode() {
///
unsigned getSize() const { return Size; }
- // getType - Return the node type of this object...
+ /// getType - Return the node type of this object...
+ ///
const Type *getType() const { return Ty; }
+
bool isArray() const { return NodeType & Array; }
/// hasNoReferrers - Return true if nothing is pointing to this node at all.
/// getForwardNode - This method returns the node that this node is forwarded
/// to, if any.
+ ///
DSNode *getForwardNode() const { return ForwardNH.getNode(); }
/// isForwarding - Return true if this node is forwarding to another.
/// stopForwarding - When the last reference to this forwarding node has been
/// dropped, delete the node.
+ ///
void stopForwarding() {
assert(isForwarding() &&
- "Node isn't forwarding, cannot stopForwarding!");
+ "Node isn't forwarding, cannot stopForwarding()!");
ForwardNH.setNode(0);
assert(ParentGraph == 0 &&
"Forwarding nodes must have been removed from graph!");
}
/// getLink - Return the link at the specified offset.
+ ///
DSNodeHandle &getLink(unsigned Offset) {
assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
"Pointer offset not aligned correctly!");
/// getNodeFlags - Return all of the flags set on the node. If the DEAD flag
/// is set, hide it from the caller.
+ ///
unsigned getNodeFlags() const { return NodeType & ~DEAD; }
bool isAllocaNode() const { return NodeType & AllocaNode; }
/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
+ ///
void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
/// markReachableNodes - This method recursively traverses the specified
getNode()->setLink(Off+Offset, NH);
}
-/// addEdgeTo - Add an edge from the current node to the specified node. This
+/// addEdgeTo - Add an edge from the current node to the specified node. This
/// can cause merging of nodes in the graph.
///
inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) {
PointerSize = 1 << PointerShift
};
- // isPointerType - Return true if this first class type is big enough to hold
- // a pointer.
- //
+ /// isPointerType - Return true if this first class type is big enough to hold
+ /// a pointer.
+ ///
bool isPointerType(const Type *Ty);
};
/// isNull - Check to see if getNode() == 0, without going through the trouble
/// of checking to see if we are forwarding...
+ ///
bool isNull() const { return N == 0; }
// Allow explicit conversion to DSNode...
///
void mergeWith(const DSNodeHandle &N) const;
- // hasLink - Return true if there is a link at the specified offset...
+ /// hasLink - Return true if there is a link at the specified offset...
+ ///
inline bool hasLink(unsigned Num) const;
/// getLink - Treat this current node pointer as a pointer to a structure of
}
}
- // mergeWith - Merge the return value and parameters of the these two call
- // sites.
+ /// mergeWith - Merge the return value and parameters of the these two call
+ /// sites.
+ ///
void mergeWith(DSCallSite &CS) {
getRetVal().mergeWith(CS.getRetVal());
unsigned MinArgs = getNumPtrArgs();
// FIXME: move this stuff to a private header
namespace DataStructureAnalysis {
- // isPointerType - Return true if this first class type is big enough to hold
- // a pointer.
- //
+ /// isPointerType - Return true if this first class type is big enough to hold
+ /// a pointer.
+ ///
bool isPointerType(const Type *Ty);
}
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// releaseMemory - if the pass pipeline is done with this pass, we can
+ /// release our memory...
+ ///
virtual void releaseMemory();
- // getAnalysisUsage - This obviously provides a data structure graph.
+ /// getAnalysisUsage - This obviously provides a data structure graph.
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<TargetData>();
};
-// BUDataStructures - The analysis that computes the interprocedurally closed
-// data structure graphs for all of the functions in the program. This pass
-// only performs a "Bottom Up" propagation (hence the name).
-//
+/// BUDataStructures - The analysis that computes the interprocedurally closed
+/// data structure graphs for all of the functions in the program. This pass
+/// only performs a "Bottom Up" propagation (hence the name).
+///
class BUDataStructures : public Pass {
protected:
// DSInfo, one graph for each function
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// releaseMemory - if the pass pipeline is done with this pass, we can
+ /// release our memory...
+ ///
virtual void releaseMemory();
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
};
-// TDDataStructures - Analysis that computes new data structure graphs
-// for each function using the closed graphs for the callers computed
-// by the bottom-up pass.
-//
+/// TDDataStructures - Analysis that computes new data structure graphs
+/// for each function using the closed graphs for the callers computed
+/// by the bottom-up pass.
+///
class TDDataStructures : public Pass {
// DSInfo, one graph for each function
hash_map<Function*, DSGraph*> DSInfo;
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// If the pass pipeline is done with this pass, we can release our memory...
+ ///
virtual void releaseMyMemory();
- // getAnalysisUsage - This obviously provides a data structure graph.
+ /// getAnalysisUsage - This obviously provides a data structure graph.
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<BUDataStructures>();
};
-// CompleteBUDataStructures - 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.
-//
+/// CompleteBUDataStructures - 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.
+///
struct CompleteBUDataStructures : public BUDataStructures {
virtual bool run(Module &M);
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
AU.addRequired<TDDataStructures>();
}
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
private:
void processGraph(DSGraph &G);
};
-
-
} // End llvm namespace
#endif
/// replaceScalar - When an instruction needs to be modified, this method can
/// be used to update the scalar map to remove the old and insert the new.
+ ///
void replaceScalar(Value *Old, Value *New) {
iterator I = find(Old);
assert(I != end() && "Old value is not in the map!");
/// getFunctionNames - Return a space separated list of the name of the
/// functions in this graph (if any)
+ ///
std::string getFunctionNames() const;
/// addNode - Add a new node to the graph.
/// getReturnNodes - Return the mapping of functions to their return nodes for
/// this graph.
+ ///
const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; }
ReturnNodesTy &getReturnNodes() { return ReturnNodes; }
/// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
/// then cleanup. For use from the debugger.
+ ///
void viewGraph() const;
void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
void mergeInGraph(const DSCallSite &CS, Function &F, const DSGraph &Graph,
unsigned CloneFlags);
-
/// getCallSiteForArguments - Get the arguments and return value bindings for
/// the specified function in the current graph.
///
};
- /// ReachabilityCloner - This class is used to incrementally clone and merge
- /// nodes from a non-changing source graph into a potentially mutating
- /// destination graph. Nodes are only cloned over on demand, either in
- /// responds to a merge() or getClonedNH() call. When a node is cloned over,
- /// all of the nodes reachable from it are automatically brought over as well.
- class ReachabilityCloner {
- DSGraph &Dest;
- const DSGraph &Src;
-
- /// BitsToKeep - These bits are retained from the source node when the
- /// source nodes are merged into the destination graph.
- unsigned BitsToKeep;
- unsigned CloneFlags;
-
- // NodeMap - A mapping from nodes in the source graph to the nodes that
- // represent them in the destination graph.
- DSGraph::NodeMapTy NodeMap;
- public:
- ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
- : Dest(dest), Src(src), CloneFlags(cloneFlags) {
- assert(&Dest != &Src && "Cannot clone from graph to same graph!");
- BitsToKeep = ~DSNode::DEAD;
- if (CloneFlags & DSGraph::StripAllocaBit)
- BitsToKeep &= ~DSNode::AllocaNode;
- if (CloneFlags & DSGraph::StripModRefBits)
- BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
- if (CloneFlags & DSGraph::StripIncompleteBit)
- BitsToKeep &= ~DSNode::Incomplete;
- }
-
- DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
+/// ReachabilityCloner - This class is used to incrementally clone and merge
+/// nodes from a non-changing source graph into a potentially mutating
+/// destination graph. Nodes are only cloned over on demand, either in
+/// responds to a merge() or getClonedNH() call. When a node is cloned over,
+/// all of the nodes reachable from it are automatically brought over as well.
+///
+class ReachabilityCloner {
+ DSGraph &Dest;
+ const DSGraph &Src;
+
+ /// BitsToKeep - These bits are retained from the source node when the
+ /// source nodes are merged into the destination graph.
+ unsigned BitsToKeep;
+ unsigned CloneFlags;
+
+ // NodeMap - A mapping from nodes in the source graph to the nodes that
+ // represent them in the destination graph.
+ DSGraph::NodeMapTy NodeMap;
+public:
+ ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
+ : Dest(dest), Src(src), CloneFlags(cloneFlags) {
+ assert(&Dest != &Src && "Cannot clone from graph to same graph!");
+ BitsToKeep = ~DSNode::DEAD;
+ if (CloneFlags & DSGraph::StripAllocaBit)
+ BitsToKeep &= ~DSNode::AllocaNode;
+ if (CloneFlags & DSGraph::StripModRefBits)
+ BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
+ if (CloneFlags & DSGraph::StripIncompleteBit)
+ BitsToKeep &= ~DSNode::Incomplete;
+ }
+
+ DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
- void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
+ void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
- /// mergeCallSite - Merge the nodes reachable from the specified src call
- /// site into the nodes reachable from DestCS.
- void mergeCallSite(const DSCallSite &DestCS, const DSCallSite &SrcCS);
+ /// mergeCallSite - Merge the nodes reachable from the specified src call
+ /// site into the nodes reachable from DestCS.
+ ///
+ void mergeCallSite(const DSCallSite &DestCS, const DSCallSite &SrcCS);
- bool clonedAnyNodes() const { return !NodeMap.empty(); }
+ bool clonedAnyNodes() const { return !NodeMap.empty(); }
- /// hasClonedNode - Return true if the specified node has been cloned from
- /// the source graph into the destination graph.
- bool hasClonedNode(const DSNode *N) {
- return NodeMap.count(N);
- }
+ /// hasClonedNode - Return true if the specified node has been cloned from
+ /// the source graph into the destination graph.
+ bool hasClonedNode(const DSNode *N) {
+ return NodeMap.count(N);
+ }
+
+ void destroy() { NodeMap.clear(); }
+};
- void destroy() { NodeMap.clear(); }
- };
} // End llvm namespace
#endif
/// that this node really is. When nodes get folded together, the node to be
/// eliminated has these fields filled in, otherwise ForwardNH.getNode() is
/// null.
+ ///
DSNodeHandle ForwardNH;
/// Next, Prev - These instance variables are used to keep the node on a
/// doubly-linked ilist in the DSGraph.
+ ///
DSNode *Next, *Prev;
friend class ilist_traits<DSNode>;
/// DSNode ctor - Create a node of the specified type, inserting it into the
/// specified graph.
+ ///
DSNode(const Type *T, DSGraph *G);
/// DSNode "copy ctor" - Copy the specified node, inserting it into the
/// specified graph. If NullLinks is true, then null out all of the links,
/// but keep the same number of them. This can be used for efficiency if the
/// links are just going to be clobbered anyway.
+ ///
DSNode(const DSNode &, DSGraph *G, bool NullLinks = false);
~DSNode() {
///
unsigned getSize() const { return Size; }
- // getType - Return the node type of this object...
+ /// getType - Return the node type of this object...
+ ///
const Type *getType() const { return Ty; }
+
bool isArray() const { return NodeType & Array; }
/// hasNoReferrers - Return true if nothing is pointing to this node at all.
/// getForwardNode - This method returns the node that this node is forwarded
/// to, if any.
+ ///
DSNode *getForwardNode() const { return ForwardNH.getNode(); }
/// isForwarding - Return true if this node is forwarding to another.
/// stopForwarding - When the last reference to this forwarding node has been
/// dropped, delete the node.
+ ///
void stopForwarding() {
assert(isForwarding() &&
- "Node isn't forwarding, cannot stopForwarding!");
+ "Node isn't forwarding, cannot stopForwarding()!");
ForwardNH.setNode(0);
assert(ParentGraph == 0 &&
"Forwarding nodes must have been removed from graph!");
}
/// getLink - Return the link at the specified offset.
+ ///
DSNodeHandle &getLink(unsigned Offset) {
assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
"Pointer offset not aligned correctly!");
/// getNodeFlags - Return all of the flags set on the node. If the DEAD flag
/// is set, hide it from the caller.
+ ///
unsigned getNodeFlags() const { return NodeType & ~DEAD; }
bool isAllocaNode() const { return NodeType & AllocaNode; }
/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
+ ///
void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
/// markReachableNodes - This method recursively traverses the specified
getNode()->setLink(Off+Offset, NH);
}
-/// addEdgeTo - Add an edge from the current node to the specified node. This
+/// addEdgeTo - Add an edge from the current node to the specified node. This
/// can cause merging of nodes in the graph.
///
inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) {
PointerSize = 1 << PointerShift
};
- // isPointerType - Return true if this first class type is big enough to hold
- // a pointer.
- //
+ /// isPointerType - Return true if this first class type is big enough to hold
+ /// a pointer.
+ ///
bool isPointerType(const Type *Ty);
};
/// isNull - Check to see if getNode() == 0, without going through the trouble
/// of checking to see if we are forwarding...
+ ///
bool isNull() const { return N == 0; }
// Allow explicit conversion to DSNode...
///
void mergeWith(const DSNodeHandle &N) const;
- // hasLink - Return true if there is a link at the specified offset...
+ /// hasLink - Return true if there is a link at the specified offset...
+ ///
inline bool hasLink(unsigned Num) const;
/// getLink - Treat this current node pointer as a pointer to a structure of
}
}
- // mergeWith - Merge the return value and parameters of the these two call
- // sites.
+ /// mergeWith - Merge the return value and parameters of the these two call
+ /// sites.
+ ///
void mergeWith(DSCallSite &CS) {
getRetVal().mergeWith(CS.getRetVal());
unsigned MinArgs = getNumPtrArgs();
// FIXME: move this stuff to a private header
namespace DataStructureAnalysis {
- // isPointerType - Return true if this first class type is big enough to hold
- // a pointer.
- //
+ /// isPointerType - Return true if this first class type is big enough to hold
+ /// a pointer.
+ ///
bool isPointerType(const Type *Ty);
}
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// releaseMemory - if the pass pipeline is done with this pass, we can
+ /// release our memory...
+ ///
virtual void releaseMemory();
- // getAnalysisUsage - This obviously provides a data structure graph.
+ /// getAnalysisUsage - This obviously provides a data structure graph.
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<TargetData>();
};
-// BUDataStructures - The analysis that computes the interprocedurally closed
-// data structure graphs for all of the functions in the program. This pass
-// only performs a "Bottom Up" propagation (hence the name).
-//
+/// BUDataStructures - The analysis that computes the interprocedurally closed
+/// data structure graphs for all of the functions in the program. This pass
+/// only performs a "Bottom Up" propagation (hence the name).
+///
class BUDataStructures : public Pass {
protected:
// DSInfo, one graph for each function
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// releaseMemory - if the pass pipeline is done with this pass, we can
+ /// release our memory...
+ ///
virtual void releaseMemory();
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
};
-// TDDataStructures - Analysis that computes new data structure graphs
-// for each function using the closed graphs for the callers computed
-// by the bottom-up pass.
-//
+/// TDDataStructures - Analysis that computes new data structure graphs
+/// for each function using the closed graphs for the callers computed
+/// by the bottom-up pass.
+///
class TDDataStructures : public Pass {
// DSInfo, one graph for each function
hash_map<Function*, DSGraph*> DSInfo;
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
- // If the pass pipeline is done with this pass, we can release our memory...
+ /// If the pass pipeline is done with this pass, we can release our memory...
+ ///
virtual void releaseMyMemory();
- // getAnalysisUsage - This obviously provides a data structure graph.
+ /// getAnalysisUsage - This obviously provides a data structure graph.
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<BUDataStructures>();
};
-// CompleteBUDataStructures - 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.
-//
+/// CompleteBUDataStructures - 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.
+///
struct CompleteBUDataStructures : public BUDataStructures {
virtual bool run(Module &M);
return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
}
- // getDSGraph - Return the data structure graph for the specified function.
+ /// getDSGraph - Return the data structure graph for the specified function.
+ ///
DSGraph &getDSGraph(const Function &F) const {
hash_map<Function*, DSGraph*>::const_iterator I =
DSInfo.find(const_cast<Function*>(&F));
AU.addRequired<TDDataStructures>();
}
- // print - Print out the analysis results...
+ /// print - Print out the analysis results...
+ ///
void print(std::ostream &O, const Module *M) const;
private:
void processGraph(DSGraph &G);
};
-
-
} // End llvm namespace
#endif
#define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
#include "Support/hash_map"
+#include <cassert>
#include <iosfwd>
-#include <vector>
#include <utility>
-#include <cassert>
+#include <vector>
namespace llvm {
class DepGraphNode;
class DependenceGraph;
-
-//----------------------------------------------------------------------------
-// enum DependenceType: The standard data dependence types.
//----------------------------------------------------------------------------
-
+/// enum DependenceType - The standard data dependence types
+///
enum DependenceType {
NoDependence = 0x0,
TrueDependence = 0x1,
IncomingFlag = 0x10 // is this an incoming or outgoing dep?
};
-
//----------------------------------------------------------------------------
-// class Dependence:
-//
-// A representation of a simple (non-loop-related) dependence.
-//----------------------------------------------------------------------------
-
+/// Dependence Class - A representation of a simple (non-loop-related)
+/// dependence.
+///
class Dependence {
DepGraphNode* toOrFromNode;
unsigned char depType;
: toOrFromNode(toOrFromN),
depType(type | (isIncoming? IncomingFlag : 0x0)) { }
- /* copy ctor*/ Dependence (const Dependence& D)
- : toOrFromNode(D.toOrFromNode),
+ Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode),
depType(D.depType) { }
bool operator==(const Dependence& D) const {
/// Get source or sink depending on what type of node this is!
///
- DepGraphNode* getSrc() {
+ DepGraphNode* getSrc() {
assert(depType & IncomingFlag); return toOrFromNode;
}
- const DepGraphNode* getSrc() const {
+ const DepGraphNode* getSrc() const {
assert(depType & IncomingFlag); return toOrFromNode;
}
- DepGraphNode* getSink() {
+ DepGraphNode* getSink() {
assert(! (depType & IncomingFlag)); return toOrFromNode;
}
- const DepGraphNode* getSink() const {
+ const DepGraphNode* getSink() const {
assert(! (depType & IncomingFlag)); return toOrFromNode;
}
// Default constructor: Do not use directly except for graph builder code
//
- /*ctor*/ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
+ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
};
-
#ifdef SUPPORTING_LOOP_DEPENDENCES
struct LoopDependence: public Dependence {
DependenceDirection dir;
//----------------------------------------------------------------------------
-// class DepGraphNode:
-//
-// A representation of a single node in a dependence graph, corresponding
-// to a single instruction.
-//----------------------------------------------------------------------------
-
+/// 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;
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 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(); }
+ 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; }
+ Instruction& getInstr() { return *instr; }
+ const Instruction& getInstr() const { return *instr; }
/// Debugging support methods
///
//----------------------------------------------------------------------------
-// class DependenceGraph:
-//
-// 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.
-//----------------------------------------------------------------------------
-
+/// 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
DepNodeMapType depNodeMap;
inline DepGraphNode* getNodeInternal(Instruction& inst,
- bool createIfMissing = false) {
+ bool createIfMissing = false) {
map_iterator I = depNodeMap.find(&inst);
if (I == depNodeMap.end())
return (!createIfMissing)? NULL :
void print(const Function& func, std::ostream &O) const;
public:
- /// Functions for adding and modifying the dependence graph.
+ /// AddSimpleDependence - adding and modifying the dependence graph.
/// These should to be used only by dependence analysis implementations.
- void AddSimpleDependence(Instruction& fromI,
- Instruction& toI,
+ ///
+ void AddSimpleDependence(Instruction& fromI, Instruction& toI,
DependenceType depType) {
DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
DepGraphNode* toNode = getNodeInternal(toI, /*create*/ 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.
+ // 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,
#endif // SUPPORTING_LOOP_DEPENDENCES
};
-//===----------------------------------------------------------------------===//
-
} // End llvm namespace
#endif
template <typename GraphType> struct GraphTraits;
//===----------------------------------------------------------------------===//
-//
-// DominatorBase - Base class that other, more interesting dominator analyses
-// inherit from.
-//
+/// DominatorBase - Base class that other, more interesting dominator analyses
+/// inherit from.
+///
class DominatorBase : public FunctionPass {
protected:
std::vector<BasicBlock*> Roots;
inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
public:
- // Return the root blocks of the current CFG. This may include multiple
- // blocks if we are computing post dominators. For forward dominators, this
- // will always be a single block (the entry node).
+ /// getRoots - Return the root blocks of the current CFG. This may include
+ /// multiple blocks if we are computing post dominators. For forward
+ /// dominators, this will always be a single block (the entry node).
+ ///
inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
- // Returns true if analysis based of postdoms
+ /// isPostDominator - Returns true if analysis based of postdoms
+ ///
bool isPostDominator() const { return IsPostDominators; }
};
//===----------------------------------------------------------------------===//
-//
-// ImmediateDominators - Calculate the immediate dominator for each node in a
-// function.
-//
+/// ImmediateDominators - Calculate the immediate dominator for each node in a
+/// function.
+///
class ImmediateDominatorsBase : public DominatorBase {
protected:
std::map<BasicBlock*, BasicBlock*> IDoms;
inline const_iterator end() const { return IDoms.end(); }
inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
- // operator[] - Return the idom for the specified basic block. The start
- // node returns null, because it does not have an immediate dominator.
- //
+ /// operator[] - Return the idom for the specified basic block. The start
+ /// node returns null, because it does not have an immediate dominator.
+ ///
inline BasicBlock *operator[](BasicBlock *BB) const {
return get(BB);
}
- // get() - Synonym for operator[].
+ /// get() - Synonym for operator[].
+ ///
inline BasicBlock *get(BasicBlock *BB) const {
std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
return I != IDoms.end() ? I->second : 0;
/// change the current immediate dominator for the specified block to another
/// block. This method requires that BB already have an IDom, otherwise just
/// use addNewBlock.
+ ///
void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
IDoms[BB] = NewIDom;
}
- // print - Convert to human readable form
+ /// print - Convert to human readable form
+ ///
virtual void print(std::ostream &OS) const;
};
//===-------------------------------------
-// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
-// is used to compute a normal immediate dominator set.
-//
+/// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
+/// that is used to compute a normal immediate dominator set.
+///
struct ImmediateDominators : public ImmediateDominatorsBase {
ImmediateDominators() : ImmediateDominatorsBase(false) {}
//===----------------------------------------------------------------------===//
-//
-// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
-// function, that represents the blocks that dominate the block. If the block
-// is unreachable in this function, the set will be empty. This cannot happen
-// for reachable code, because every block dominates at least itself.
-//
+/// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
+/// function, that represents the blocks that dominate the block. If the block
+/// is unreachable in this function, the set will be empty. This cannot happen
+/// for reachable code, because every block dominates at least itself.
+///
struct DominatorSetBase : public DominatorBase {
typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
// Map of dom sets
/// isReachable - Return true if the specified basicblock is reachable. If
/// the block is reachable, we have dominator set information for it.
+ ///
bool isReachable(BasicBlock *BB) const {
return !getDominators(BB).empty();
}
}
/// print - Convert to human readable form
+ ///
virtual void print(std::ostream &OS) const;
/// dominates - Return true if A dominates B. This performs the special
/// addBasicBlock - Call to update the dominator set with information about a
/// new block that was inserted into the function.
+ ///
void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
assert(find(BB) == end() && "Block already in DominatorSet!");
Doms.insert(std::make_pair(BB, Dominators));
}
- // addDominator - If a new block is inserted into the CFG, then method may be
- // called to notify the blocks it dominates that it is in their set.
- //
+ /// addDominator - If a new block is inserted into the CFG, then method may be
+ /// called to notify the blocks it dominates that it is in their set.
+ ///
void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
iterator I = find(BB);
assert(I != end() && "BB is not in DominatorSet!");
//===-------------------------------------
-// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
-// compute a normal dominator set.
-//
+/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
+/// compute a normal dominator set.
+///
struct DominatorSet : public DominatorSetBase {
DominatorSet() : DominatorSetBase(false) {}
return Roots[0];
}
- // getAnalysisUsage - This simply provides a dominator set
+ /// getAnalysisUsage - This simply provides a dominator set
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<ImmediateDominators>();
AU.setPreservesAll();
//===----------------------------------------------------------------------===//
-//
-// DominatorTree - Calculate the immediate dominator tree for a function.
-//
+/// DominatorTree - Calculate the immediate dominator tree for a function.
+///
struct DominatorTreeBase : public DominatorBase {
class Node;
protected:
inline Node *getIDom() const { return IDom; }
inline const std::vector<Node*> &getChildren() const { return Children; }
- // dominates - Returns true iff this dominates N. Note that this is not a
- // constant time operation!
+ /// dominates - Returns true iff this dominates N. Note that this is not a
+ /// constant time operation!
+ ///
inline bool dominates(const Node *N) const {
const Node *IDom;
while ((IDom = N->getIDom()) != 0 && IDom != this)
- N = IDom; // Walk up the tree
+ N = IDom; // Walk up the tree
return IDom != 0;
}
private:
- inline Node(BasicBlock *BB, Node *iDom)
- : TheBB(BB), IDom(iDom) {}
+ inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
inline Node *addChild(Node *C) { Children.push_back(C); return C; }
void setIDom(Node *NewIDom);
return getNode(BB);
}
- // getRootNode - This returns the entry node for the CFG of the function. If
- // this tree represents the post-dominance relations for a function, however,
- // this root may be a node with the block == NULL. This is the case when
- // there are multiple exit nodes from a particular function. Consumers of
- // post-dominance information must be capable of dealing with this
- // possibility.
- //
+ /// getRootNode - This returns the entry node for the CFG of the function. If
+ /// this tree represents the post-dominance relations for a function, however,
+ /// this root may be a node with the block == NULL. This is the case when
+ /// there are multiple exit nodes from a particular function. Consumers of
+ /// post-dominance information must be capable of dealing with this
+ /// possibility.
+ ///
Node *getRootNode() { return RootNode; }
const Node *getRootNode() const { return RootNode; }
}
/// print - Convert to human readable form
+ ///
virtual void print(std::ostream &OS) const;
};
//===-------------------------------------
-// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
-// compute a normal dominator tree.
-//
+/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
+/// compute a normal dominator tree.
+///
struct DominatorTree : public DominatorTreeBase {
DominatorTree() : DominatorTreeBase(false) {}
};
//===-------------------------------------
-// DominatorTree GraphTraits specialization so the DominatorTree can be
-// iterable by generic graph iterators.
-
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
template <> struct GraphTraits<DominatorTree::Node*> {
typedef DominatorTree::Node NodeType;
typedef NodeType::iterator ChildIteratorType;
};
//===----------------------------------------------------------------------===//
-//
-// DominanceFrontier - Calculate the dominance frontiers for a function.
-//
+/// DominanceFrontier - Calculate the dominance frontiers for a function.
+///
struct DominanceFrontierBase : public DominatorBase {
typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
I->second.erase(Node);
}
- // print - Convert to human readable form
+ /// print - Convert to human readable form
+ ///
virtual void print(std::ostream &OS) const;
};
//===-------------------------------------
-// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
-// compute a normal dominator tree.
-//
+/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
+/// compute a normal dominator tree.
+///
struct DominanceFrontier : public DominanceFrontierBase {
DominanceFrontier() : DominanceFrontierBase(false) {}
struct ExprType;
-/// ClassifyExpr: Analyze an expression to determine the complexity of the
+/// ClassifyExpr - Analyze an expression to determine the complexity of the
/// expression, and which other values it depends on.
///
ExprType ClassifyExpr(Value *Expr);
-// ExprType - Represent an expression of the form CONST*VAR+CONST
-// or simpler. The expression form that yields the least information about the
-// expression is just the Linear form with no offset.
-//
+/// ExprType Class - Represent an expression of the form CONST*VAR+CONST
+/// or simpler. The expression form that yields the least information about the
+/// expression is just the Linear form with no offset.
+///
struct ExprType {
enum ExpressionType {
Constant, // Expr is a simple constant, Offset is value
ExprType(Value *Val); // Create a linear or constant expression
ExprType(const ConstantInt *scale, Value *var, const ConstantInt *offset);
- // If this expression has an intrinsic type, return it. If it is zero, return
- // the specified type.
- //
+ /// If this expression has an intrinsic type, return it. If it is zero,
+ /// return the specified type.
+ ///
const Type *getExprType(const Type *Default) const;
};
return UnsafeTypes;
}
- // run - Inspect the operations that the specified module does on
- // values of various types. If they are deemed to be 'unsafe' note that the
- // type is not safe to transform.
- //
+ /// run - Inspect the operations that the specified module does on
+ /// values of various types. If they are deemed to be 'unsafe' note that the
+ /// type is not safe to transform.
+ ///
virtual bool run(Module &M);
- // print - Loop over the results of the analysis, printing out unsafe types.
- //
+ /// print - Loop over the results of the analysis, printing out unsafe types.
+ ///
void print(std::ostream &o, const Module *Mod) const;
- // getAnalysisUsage - Of course, we provide ourself...
- //
+ /// getAnalysisUsage - Of course, we provide ourself...
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
}
class FunctionModRefInfo; // ModRefInfo for a func and all calls in it
class IPModRef; // Pass that computes IP Mod/Ref info
-//---------------------------------------------------------------------------
-// class ModRefInfo
-//
-// Purpose:
-// 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.
-//---------------------------------------------------------------------------
-
+//----------------------------------------------------------------------------
+/// 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) { }
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; }
//----------------------------------------------------------------------------
-// class FunctionModRefInfo
-//
-// 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].
-//----------------------------------------------------------------------------
-
+/// 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
friend class IPModRef;
- void computeModRef (const Function &func);
- void computeModRef (CallSite call);
- DSGraph *ResolveCallSiteModRefInfo(CallSite CS,
- hash_map<const DSNode*, DSNodeHandle> &NodeMap);
+ void computeModRef(const Function &func);
+ void computeModRef(CallSite call);
+ DSGraph*
+ ResolveCallSiteModRefInfo(CallSite CS,
+ hash_map<const DSNode*, DSNodeHandle> &NodeMap);
public:
- /* ctor */ FunctionModRefInfo (const Function& func,
- IPModRef& IPModRefObj,
- DSGraph* tdgClone);
- /* dtor */ ~FunctionModRefInfo ();
+ FunctionModRefInfo(const Function& func, IPModRef &IPModRefObj,
+ DSGraph* tdgClone);
+ ~FunctionModRefInfo();
// Identify the function and its relevant DS graph
//
- const Function& getFunction() const { return F; }
- const DSGraph& getFuncGraph() const { return *funcTDGraph; }
+ const Function& getFunction() const { return F; }
+ const DSGraph& getFuncGraph() const { return *funcTDGraph; }
// Retrieve Mod/Ref results for a single call site and for the function body
//
- const ModRefInfo* getModRefInfo (const Function& func) const {
+ const ModRefInfo* getModRefInfo(const Function& func) const {
return &funcModRefInfo;
}
- const ModRefInfo* getModRefInfo (const CallInst& callInst) const {
+ const ModRefInfo* getModRefInfo(const CallInst& callInst) const {
std::map<const Instruction*, ModRefInfo*>::const_iterator I =
callSiteModRefInfo.find((Instruction*)&callInst);
return (I == callSiteModRefInfo.end()) ? NULL : I->second;
}
- const ModRefInfo* getModRefInfo (const InvokeInst& II) const {
+ const ModRefInfo* getModRefInfo(const InvokeInst& II) const {
std::map<const Instruction*, ModRefInfo*>::const_iterator I =
callSiteModRefInfo.find((Instruction*)&II);
return (I == callSiteModRefInfo.end()) ? NULL : I->second;
// Get the nodeIds used to index all Mod/Ref information for current function
//
- unsigned getNodeId (const DSNode* node) const {
+ unsigned getNodeId(const DSNode* node) const {
std::map<const DSNode*, unsigned>::const_iterator iter = NodeIds.find(node);
assert(iter != NodeIds.end() && iter->second < funcModRefInfo.getSize());
return iter->second;
}
- unsigned getNodeId (const Value* value) const;
+ unsigned getNodeId(const Value* value) const;
// Debugging support methods
void print(std::ostream &O) const;
//----------------------------------------------------------------------------
-// class IPModRef
-//
-// Purpose:
-// An interprocedural pass that computes IP Mod/Ref info for functions and
-// for individual call sites.
-//
-// Given the DSGraph of a function, this class can be queried for
-// a ModRefInfo object describing all the nodes in the DSGraph that are
-// (a) modified, and (b) referenced during an execution of the function
-// from an arbitrary callsite, or during an execution of a single call-site
-// within the function.
-//----------------------------------------------------------------------------
-
+/// IPModRef Class - An interprocedural pass that computes IP Mod/Ref info for
+/// functions and for individual call sites.
+///
+/// Given the DSGraph of a function, this class can be queried for
+/// a ModRefInfo object describing all the nodes in the DSGraph that are
+/// (a) modified, and (b) referenced during an execution of the function
+/// from an arbitrary callsite, or during an execution of a single call-site
+/// within the function.
+///
class IPModRef : public Pass {
std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
Module* M;
FunctionModRefInfo& getFuncInfo(const Function& func,
bool computeIfMissing = false);
public:
- IPModRef() : M(NULL) { }
- ~IPModRef() { }
+ IPModRef() : M(NULL) {}
+ ~IPModRef() {}
- // Driver function to run IP Mod/Ref on a Module.
- // This initializes the module reference, and then computes IPModRef
- // results immediately if demand-driven analysis was *not* specified.
- //
+ /// run - Driver function to run IP Mod/Ref on a Module.
+ /// This initializes the module reference, and then computes IPModRef
+ /// results immediately if demand-driven analysis was *not* specified.
+ ///
virtual bool run(Module &M);
- // Retrieve the Mod/Ref information for a single function
- //
+ /// getFunctionModRefInfo - Retrieve the Mod/Ref information for a single
+ /// function
+ ///
const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
return getFuncInfo(func);
}
void print(std::ostream &O) const;
void dump() const;
- // Release memory held by this pass when the pass pipeline is done
- //
+ /// releaseMemory - Release memory held by this pass when the pass pipeline is
+ /// done
+ ///
virtual void releaseMemory();
- // getAnalysisUsage - This pass requires top-down data structure graphs.
- // It modifies nothing.
- //
+ /// getAnalysisUsage - This pass requires top-down data structure graphs.
+ /// It modifies nothing.
+ ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
};
-//===----------------------------------------------------------------------===//
-
} // End llvm namespace
#endif
class MemoryDepAnalysis : public Pass {
/// The following map and depGraph pointer are temporary until this class
- /// becomes a FunctionPass instead of a module Pass. */
+ /// becomes a FunctionPass instead of a module Pass.
hash_map<Function*, DependenceGraph*> funcMap;
DependenceGraph* funcDepGraph;
const FunctionModRefInfo* funcModRef;
/// Internal routine that processes each SCC of the CFG.
+ ///
void ProcessSCC(std::vector<BasicBlock*> &SCC, ModRefTable& ModRefAfter,
bool HasLoop);
~MemoryDepAnalysis();
/// Driver function to compute dependence graphs for every function.
+ ///
bool run(Module &M);
- /// getGraph() -- Retrieve the dependence graph for a function.
+ /// getGraph - Retrieve the dependence graph for a function.
/// This is temporary and will go away once this is a FunctionPass.
/// At that point, this class should directly inherit from DependenceGraph.
///
return *I->second;
}
const DependenceGraph& getGraph(Function& F) const {
- hash_map<Function*, DependenceGraph*>::const_iterator
- I = funcMap.find(&F);
+ hash_map<Function*, DependenceGraph*>::const_iterator I = funcMap.find(&F);
assert(I != funcMap.end());
return *I->second;
}
///
virtual void releaseMemory();
-
/// Driver functions to compute the Load/Store Dep. Graph per function.
///
bool runOnFunction(Function &F);
class DependenceGraph;
class PgmDependenceGraph;
-
-///---------------------------------------------------------------------------
-/// enum PDGIteratorFlags
-///
-/// These bit flags specify which dependences incident on a statement are to be
-/// enumerated: Memory deps, SSA deps, Control deps, or any combination thereof.
-///---------------------------------------------------------------------------
-
+//---------------------------------------------------------------------------
+/// enum PDGIteratorFlags - specify which dependences incident on a statement
+/// are to be enumerated: Memory deps, SSA deps, Control deps, or any
+/// combination thereof.
+///
enum PDGIteratorFlags {
MemoryDeps = 0x1, // load/store/call deps
SSADeps = 0x2, // SSA deps (true)
AllDeps = MemoryDeps | SSADeps | ControlDeps // shorthand for all three
};
-
-///---------------------------------------------------------------------------
-/// struct DepIterState
-///
-/// This data type is primarily an internal implementation detail.
+//---------------------------------------------------------------------------
+/// struct DepIterState - an internal implementation detail.
/// It are exposed here only to give inlinable access to field dep,
/// which is the representation for the current dependence pointed to by
/// a PgmDependenceGraph::iterator.
-///---------------------------------------------------------------------------
-
+///
class DepIterState {
private:
typedef char IterStateFlags;
PDGIteratorFlags depFlags:8; // which deps are we enumerating?
IterStateFlags iterFlags:8; // marking where the iter stands
- /*ctor*/ DepIterState (DependenceGraph* _memDepGraph,
- Instruction& I,
- bool incomingDeps,
- PDGIteratorFlags whichDeps);
+ DepIterState(DependenceGraph* _memDepGraph,
+ Instruction& I,
+ bool incomingDeps,
+ PDGIteratorFlags whichDeps);
- bool operator==(const DepIterState& S) {
+ bool operator==(const DepIterState& S) {
assert(memDepGraph == S.memDepGraph &&
"Incompatible iterators! This is a probable sign of something BAD.");
return (iterFlags == S.iterFlags &&
// Is the iteration completely done?
//
- bool done () const { return iterFlags & AllDone; }
+ bool done() const { return iterFlags & AllDone; }
- // Bump this iterator logically by 1 (to next dependence) and reset the
- // dep field to represent the new dependence if there is one.
- // Set done = true otherwise.
- //
- void Next ();
+ /// Next - Bump this iterator logically by 1 (to next dependence) and reset
+ /// the dep field to represent the new dependence if there is one.
+ /// Set done = true otherwise.
+ ///
+ void Next();
- // Find the first memory dependence for the current Mem In/Out iterators.
- // Sets dep to that dependence and returns true if one is found.
- // Returns false and leaves dep unchanged otherwise.
- //
- bool SetFirstMemoryDep();
+ /// SetFirstMemoryDep - Find the first memory dependence for the current Mem
+ /// In/Out iterators. Sets dep to that dependence and returns true if one is
+ /// found. Returns false and leaves dep unchanged otherwise.
+ ///
+ bool SetFirstMemoryDep();
- // Find the next valid data dependence for the current SSA In/Out iterators.
- // A valid data dependence is one that is to/from an Instruction.
- // E.g., an SSA edge from a formal parameter is not a valid dependence.
- // Sets dep to that dependence and returns true if a valid one is found.
- // Returns false and leaves dep unchanged otherwise.
- //
- bool SetFirstSSADep ();
+ /// SetFirstSSADep - Find the next valid data dependence for the current SSA
+ /// In/Out iterators. A valid data dependence is one that is to/from an
+ /// Instruction. E.g., an SSA edge from a formal parameter is not a valid
+ /// dependence. Sets dep to that dependence and returns true if a valid one is
+ /// found. Returns false and leaves dep unchanged otherwise.
+ ///
+ bool SetFirstSSADep();
};
-///---------------------------------------------------------------------------
-/// The dependence iterator class. This class represents a pointer to
-/// a single dependence in the program dependence graph. It is essentially
-/// like a pointer to an object of class Dependence but it is much more
-/// efficient to retrieve information about the dependence directly rather
-/// than constructing the equivalent Dependence object (since that object
-/// is normally not constructed for SSA def-use dependences).
-///---------------------------------------------------------------------------
-
+//---------------------------------------------------------------------------
+/// PDGIterator Class - represents a pointer to a single dependence in the
+/// program dependence graph. It is essentially like a pointer to an object of
+/// class Dependence but it is much more efficient to retrieve information about
+/// the dependence directly rather than constructing the equivalent Dependence
+/// object (since that object is normally not constructed for SSA def-use
+/// dependences).
+///
class PDGIterator: public forward_iterator<Dependence, ptrdiff_t> {
DepIterState* istate;
public:
typedef PDGIterator _Self;
- /*ctor*/ PDGIterator (DepIterState* _istate) : istate(_istate) { }
- /*dtor*/ ~PDGIterator () { delete istate; }
+ PDGIterator(DepIterState* _istate) : istate(_istate) {}
+ ~PDGIterator() { delete istate; }
- /*copy*/ PDGIterator (const PDGIterator& I)
- : istate(new DepIterState(*I.istate)) { }
+ PDGIterator(const PDGIterator& I) :istate(new DepIterState(*I.istate)) {}
- PDGIterator& operator= (const PDGIterator& I) {
+ PDGIterator& operator=(const PDGIterator& I) {
if (istate) delete istate;
istate = new DepIterState(*I.istate);
return *this;
}
- // Check if the iteration is complete
- //
- bool fini() const { return !istate || istate->done(); }
+ /// fini - check if the iteration is complete
+ ///
+ bool fini() const { return !istate || istate->done(); }
// Retrieve the underlying Dependence. Returns NULL if fini().
//
- Dependence* operator*() const { return fini() ? NULL : &istate->dep; }
- Dependence* operator->() const { assert(!fini()); return &istate->dep; }
+ Dependence* operator*() const { return fini() ? NULL : &istate->dep; }
+ Dependence* operator->() const { assert(!fini()); return &istate->dep; }
// Increment the iterator
//
- _Self& operator++() { if (!fini()) istate->Next(); return *this;}
- _Self& operator++(int); // do not implement!
+ _Self& operator++() { if (!fini()) istate->Next(); return *this;}
+ _Self& operator++(int); // do not implement!
// Equality comparison: a "null" state should compare equal to done
// This is efficient for comparing with "end" or with itself, but could
// be quite inefficient for other cases.
//
- bool operator==(const PDGIterator& I) const {
+ bool operator==(const PDGIterator& I) const {
if (I.istate == NULL) // most common case: iter == end()
return (istate == NULL || istate->done());
if (istate == NULL)
return (I.istate == NULL || I.istate->done());
return (*istate == *I.istate);
}
- bool operator!=(const PDGIterator& I) const {
+ bool operator!=(const PDGIterator& I) const {
return ! (*this == I);
}
};
// print helper function.
void printOutgoingSSADeps(Instruction& I, std::ostream &O);
- // MakeIterator --
- // The first version creates and initializes an iterator as specified.
- // The second version creates a null iterator representing end-of-iteration.
- //
- PDGIterator MakeIterator (Instruction& I,
- bool incomingDeps,
- PDGIteratorFlags whichDeps);
+ /// MakeIterator - creates and initializes an iterator as specified.
+ ///
+ PDGIterator MakeIterator(Instruction& I,
+ bool incomingDeps,
+ PDGIteratorFlags whichDeps);
- PDGIterator MakeIterator () { return PDGIterator(NULL); }
+ /// MakeIterator - creates a null iterator representing end-of-iteration.
+ ///
+ PDGIterator MakeIterator() { return PDGIterator(NULL); }
friend class PDGIterator;
friend class DepIterState;
/* typedef PDGIterator<const Dependence> const iterator; */
public:
- PgmDependenceGraph() : memDepGraph(NULL) { }
- ~PgmDependenceGraph() { }
+ PgmDependenceGraph() : memDepGraph(NULL) {}
+ ~PgmDependenceGraph() {}
/// Iterators to enumerate the program dependence graph for a function.
/// Note that this does not provide "end" iterators to check for completion.
/// Instead, just use iterator::fini() or iterator::operator*() == NULL
- //
+ ///
iterator inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
return MakeIterator(I, /*inDeps*/ true, whichDeps);
}
return MakeIterator();
}
- ///------------------------------------------------------------------------
+ //------------------------------------------------------------------------
/// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
/// These functions will go away once this class becomes a FunctionPass.
void dump() const;
};
-//===----------------------------------------------------------------------===//
-
} // End llvm namespace
#endif
projects / oota-llvm.git / commitdiff