X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FLazyCallGraph.h;h=7cbc40f768ebcc4a90efe32f1995d799e1ec6211;hb=2b762697564ca1e12e0e974e93ceeb4c3420505c;hp=99e6fc25d9905460e4992d1a779985f947de0838;hpb=b9acdb79a5792a20b6b749a532ee0c347cf4d915;p=oota-llvm.git diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index 99e6fc25d99..7cbc40f768e 100644 --- a/include/llvm/Analysis/LazyCallGraph.h +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -32,8 +32,8 @@ /// //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH -#define LLVM_ANALYSIS_LAZY_CALL_GRAPH +#ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H +#define LLVM_ANALYSIS_LAZYCALLGRAPH_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PointerUnion.h" @@ -46,11 +46,11 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Function.h" #include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include namespace llvm { -class ModuleAnalysisManager; class PreservedAnalyses; class raw_ostream; @@ -113,21 +113,34 @@ public: /// 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 iterator_adaptor_base< - iterator, NodeVectorImplT::iterator, Node> { + class iterator + : public iterator_adaptor_base { friend class LazyCallGraph; friend class LazyCallGraph::Node; LazyCallGraph *G; - NodeVectorImplT::iterator NI; + NodeVectorImplT::iterator E; // Build the iterator for a specific position in a node list. - iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI) - : iterator_adaptor_base(NI), G(&G) {} + iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI, + NodeVectorImplT::iterator E) + : iterator_adaptor_base(NI), G(&G), E(E) { + while (I != E && I->isNull()) + ++I; + } public: iterator() {} + using iterator_adaptor_base::operator++; + iterator &operator++() { + do { + ++I; + } while (I != E && I->isNull()); + return *this; + } + reference operator*() const { if (I->is()) return *I->get(); @@ -163,15 +176,26 @@ public: /// CalleeIndexMap. Node(LazyCallGraph &G, Function &F); + /// \brief Internal helper to insert a callee. + void insertEdgeInternal(Function &Callee); + + /// \brief Internal helper to insert a callee. + void insertEdgeInternal(Node &CalleeN); + + /// \brief Internal helper to remove a callee from this node. + void removeEdgeInternal(Function &Callee); + public: typedef LazyCallGraph::iterator iterator; Function &getFunction() const { return F; - }; + } - iterator begin() const { return iterator(*G, Callees.begin()); } - iterator end() const { return iterator(*G, Callees.end()); } + iterator begin() const { + return iterator(*G, Callees.begin(), Callees.end()); + } + iterator end() const { return iterator(*G, Callees.end(), Callees.end()); } /// Equality is defined as address equality. bool operator==(const Node &N) const { return this == &N; } @@ -187,25 +211,19 @@ public: friend class LazyCallGraph; friend class LazyCallGraph::Node; + LazyCallGraph *G; SmallPtrSet ParentSCCs; SmallVector Nodes; - SCC() {} - - void insert(LazyCallGraph &G, Node &N); + SCC(LazyCallGraph &G) : G(&G) {} - void removeEdge(LazyCallGraph &G, Function &Caller, Function &Callee, - SCC &CalleeC); + void insert(Node &N); void - internalDFS(LazyCallGraph &G, - SmallVectorImpl> &DFSStack, + internalDFS(SmallVectorImpl> &DFSStack, SmallVectorImpl &PendingSCCStack, Node *N, SmallVectorImpl &ResultSCCs); - SmallVector - removeInternalEdge(LazyCallGraph &G, Node &Caller, Node &Callee); - public: typedef SmallVectorImpl::const_iterator iterator; typedef pointee_iterator::const_iterator> parent_iterator; @@ -219,6 +237,113 @@ public: iterator_range parents() const { return iterator_range(parent_begin(), parent_end()); } + + /// \brief Test if this SCC is a parent of \a C. + bool isParentOf(const SCC &C) const { return C.isChildOf(*this); } + + /// \brief Test if this SCC is an ancestor of \a C. + bool isAncestorOf(const SCC &C) const { return C.isDescendantOf(*this); } + + /// \brief Test if this SCC is a child of \a C. + bool isChildOf(const SCC &C) const { + return ParentSCCs.count(const_cast(&C)); + } + + /// \brief Test if this SCC is a descendant of \a C. + bool isDescendantOf(const SCC &C) const; + + /// \brief Short name useful for debugging or logging. + /// + /// We use the name of the first function in the SCC to name the SCC for + /// the purposes of debugging and logging. + StringRef getName() const { return (*begin())->getFunction().getName(); } + + ///@{ + /// \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 Insert an edge from one node in this SCC to another in this SCC. + /// + /// By the definition of an SCC, this does not change the nature or make-up + /// of any SCCs. + void insertIntraSCCEdge(Node &CallerN, Node &CalleeN); + + /// \brief Insert an edge whose tail is in this SCC and head is in some + /// child SCC. + /// + /// There must be an existing path from the caller to the callee. This + /// operation is inexpensive and does not change the set of SCCs in the + /// graph. + void insertOutgoingEdge(Node &CallerN, Node &CalleeN); + + /// \brief Insert an edge whose tail is in a descendant SCC and head is in + /// this SCC. + /// + /// There must be an existing path from the callee to the caller in this + /// case. NB! This is has the potential to be a very expensive function. It + /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs + /// to resolve that cycle. But finding all of the SCCs which participate in + /// the cycle can in the worst case require traversing every SCC in the + /// graph. Every attempt is made to avoid that, but passes must still + /// exercise caution calling this routine repeatedly. + /// + /// FIXME: We could possibly optimize this quite a bit for cases where the + /// caller and callee are very nearby in the graph. See comments in the + /// implementation for details, but that use case might impact users. + SmallVector insertIncomingEdge(Node &CallerN, Node &CalleeN); + + /// \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 definition 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 removeIntraSCCEdge(Node &CallerN, Node &CalleeN); + + ///@} }; /// \brief A post-order depth-first SCC iterator over the call graph. @@ -228,7 +353,8 @@ public: /// 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 { + : public iterator_facade_base { friend class LazyCallGraph; friend class LazyCallGraph::Node; @@ -251,22 +377,14 @@ public: 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*(); } + 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. @@ -279,8 +397,10 @@ public: LazyCallGraph(LazyCallGraph &&G); LazyCallGraph &operator=(LazyCallGraph &&RHS); - iterator begin() { return iterator(*this, EntryNodes.begin()); } - iterator end() { return iterator(*this, EntryNodes.end()); } + iterator begin() { + return iterator(*this, EntryNodes.begin(), EntryNodes.end()); + } + iterator end() { return iterator(*this, EntryNodes.end(), EntryNodes.end()); } postorder_scc_iterator postorder_scc_begin() { return postorder_scc_iterator(*this); @@ -314,6 +434,24 @@ public: 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); @@ -322,6 +460,8 @@ public: return removeEdge(get(Caller), Callee); } + ///@} + private: /// \brief Allocator that holds all the call graph nodes. SpecificBumpPtrAllocator BPA; @@ -403,11 +543,13 @@ public: static void *ID() { return (void *)&PassID; } - /// \brief Compute the \c LazyCallGraph for a the module \c M. + static StringRef name() { return "Lazy CallGraph Analysis"; } + + /// \brief Compute the \c LazyCallGraph for the module \c M. /// /// This just builds the set of entry points to the call graph. The rest is /// built lazily as it is walked. - LazyCallGraph run(Module *M) { return LazyCallGraph(*M); } + LazyCallGraph run(Module &M) { return LazyCallGraph(M); } private: static char PassID; @@ -422,7 +564,7 @@ class LazyCallGraphPrinterPass { public: explicit LazyCallGraphPrinterPass(raw_ostream &OS); - PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM); static StringRef name() { return "LazyCallGraphPrinterPass"; } };