Fix typos in comments, NFC

[oota-llvm.git] / include / llvm / Analysis / LazyCallGraph.h

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index e5dd5cc2caa083a6fea35c6c609b6328ba0b1342..9a59844d6720eb7534def33d8743b490d9aef9ff 100644 (file)
--- 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"
@@ -238,6 +238,20 @@ public:
       return iterator_range<parent_iterator>(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<SCC *>(&C));
+    }
+
+    /// \brief Test if this SCC is a descendant of \a C.
+    bool isDescendantOf(const SCC &C) const;
+
     ///@{
     /// \name Mutation API
     ///
@@ -253,6 +267,30 @@ public:
     /// 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<SCC *, 1> 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
@@ -278,7 +316,7 @@ public:
     /// 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).
+    ///    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
@@ -499,7 +537,7 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
-  /// \brief Compute the \c LazyCallGraph for a the module \c M.
+  /// \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.