[analyzer] Change the order in which we analyze the functions under

inlining to be the reverse of their declaration.

This optimizes running time under inlining up to 20% since we do not
re-analyze the utility functions which are usually defined first in the
translation unit if they have already been analyzed while inlined into
the root functions.

llvm-svn: 152653

3 files changed, 23 insertions, 19 deletions

diff --git a/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp b/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
index e8903804f91..5cf9e31c5b0 100644
--- a/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
+++ b/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
@@ -272,21 +272,25 @@ void AnalysisConsumer::HandleDeclsGallGraph(TranslationUnitDecl *TU) {
   // Find the top level nodes - children of root + the unreachable (parentless)
   // nodes.
   llvm::SmallVector<CallGraphNode*, 24> TopLevelFunctions;
+  for (CallGraph::nodes_iterator TI = CG.parentless_begin(),
+                                 TE = CG.parentless_end(); TI != TE; ++TI) {
+    TopLevelFunctions.push_back(*TI);
+    NumFunctionTopLevel++;
+  }
   CallGraphNode *Entry = CG.getRoot();
   for (CallGraphNode::iterator I = Entry->begin(),
                                E = Entry->end(); I != E; ++I) {
     TopLevelFunctions.push_back(*I);
     NumFunctionTopLevel++;
   }
-  for (CallGraph::nodes_iterator TI = CG.parentless_begin(),
-                                 TE = CG.parentless_end(); TI != TE; ++TI) {
-    TopLevelFunctions.push_back(*TI);
-    NumFunctionTopLevel++;
-  }
 
+  // Make sure the nodes are sorted in order reverse of their definition in the 
+  // translation unit. This step is very important for performance. It ensures 
+  // that we analyze the root functions before the externally available 
+  // subroutines.
   std::queue<CallGraphNode*> BFSQueue;
-  for (llvm::SmallVector<CallGraphNode*, 24>::iterator
-         TI = TopLevelFunctions.begin(), TE = TopLevelFunctions.end();
+  for (llvm::SmallVector<CallGraphNode*, 24>::reverse_iterator
+         TI = TopLevelFunctions.rbegin(), TE = TopLevelFunctions.rend();
          TI != TE; ++TI)
     BFSQueue.push(*TI);
 
diff --git a/clang/test/Analysis/inline-unique-reports.c b/clang/test/Analysis/inline-unique-reports.c
index 1cc3130c477..83df2d84de0 100644
--- a/clang/test/Analysis/inline-unique-reports.c
+++ b/clang/test/Analysis/inline-unique-reports.c
@@ -34,12 +34,12 @@ void test_bug_2() {
 // CHECK:         <key>start</key>
 // CHECK:          <array>
 // CHECK:           <dict>
-// CHECK:            <key>line</key><integer>9</integer>
+// CHECK:            <key>line</key><integer>14</integer>
 // CHECK:            <key>col</key><integer>3</integer>
 // CHECK:            <key>file</key><integer>0</integer>
 // CHECK:           </dict>
 // CHECK:           <dict>
-// CHECK:            <key>line</key><integer>9</integer>
+// CHECK:            <key>line</key><integer>14</integer>
 // CHECK:            <key>col</key><integer>3</integer>
 // CHECK:            <key>file</key><integer>0</integer>
 // CHECK:           </dict>
@@ -47,12 +47,12 @@ void test_bug_2() {
 // CHECK:         <key>end</key>
 // CHECK:          <array>
 // CHECK:           <dict>
-// CHECK:            <key>line</key><integer>10</integer>
+// CHECK:            <key>line</key><integer>15</integer>
 // CHECK:            <key>col</key><integer>3</integer>
 // CHECK:            <key>file</key><integer>0</integer>
 // CHECK:           </dict>
 // CHECK:           <dict>
-// CHECK:            <key>line</key><integer>10</integer>
+// CHECK:            <key>line</key><integer>15</integer>
 // CHECK:            <key>col</key><integer>3</integer>
 // CHECK:            <key>file</key><integer>0</integer>
 // CHECK:           </dict>
@@ -64,7 +64,7 @@ void test_bug_2() {
 // CHECK:      <key>kind</key><string>event</string>
 // CHECK:      <key>location</key>
 // CHECK:      <dict>
-// CHECK:       <key>line</key><integer>10</integer>
+// CHECK:       <key>line</key><integer>15</integer>
 // CHECK:       <key>col</key><integer>3</integer>
 // CHECK:       <key>file</key><integer>0</integer>
 // CHECK:      </dict>
@@ -72,12 +72,12 @@ void test_bug_2() {
 // CHECK:      <array>
 // CHECK:        <array>
 // CHECK:         <dict>
-// CHECK:          <key>line</key><integer>10</integer>
+// CHECK:          <key>line</key><integer>15</integer>
 // CHECK:          <key>col</key><integer>3</integer>
 // CHECK:          <key>file</key><integer>0</integer>
 // CHECK:         </dict>
 // CHECK:         <dict>
-// CHECK:          <key>line</key><integer>10</integer>
+// CHECK:          <key>line</key><integer>15</integer>
 // CHECK:          <key>col</key><integer>8</integer>
 // CHECK:          <key>file</key><integer>0</integer>
 // CHECK:         </dict>
diff --git a/clang/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m b/clang/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
index 96bc7a9b3e7..7c46426a815 100644
--- a/clang/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
+++ b/clang/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
@@ -80,16 +80,16 @@ int handleVoidInComma() {
 int marker(void) { // control reaches end of non-void function
 }
 
-
-// CHECK-darwin8: warning: The receiver of message 'longDoubleM' is nil and returns a value of type 'long double' that will be garbage
 // CHECK-darwin8: warning: The receiver of message 'longlongM' is nil and returns a value of type 'long long' that will be garbage
-// CHECK-darwin8: warning: The receiver of message 'doubleM' is nil and returns a value of type 'double' that will be garbage
 // CHECK-darwin8: warning: The receiver of message 'unsignedLongLongM' is nil and returns a value of type 'unsigned long long' that will be garbage
+// CHECK-darwin8: warning: The receiver of message 'doubleM' is nil and returns a value of type 'double' that will be garbage
 // CHECK-darwin8: warning: The receiver of message 'longlongM' is nil and returns a value of type 'long long' that will be garbage
-// CHECK-darwin9-NOT: warning: The receiver of message 'longDoubleM' is nil and returns a value of type 'long double' that will be garbage
+// CHECK-darwin8: warning: The receiver of message 'longDoubleM' is nil and returns a value of type 'long double' that will be garbage
+
 // CHECK-darwin9-NOT: warning: The receiver of message 'longlongM' is nil and returns a value of type 'long long' that will be garbage
-// CHECK-darwin9-NOT: warning: The receiver of message 'doubleM' is nil and returns a value of type 'double' that will be garbage
 // CHECK-darwin9-NOT: warning: The receiver of message 'unsignedLongLongM' is nil and returns a value of type 'unsigned long long' that will be garbage
+// CHECK-darwin9-NOT: warning: The receiver of message 'doubleM' is nil and returns a value of type 'double' that will be garbage
 // CHECK-darwin9-NOT: warning: The receiver of message 'longlongM' is nil and returns a value of type 'long long' that will be garbage
+// CHECK-darwin9-NOT: warning: The receiver of message 'longDoubleM' is nil and returns a value of type 'long double' that will be garbage
 // CHECK-darwin9: 1 warning generated