[analyzer] Switch the default exploration strategy to priority queue based on coverage

[george.karpenkov]

Summary

After the investigation it seems safe to flip the switch.

[NoQ]

Peter, would you have time to see if the loop-unrolling changes are making sense - now or after the fact? Like, we're changing exploration order, so it'd bail-out on block counts and replay-without-inlining functions in a different manner, so numTimesReached counts get skewed. Do the two updated tests still demonstrate the expected behavior, or should a FIXME be added?

[NoQ]

Or you can hardcode the old exploration order in the test run-lines.

Or hardcode both exploration orders - but in this case it's still be good to figure out if the other behavior is correct.

[NoQ]

LGTM otherwise. I repeat that in my opinion this whole exploration order thing was a fantastic discovery.

[george.karpenkov]

I guess until we get a comment from @phosek let's test both.

[george.karpenkov]

Ooops I've meant @szepet

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

AnalyzerOptions::UserModeKind AnalyzerOptions::getUserMode() {
   return UserMode;
 }
 
 AnalyzerOptions::ExplorationStrategyKind
 AnalyzerOptions::getExplorationStrategy() {
   if (ExplorationStrategy == ExplorationStrategyKind::NotSet) {
     StringRef StratStr =
         Config
-            .insert(std::make_pair("exploration_strategy", "dfs"))
+            .insert(std::make_pair("exploration_strategy", "unexplored_first_queue"))
             .first->second;
     ExplorationStrategy =
         llvm::StringSwitch<ExplorationStrategyKind>(StratStr)
             .Case("dfs", ExplorationStrategyKind::DFS)
             .Case("bfs", ExplorationStrategyKind::BFS)
             .Case("unexplored_first",
                   ExplorationStrategyKind::UnexploredFirst)
             .Case("unexplored_first_queue",

test/Analysis/analyzer-config.c

 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin10 %s -o /dev/null -analyzer-checker=core,osx.cocoa,debug.ConfigDumper -analyzer-max-loop 34 > %t 2>&1
-// RUN: FileCheck --input-file=%t %s
+// RUN: FileCheck --input-file=%t %s --match-full-lines
 
 void bar() {}
 void foo() {
   // Call bar 33 times so max-times-inline-large is met and
   // min-blocks-for-inline-large is checked
   for (int i = 0; i < 34; ++i) {
     bar();
   }
 }
 
 // CHECK: [config]
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-rich-constructors = true
 // CHECK-NEXT: cfg-temporary-dtors = false
-// CHECK-NEXT: exploration_strategy = dfs
+// CHECK-NEXT: exploration_strategy = unexplored_first_queue
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000

test/Analysis/analyzer-config.cpp

 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin10 %s -o /dev/null -analyzer-checker=core,osx.cocoa,debug.ConfigDumper -analyzer-max-loop 34 > %t 2>&1
-// RUN: FileCheck --input-file=%t %s
+// RUN: FileCheck --input-file=%t %s --match-full-lines
 
 void bar() {}
 void foo() {
   // Call bar 33 times so max-times-inline-large is met and
   // min-blocks-for-inline-large is checked
   for (int i = 0; i < 34; ++i) {
     bar();
   }

 // CHECK-NEXT: c++-stdlib-inlining = true
 // CHECK-NEXT: c++-template-inlining = true
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-rich-constructors = true
 // CHECK-NEXT: cfg-temporary-dtors = false
-// CHECK-NEXT: exploration_strategy = dfs
+// CHECK-NEXT: exploration_strategy = unexplored_first_queue
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000

test/Analysis/loop-unrolling.cpp

for (int i = 2; i < 12; i++) {
     // This function is inlined in nested_inlined_unroll1()
     clang_analyzer_numTimesReached(); // expected-warning {{90}}
   }
   return 0;
 }
 
 int simple_unknown_bound_loop() {
   for (int i = 2; i < getNum(); i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    clang_analyzer_numTimesReached(); // expected-warning {{13}}
   }
   return 0;
 }
 
 int nested_inlined_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{9}}
     k = simple_known_bound_loop();    // no reevaluation without inlining
   }
   int a = 22 / k; // expected-warning {{Division by zero}}
   return 0;
 }
 
 int nested_inlined_no_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    clang_analyzer_numTimesReached(); // expected-warning {{15}}
     k = simple_unknown_bound_loop();  // reevaluation without inlining, splits the state as well
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
 int recursion_unroll1(bool b) {
   int k = 2;