Fix subtle bug in AnalysisConsumer where we would not analyze functions whose parent

in the call graph had been inlined but for whatever reason we did not inline some
of its callees.

Also, fix a related traversal bug where we meant to do a BFS of the callgraph but
instead were doing a DFS.

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

3 files changed, 173 insertions, 55 deletions

diff --git a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
index 76e102c06a..05fb0155f1 100644
--- a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
+++ b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
@@ -22,6 +22,7 @@
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/CallGraph.h"
+#include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/StaticAnalyzer/Frontend/CheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Checkers/LocalCheckers.h"
@@ -347,7 +348,7 @@ void AnalysisConsumer::HandleDeclsGallGraph(const unsigned LocalTUDeclsSize) {
   for (llvm::SmallVector<CallGraphNode*, 24>::reverse_iterator
          TI = TopLevelFunctions.rbegin(), TE = TopLevelFunctions.rend();
          TI != TE; ++TI)
-    BFSQueue.push_front(*TI);
+    BFSQueue.push_back(*TI);
 
   // BFS over all of the functions, while skipping the ones inlined into
   // the previously processed functions. Use external Visited set, which is
@@ -357,6 +358,13 @@ void AnalysisConsumer::HandleDeclsGallGraph(const unsigned LocalTUDeclsSize) {
     CallGraphNode *N = BFSQueue.front();
     BFSQueue.pop_front();
 
+    // Push the children into the queue.
+    for (CallGraphNode::const_iterator CI = N->begin(),
+         CE = N->end(); CI != CE; ++CI) {
+      if (!Visited.count(*CI))
+        BFSQueue.push_back(*CI);
+    }
+
     // Skip the functions which have been processed already or previously
     // inlined.
     if (Visited.count(N))
@@ -377,12 +385,6 @@ void AnalysisConsumer::HandleDeclsGallGraph(const unsigned LocalTUDeclsSize) {
         Visited.insert(VN);
     }
     Visited.insert(N);
-
-    // Push the children into the queue.
-    for (CallGraphNode::const_iterator CI = N->begin(),
-                                       CE = N->end(); CI != CE; ++CI) {
-      BFSQueue.push_front(*CI);
-    }
   }
 }
 
diff --git a/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m b/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
index 7cf2aee35f..e4d5aaf82b 100644
--- a/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
+++ b/test/Analysis/nil-receiver-undefined-larger-than-voidptr-ret.m
@@ -80,11 +80,11 @@ 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-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 'unsignedLongLongM' is nil and returns a value of type 'unsigned long long' that will be garbage
diff --git a/test/Analysis/traversal-algorithm.mm b/test/Analysis/traversal-algorithm.mm
index 49e72249e0..e8a36eafc7 100644
--- a/test/Analysis/traversal-algorithm.mm
+++ b/test/Analysis/traversal-algorithm.mm
@@ -23,43 +23,6 @@ void test(id input) {
     work();
 }
 
-// This ordering assumes that true cases happen before the false cases.
-
-// BFS: 10 IfStmt
-// BFS-NEXT: 11 IfStmt
-// BFS-NEXT: 16 IfStmt
-// BFS-NEXT: 22 IfStmt
-// BFS-NEXT: 22 IfStmt
-// BFS-NEXT: 22 IfStmt
-// BFS-NEXT: 22 IfStmt
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-// BFS-NEXT: --END PATH--
-
-// And this ordering assumes that false cases happen before the true cases.
-
-// DFS: 10 IfStmt
-// DFS-NEXT: 16 IfStmt
-// DFS-NEXT: 22 IfStmt
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: 22 IfStmt
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: 11 IfStmt
-// DFS-NEXT: 22 IfStmt
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: 22 IfStmt
-// DFS-NEXT: --END PATH--
-// DFS-NEXT: --END PATH--
-
-
 void testLoops(id input) {
   while (a()) {
     work();
@@ -85,13 +48,166 @@ void testLoops(id input) {
   }
 }
 
-// BFS: 64 WhileStmt
-// BFS: 70 ForStmt
-// BFS-NOT-NEXT: ObjCForCollectionStmt
-// BFS: 74 ObjCForCollectionStmt
-// BFS: 81 CXXForRangeStmt
+// This ordering assumes that false cases happen before the true cases.
+
+// DFS:27 WhileStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:27 WhileStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:27 WhileStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:27 WhileStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:33 ForStmt
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:44 CXXForRangeStmt
+// DFS-next:--END PATH--
+// DFS-next:37 ObjCForCollectionStmt
+// DFS-next:10 IfStmt
+// DFS-next:16 IfStmt
+// DFS-next:22 IfStmt
+// DFS-next:--END PATH--
+// DFS-next:--END PATH--
+// DFS-next:22 IfStmt
+// DFS-next:--END PATH--
+// DFS-next:--END PATH--
+// DFS-next:11 IfStmt
+// DFS-next:22 IfStmt
+// DFS-next:--END PATH--
+// DFS-next:--END PATH--
+// DFS-next:22 IfStmt
+// DFS-next:--END PATH--
+// DFS-next:--END PATH--
 
-// DFS: 64 While
-// DFS-NEXT: 70 ForStmt
-// DFS-NEXT: 74 ObjCForCollectionStmt
-// DFS-NEXT: 81 CXXForRangeStmt