[analyzer] Re-apply r170826 and make the dumping of the GallGraph

deterministic.

Commit message for r170826:

[analyzer] Traverse the Call Graph in topological order.

Modify the call graph by removing the parentless nodes. Instead all
nodes are children of root to ensure they are all reachable. Remove the
tracking of nodes that are "top level" or global. This information is
not used and can be obtained from the Decls stored inside
CallGraphNodes.

Instead of existing ordering hacks, analyze the functions in topological
order over the Call Graph.

Together with the addition of devirtualizable ObjC message sends and
blocks to the call graph, this gives around 6% performance improvement
on several large ObjC benchmarks.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@170906 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 2 insertions, 15 deletions

diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h
index d554f3a7af..998076d1e1 100644
--- a/include/clang/Analysis/CallGraph.h
+++ b/include/clang/Analysis/CallGraph.h
@@ -39,15 +39,9 @@ class CallGraph : public RecursiveASTVisitor<CallGraph> {
   /// FunctionMap owns all CallGraphNodes.
   FunctionMapTy FunctionMap;
 
-  /// This is a virtual root node that has edges to all the global functions -
-  /// 'main' or functions accessible from other translation units.
+  /// This is a virtual root node that has edges to all the functions.
   CallGraphNode *Root;
 
-  /// The list of nodes that have no parent. These are unreachable from Root.
-  /// Declarations can get to this list due to impressions in the graph, for
-  /// example, we do not track functions whose addresses were taken.
-  llvm::SetVector<CallGraphNode *> ParentlessNodes;
-
 public:
   CallGraph();
   ~CallGraph();
@@ -91,12 +85,6 @@ public:
   /// failing to add a call edge due to the analysis imprecision.
   typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
   typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
-  nodes_iterator parentless_begin() { return ParentlessNodes.begin(); }
-  nodes_iterator parentless_end() { return ParentlessNodes.end(); }
-  const_nodes_iterator
-    parentless_begin() const { return ParentlessNodes.begin(); }
-  const_nodes_iterator
-    parentless_end() const { return ParentlessNodes.end(); }
 
   void print(raw_ostream &os) const;
   void dump() const;
@@ -170,7 +158,6 @@ public:
 
   void addCallee(CallGraphNode *N, CallGraph *CG) {
     CalledFunctions.push_back(N);
-    CG->ParentlessNodes.remove(N);
   }
 
   Decl *getDecl() const { return FD; }
@@ -206,7 +193,7 @@ template <> struct GraphTraits<const clang::CallGraphNode*> {
   typedef NodeType::const_iterator ChildIteratorType;
   static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
-  static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
+  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 
 template <> struct GraphTraits<clang::CallGraph*>