#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
/// be scanned for "calls" or uses of functions and its child information
/// will be constructed. All of these results are accumulated and cached in
/// the graph.
- class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
- ptrdiff_t, Node *, Node *> {
+ class iterator
+ : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator,
+ std::random_access_iterator_tag, Node> {
friend class LazyCallGraph;
friend class LazyCallGraph::Node;
- typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
- Node *, Node *> BaseT;
-
- /// \brief Nonce type to select the constructor for the end iterator.
- struct IsAtEndT {};
LazyCallGraph *G;
NodeVectorImplT::iterator NI;
- // Build the begin iterator for a node.
- explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
- : G(&G), NI(Nodes.begin()) {}
-
- // Build the end iterator for a node. This is selected purely by overload.
- iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
- : G(&G), NI(Nodes.end()) {}
+ // Build the iterator for a specific position in a node list.
+ iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI)
+ : iterator_adaptor_base(NI), G(&G) {}
public:
- bool operator==(const iterator &Arg) const { return NI == Arg.NI; }
- bool operator!=(const iterator &Arg) const { return !operator==(Arg); }
+ iterator() {}
reference operator*() const {
- if (NI->is<Node *>())
- return NI->get<Node *>();
+ if (I->is<Node *>())
+ return *I->get<Node *>();
- Function *F = NI->get<Function *>();
- Node *ChildN = G->get(*F);
- *NI = ChildN;
+ Function *F = I->get<Function *>();
+ Node &ChildN = G->get(*F);
+ *I = &ChildN;
return ChildN;
}
- pointer operator->() const { return operator*(); }
-
- iterator &operator++() {
- ++NI;
- return *this;
- }
- iterator operator++(int) {
- iterator prev = *this;
- ++*this;
- return prev;
- }
-
- iterator &operator--() {
- --NI;
- return *this;
- }
- iterator operator--(int) {
- iterator next = *this;
- --*this;
- return next;
- }
};
/// \brief A node in the call graph.
/// CalleeIndexMap.
Node(LazyCallGraph &G, Function &F);
+ /// \brief Internal helper to insert a callee.
+ void insertEdgeInternal(Function &Callee);
+
+ /// \brief Internal helper to remove a callee from this node.
+ void removeEdgeInternal(Function &Callee);
+
public:
typedef LazyCallGraph::iterator iterator;
return F;
};
- iterator begin() const { return iterator(*G, Callees); }
- iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
+ iterator begin() const { return iterator(*G, Callees.begin()); }
+ iterator end() const { return iterator(*G, Callees.end()); }
/// Equality is defined as address equality.
bool operator==(const Node &N) const { return this == &N; }
friend class LazyCallGraph;
friend class LazyCallGraph::Node;
- SmallSetVector<SCC *, 1> ParentSCCs;
+ LazyCallGraph *G;
+ SmallPtrSet<SCC *, 1> ParentSCCs;
SmallVector<Node *, 1> Nodes;
- SmallPtrSet<Function *, 1> NodeSet;
- SCC() {}
+ SCC(LazyCallGraph &G) : G(&G) {}
+
+ void insert(Node &N);
+
+ void
+ internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
+ SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
+ SmallVectorImpl<SCC *> &ResultSCCs);
public:
typedef SmallVectorImpl<Node *>::const_iterator iterator;
+ typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
iterator begin() const { return Nodes.begin(); }
iterator end() const { return Nodes.end(); }
+
+ parent_iterator parent_begin() const { return ParentSCCs.begin(); }
+ parent_iterator parent_end() const { return ParentSCCs.end(); }
+
+ iterator_range<parent_iterator> parents() const {
+ return iterator_range<parent_iterator>(parent_begin(), parent_end());
+ }
+
+ ///@{
+ /// \name Mutation API
+ ///
+ /// These methods provide the core API for updating the call graph in the
+ /// presence of a (potentially still in-flight) DFS-found SCCs.
+ ///
+ /// Note that these methods sometimes have complex runtimes, so be careful
+ /// how you call them.
+
+ /// \brief Remove an edge whose source is in this SCC and target is *not*.
+ ///
+ /// This removes an inter-SCC edge. All inter-SCC edges originating from
+ /// this SCC have been fully explored by any in-flight DFS SCC formation,
+ /// so this is always safe to call once you have the source SCC.
+ ///
+ /// This operation does not change the set of SCCs or the members of the
+ /// SCCs and so is very inexpensive. It may change the connectivity graph
+ /// of the SCCs though, so be careful calling this while iterating over
+ /// them.
+ void removeInterSCCEdge(Node &CallerN, Node &CalleeN);
+
+ /// \brief Remove an edge which is entirely within this SCC.
+ ///
+ /// Both the \a Caller and the \a Callee must be within this SCC. Removing
+ /// such an edge make break cycles that form this SCC and thus this
+ /// operation may change the SCC graph significantly. In particular, this
+ /// operation will re-form new SCCs based on the remaining connectivity of
+ /// the graph. The following invariants are guaranteed to hold after
+ /// calling this method:
+ ///
+ /// 1) This SCC is still an SCC in the graph.
+ /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
+ /// preserved as the root of any new SCC directed graph formed.
+ /// 3) No SCC other than this SCC has its member set changed (this is
+ /// inherent in the definiton of removing such an edge).
+ /// 4) All of the parent links of the SCC graph will be updated to reflect
+ /// the new SCC structure.
+ /// 5) All SCCs formed out of this SCC, excluding this SCC, will be
+ /// returned in a vector.
+ /// 6) The order of the SCCs in the vector will be a valid postorder
+ /// traversal of the new SCCs.
+ ///
+ /// These invariants are very important to ensure that we can build
+ /// optimization pipeliens on top of the CGSCC pass manager which
+ /// intelligently update the SCC graph without invalidating other parts of
+ /// the SCC graph.
+ ///
+ /// The runtime complexity of this method is, in the worst case, O(V+E)
+ /// where V is the number of nodes in this SCC and E is the number of edges
+ /// leaving the nodes in this SCC. Note that E includes both edges within
+ /// this SCC and edges from this SCC to child SCCs. Some effort has been
+ /// made to minimize the overhead of common cases such as self-edges and
+ /// edge removals which result in a spanning tree with no more cycles.
+ SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN);
+
+ ///@}
};
/// \brief A post-order depth-first SCC iterator over the call graph.
/// always visits SCCs for a callee prior to visiting the SCC for a caller
/// (when they are in different SCCs).
class postorder_scc_iterator
- : public std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t, SCC *,
- SCC *> {
+ : public iterator_facade_base<postorder_scc_iterator,
+ std::forward_iterator_tag, SCC> {
friend class LazyCallGraph;
friend class LazyCallGraph::Node;
- typedef std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t,
- SCC *, SCC *> BaseT;
/// \brief Nonce type to select the constructor for the end iterator.
struct IsAtEndT {};
bool operator==(const postorder_scc_iterator &Arg) const {
return G == Arg.G && C == Arg.C;
}
- bool operator!=(const postorder_scc_iterator &Arg) const {
- return !operator==(Arg);
- }
- reference operator*() const { return C; }
- pointer operator->() const { return operator*(); }
+ reference operator*() const { return *C; }
+ using iterator_facade_base::operator++;
postorder_scc_iterator &operator++() {
C = G->getNextSCCInPostOrder();
return *this;
}
- postorder_scc_iterator operator++(int) {
- postorder_scc_iterator prev = *this;
- ++*this;
- return prev;
- }
};
/// \brief Construct a graph for the given module.
LazyCallGraph(LazyCallGraph &&G);
LazyCallGraph &operator=(LazyCallGraph &&RHS);
- iterator begin() { return iterator(*this, EntryNodes); }
- iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
+ iterator begin() { return iterator(*this, EntryNodes.begin()); }
+ iterator end() { return iterator(*this, EntryNodes.end()); }
postorder_scc_iterator postorder_scc_begin() {
return postorder_scc_iterator(*this);
/// added.
Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
+ /// \brief Lookup a function's SCC in the graph.
+ ///
+ /// \returns null if the function hasn't been assigned an SCC via the SCC
+ /// iterator walk.
+ SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
+
/// \brief Get a graph node for a given function, scanning it to populate the
/// graph data as necessary.
- Node *get(Function &F) {
+ Node &get(Function &F) {
Node *&N = NodeMap[&F];
if (N)
- return N;
+ return *N;
return insertInto(F, N);
}
+ ///@{
+ /// \name Pre-SCC Mutation API
+ ///
+ /// These methods are only valid to call prior to forming any SCCs for this
+ /// call graph. They can be used to update the core node-graph during
+ /// a node-based inorder traversal that precedes any SCC-based traversal.
+ ///
+ /// Once you begin manipulating a call graph's SCCs, you must perform all
+ /// mutation of the graph via the SCC methods.
+
+ /// \brief Update the call graph after inserting a new edge.
+ void insertEdge(Node &Caller, Function &Callee);
+
+ /// \brief Update the call graph after inserting a new edge.
+ void insertEdge(Function &Caller, Function &Callee) {
+ return insertEdge(get(Caller), Callee);
+ }
+
+ /// \brief Update the call graph after deleting an edge.
+ void removeEdge(Node &Caller, Function &Callee);
+
+ /// \brief Update the call graph after deleting an edge.
+ void removeEdge(Function &Caller, Function &Callee) {
+ return removeEdge(get(Caller), Callee);
+ }
+
+ ///@}
+
private:
/// \brief Allocator that holds all the call graph nodes.
SpecificBumpPtrAllocator<Node> BPA;
SpecificBumpPtrAllocator<SCC> SCCBPA;
/// \brief Maps Function -> SCC for fast lookup.
- DenseMap<const Function *, SCC *> SCCMap;
+ DenseMap<Node *, SCC *> SCCMap;
/// \brief The leaf SCCs of the graph.
///
/// These are all of the SCCs which have no children.
SmallVector<SCC *, 4> LeafSCCs;
- /// \brief Stack of nodes not-yet-processed into SCCs.
+ /// \brief Stack of nodes in the DFS walk.
SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
/// \brief Set of entry nodes not-yet-processed into SCCs.
- SmallSetVector<Function *, 4> SCCEntryNodes;
+ SmallVector<Function *, 4> SCCEntryNodes;
+
+ /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
+ SmallVector<Node *, 4> PendingSCCStack;
/// \brief Counter for the next DFS number to assign.
int NextDFSNumber;
/// \brief Helper to insert a new function, with an already looked-up entry in
/// the NodeMap.
- Node *insertInto(Function &F, Node *&MappedN);
+ Node &insertInto(Function &F, Node *&MappedN);
/// \brief Helper to update pointers back to the graph object during moves.
void updateGraphPtrs();
/// \brief Helper to form a new SCC out of the top of a DFSStack-like
/// structure.
- SCC *formSCCFromDFSStack(
- SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack);
+ SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
/// \brief Retrieve the next node in the post-order SCC walk of the call graph.
SCC *getNextSCCInPostOrder();
projects / oota-llvm.git / blobdiff