[analyzer] Don't track function calls as control dependencies

[Szelethus]

Summary

I recently evaluated ~150 of bug reports on open source projects relating to my GSoC'19 project, which was about tracking control dependencies that were relevant to a bug report.

Here is what I found: when the condition is a function call, the extra notes were almost always unimportant, and often times intrusive:

void f(int *x) {
  x = nullptr;
  if (alwaysTrue()) // We don't need a whole lot of explanation
                    // here, the function name is good enough.
    *x = 5;
}

It almost always boiled down to a few "Returning null pointer, which participates in a condition later", or similar notes. I struggled to find a single case where the notes revealed anything interesting or some previously hidden correlation, which is kind of the point of condition tracking.

This patch checks whether the condition is a function call, and if so, bails out.

The argument against the patch is the popular feedback we hear from some of our users, namely that they can never have too much information. I was specifically fishing for examples that display best that my contribution did more good than harm, so admittedly I set the bar high, and one can argue that there can be non-trivial trickery inside functions, and function names may not be that descriptive.

My argument for the patch is all those reports that got longer without any notable improvement in the report intelligibility. I think the few exceptional cases where this patch would remove notable information are an acceptable sacrifice in favor of more reports being leaner.

[NoQ]

Interesting. Might it be that in this scenario in order to be of interest to the user the condition value has to be trackable back to the current stack frame?

the popular feedback we hear from some of our users, namely that they can never have too much information

They should try prune-paths=false in C++. Hundreds of inlined copy-constructors will definitely give them the desired experience ;)

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1931–1933

Let's make it clear that this decision is purely stochastic: we can totally build an artificial example where this results in bad behavior but we've never seen one in practice.

[Szelethus]

Fix tests, mention that this is purely a heuristic.

[Szelethus]

Ping ^-^

[steakhal]

Looks great!
Thanks for your hard work on this topic @Szelethus.

clang/lib/Analysis/CFG.cpp

5912–5913

How are these dump() changes related?

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1964

extra blank line

clang/test/Analysis/track-control-dependency-conditions.cpp

1008

Please also have a c++17 init if statement.

1038

What if this expression is enclosed by a logical operator such as &&?

[Szelethus]

Fixes according to reviewer comments.

[Szelethus]

clang/lib/Analysis/CFG.cpp

5912–5913

I'll commit them in a separate patch.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1964

That is intentional -- I think it makes the code more readable. Separates the function signature from the implementation.

clang/test/Analysis/track-control-dependency-conditions.cpp

1038

For each of those operators, a different CFGBlock would be created:

if (A && B) 
  C;
D;

      C
    /   \
  B------->
 /         \
A---------> D

This means that operands of || and && is retrievable through CFGBlock::getLastCondition(), so I shouldn't need to tear the AST apart to that extent. Though, I admit, you likely don't need to go very far to fool my implementation for realizing whether the condition boils down to a function call.

[steakhal]

I'm convinced!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1964

Okay.

clang/test/Analysis/track-control-dependency-conditions.cpp

41

Some of these hunks are unrelated to the parts you actually changed.
Strictly peaking I don't mind them, just pointing out.
clang-format-diff.py would format only the changed lines.

202–205

For the record, I never understood why we have two notes about the same thing: we are taking that branch.
Maybe we should keep simplifying these notes in the future as well.

1038

I see, thanks.

clang/include/clang/Analysis/CFG.h

public:
 
   //===--------------------------------------------------------------------===//
   // CFG Debugging: Pretty-Printing and Visualization.
   //===--------------------------------------------------------------------===//
 
   void viewCFG(const LangOptions &LO) const;
   void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
   void dump(const LangOptions &LO, bool ShowColors) const;
+  void dump(bool ShowColors=true) const;
 
   //===--------------------------------------------------------------------===//
   // Internal: constructors and data.
   //===--------------------------------------------------------------------===//
 
   CFG() : Blocks(BlkBVC, 10) {}
 
   llvm::BumpPtrAllocator& getAllocator() {

clang/lib/Analysis/CFG.cpp

if (!B.succ_empty()) {
       if (ShowColors)
         OS.resetColor();
       OS << '\n';
     }
   }
 }
 
 /// dump - A simple pretty printer of a CFG that outputs to stderr.
 void CFG::dump(const LangOptions &LO, bool ShowColors) const {
   print(llvm::errs(), LO, ShowColors);
 }
 
+void CFG::dump(bool ShowColors) const {
+  dump(LangOptions{}, ShowColors);
+}
+
 /// print - A simple pretty printer of a CFG that outputs to an ostream.
 void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
   StmtPrinterHelper Helper(this, LO);
 
   // Print the entry block.
   print_block(OS, this, getEntry(), Helper, true, ShowColors);
 
   // Iterate through the CFGBlocks and print them one by one.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

if (B->getLHS()->getType()->isPointerType()) {
       return B->getLHS();
     } else if (B->getRHS()->getType()->isPointerType()) {
       return B->getRHS();
     }
   }
   return nullptr;
 }
 
+/// \return A subexpression of @c Ex which represents the
+/// expression-of-interest.
+static const Expr *peelOffOuterExpr(const Expr *Ex, const ExplodedNode *N);
+
 /// Given that expression S represents a pointer that would be dereferenced,
 /// try to find a sub-expression from which the pointer came from.
 /// This is used for tracking down origins of a null or undefined value:
 /// "this is null because that is null because that is null" etc.
 /// We wipe away field and element offsets because they merely add offsets.
 /// We also wipe away all casts except lvalue-to-rvalue casts, because the
 /// latter represent an actual pointer dereference; however, we remove
 /// the final lvalue-to-rvalue cast before returning from this function
TrackControlDependencyCondBRVisitor::VisitNode(const ExplodedNode *N,
 
   if (ControlDeps.isControlDependent(OriginB, NB)) {
     // We don't really want to explain for range loops. Evidence suggests that
     // the only thing that leads to is the addition of calls to operator!=.
     if (llvm::isa_and_nonnull<CXXForRangeStmt>(NB->getTerminatorStmt()))
       return nullptr;
 
     if (const Expr *Condition = NB->getLastCondition()) {
+
+      // If we can't retrieve a sensible condition, just bail out.
+      const Expr *InnerExpr = peelOffOuterExpr(Condition, N);
+      if (!InnerExpr)
+        return nullptr;
+
+      // If the condition was a function call, we likely won't gain much from
+      // tracking it either. Evidence suggests that it will mostly trigger in
+      // scenarios like this:
+      //
+      //   void f(int *x) {
+      //     x = nullptr;
+      //     if (alwaysTrue()) // We don't need a whole lot of explanation
+      //                       // here, the function name is good enough.
+      //       *x = 5;
+      //   }
+      if (isa<CallExpr>(InnerExpr))
+        return nullptr;
+
       // Keeping track of the already tracked conditions on a visitor level
       // isn't sufficient, because a new visitor is created for each tracked
       // expression, hence the BugReport level set.
       if (BR.addTrackedCondition(N)) {
-        getParentTracker().track(Condition, N,
+        getParentTracker().track(InnerExpr, N,
                                  {bugreporter::TrackingKind::Condition,
                                   /*EnableNullFPSuppression=*/false});
         return constructDebugPieceForTrackedCondition(Condition, N, BRC);
       }
     }
   }
 
   return nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 // Implementation of trackExpressionValue.
 //===----------------------------------------------------------------------===//
 
-/// \return A subexpression of @c Ex which represents the
-/// expression-of-interest.
-static const Expr *peelOffOuterExpr(const Expr *Ex,
-                                    const ExplodedNode *N) {
+static const Expr *peelOffOuterExpr(const Expr *Ex, const ExplodedNode *N) {
+
   Ex = Ex->IgnoreParenCasts();
   if (const auto *FE = dyn_cast<FullExpr>(Ex))
     return peelOffOuterExpr(FE->getSubExpr(), N);
   if (const auto *OVE = dyn_cast<OpaqueValueExpr>(Ex))
     return peelOffOuterExpr(OVE->getSourceExpr(), N);
   if (const auto *POE = dyn_cast<PseudoObjectExpr>(Ex)) {
     const auto *PropRef = dyn_cast<ObjCPropertyRefExpr>(POE->getSyntacticForm());
     if (PropRef && PropRef->isMessagingGetter()) {

clang/test/Analysis/return-value-guaranteed.cpp

if (problem()) {
     // class-note@-2 {{Taking false branch}}
     return MCAsmParser::Error();
   }
 
   F.Field = 0;
   // class-note@-1 {{The value 0 is assigned to 'F.Field'}}
   return !MCAsmParser::Error();
   // class-note@-1 {{'MCAsmParser::Error' returns true}}
-  // class-note@-2 {{Returning zero, which participates in a condition later}}
 }
 
 bool parseFile() {
   Foo F;
   if (parseFoo(F)) {
     // class-note@-1 {{Calling 'parseFoo'}}
     // class-note@-2 {{Returning from 'parseFoo'}}
     // class-note@-3 {{Taking false branch}}

 
 
 // We predefined 'MCAsmParser::Error' as returning true, but now it returns
 // false, which breaks our invariant. Test the notes.
 namespace test_break {
 struct MCAsmParser {
   static bool Error() {
     return false; // class-note {{'MCAsmParser::Error' returns false}}
-    // class-note@-1 {{Returning zero, which participates in a condition later}}
   }
 };
 
 bool parseFoo(Foo &F) {
   if (problem()) {
     // class-note@-1 {{Assuming the condition is false}}
     // class-note@-2 {{Taking false branch}}
     return !MCAsmParser::Error();
   }
 
   F.Field = 0;
   // class-note@-1 {{The value 0 is assigned to 'F.Field'}}
   return MCAsmParser::Error();
   // class-note@-1 {{Calling 'MCAsmParser::Error'}}
   // class-note@-2 {{Returning from 'MCAsmParser::Error'}}
-  // class-note@-3 {{Returning zero, which participates in a condition later}}
 }
 
 bool parseFile() {
   Foo F;
   if (parseFoo(F)) {
     // class-note@-1 {{Calling 'parseFoo'}}
     // class-note@-2 {{Returning from 'parseFoo'}}
     // class-note@-3 {{Taking false branch}}

clang/test/Analysis/track-control-dependency-conditions.cpp

 void foo() {
   flag = coin(); // tracking-note-re{{{{^}}Value assigned to 'flag', which participates in a condition later{{$}}}}
 }
 
 void test() {
   int *x = 0; // expected-note-re{{{{^}}'x' initialized to a null pointer value{{$}}}}
   flag = 1;
 
   foo(); // TODO: Add nodes here about flag's value being invalidated.
   if (flag) // expected-note-re   {{{{^}}Assuming 'flag' is 0{{$}}}}
             // expected-note-re@-1{{{{^}}Taking false branch{{$}}}}
     x = new int;
 
   foo(); // tracking-note-re{{{{^}}Calling 'foo'{{$}}}}
          // tracking-note-re@-1{{{{^}}Returning from 'foo'{{$}}}}
 
   if (flag) // expected-note-re   {{{{^}}Assuming 'flag' is not equal to 0{{$}}}}

 struct ConvertsToBool {
   operator bool() const { return coin(); }
 };
 
 void test() {
   int *x = 0; // expected-note-re{{{{^}}'x' initialized to a null pointer value{{$}}}}
 
   if (ConvertsToBool())
-    // debug-note-re@-1{{{{^}}Tracking condition 'ConvertsToBool()'{{$}}}}
-    // expected-note-re@-2{{{{^}}Assuming the condition is true{{$}}}}
-    // expected-note-re@-3{{{{^}}Taking true branch{{$}}}}
+    // expected-note-re@-1{{{{^}}Assuming the condition is true{{$}}}}
+    // expected-note-re@-2{{{{^}}Taking true branch{{$}}}}
     *x = 5; // expected-warning{{Dereference of null pointer}}
             // expected-note@-1{{Dereference of null pointer}}
 }
 
-} // end of namespace variable_declaration_in_condition
+} // namespace conversion_to_bool
 
 namespace note_from_different_but_not_nested_stackframe {
 
 void nullptrDeref(int *ptr, bool True) {
   if (True) // expected-note-re{{{{^}}'True' is true{{$}}}}
             // expected-note-re@-1{{{{^}}Taking true branch{{$}}}}
             // debug-note-re@-2{{{{^}}Tracking condition 'True'{{$}}}}
     *ptr = 5;

 } // end of namespace note_from_different_but_not_nested_stackframe
 
 namespace important_returning_pointer_loaded_from {
 bool coin();
 
 int *getIntPtr();
 
 void storeValue(int **i) {
-  *i = getIntPtr(); // tracking-note-re{{{{^}}Value assigned to 'i', which participates in a condition later{{$}}}}
+  *i = getIntPtr();
 }
 
 int *conjurePointer() {
   int *i;
-  storeValue(&i); // tracking-note-re{{{{^}}Calling 'storeValue'{{$}}}}
-                  // tracking-note-re@-1{{{{^}}Returning from 'storeValue'{{$}}}}
-  return i; // tracking-note-re{{{{^}}Returning pointer (loaded from 'i'), which participates in a condition later{{$}}}}
+  storeValue(&i);
+  return i;
 }
 
 void f(int *ptr) {
   if (ptr) // expected-note-re{{{{^}}Assuming 'ptr' is null{{$}}}}
            // expected-note-re@-1{{{{^}}Taking false branch{{$}}}}
     ;
   if (!conjurePointer())
-    // tracking-note-re@-1{{{{^}}Calling 'conjurePointer'{{$}}}}
-    // tracking-note-re@-2{{{{^}}Returning from 'conjurePointer'{{$}}}}
-    // debug-note-re@-3{{{{^}}Tracking condition '!conjurePointer()'{{$}}}}
-    // expected-note-re@-4{{{{^}}Assuming the condition is true{{$}}}}
-    // expected-note-re@-5{{{{^}}Taking true branch{{$}}}}
+    // debug-note-re@-1{{{{^}}Tracking condition '!conjurePointer()'{{$}}}}
+    // expected-note-re@-2{{{{^}}Assuming the condition is true{{$}}}}
+    // expected-note-re@-3{{{{^}}Taking true branch{{$}}}}
     *ptr = 5; // expected-warning{{Dereference of null pointer}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace important_returning_pointer_loaded_from
 
 namespace unimportant_returning_pointer_loaded_from {
 bool coin();
 
 int *getIntPtr();
 
 int *conjurePointer() {
   int *i = getIntPtr();
   return i;
 }
 
 void f(int *ptr) {
   if (ptr) // expected-note-re{{{{^}}Assuming 'ptr' is null{{$}}}}
            // expected-note-re@-1{{{{^}}Taking false branch{{$}}}}
     ;
   if (!conjurePointer())
-    // debug-note-re@-1{{{{^}}Tracking condition '!conjurePointer()'{{$}}}}
-    // expected-note-re@-2{{{{^}}Assuming the condition is true{{$}}}}
-    // expected-note-re@-3{{{{^}}Taking true branch{{$}}}}
+    // expected-note-re@-1{{{{^}}Assuming the condition is true{{$}}}}
+    // expected-note-re@-2{{{{^}}Taking true branch{{$}}}}
     *ptr = 5; // expected-warning{{Dereference of null pointer}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace unimportant_returning_pointer_loaded_from
 
 namespace unimportant_returning_pointer_loaded_from_through_cast {
 
 void *conjure();
 
 int *cast(void *P) {
   return static_cast<int *>(P);
 }
 
 void f() {
   int *x = 0; // expected-note-re{{{{^}}'x' initialized to a null pointer value{{$}}}}
 
   if (cast(conjure()))
-    // debug-note-re@-1{{{{^}}Tracking condition 'cast(conjure())'{{$}}}}
-    // expected-note-re@-2{{{{^}}Assuming the condition is false{{$}}}}
-    // expected-note-re@-3{{{{^}}Taking false branch{{$}}}}
+    // expected-note-re@-1{{{{^}}Assuming the condition is false{{$}}}}
+    // expected-note-re@-2{{{{^}}Taking false branch{{$}}}}
     return;
   *x = 5; // expected-warning{{Dereference of null pointer}}
           // expected-note@-1{{Dereference of null pointer}}
 }
 
 } // end of namespace unimportant_returning_pointer_loaded_from_through_cast
 
 namespace unimportant_returning_value_note {
*ptr = 5; // expected-warning{{Dereference of null pointer}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace unimportant_returning_value_note
 
 namespace important_returning_value_note {
 bool coin();
 
 bool flipCoin() {
-  if (coin()) // tracking-note-re{{{{^}}Assuming the condition is false{{$}}}}
-              // tracking-note-re@-1{{{{^}}Taking false branch{{$}}}}
-              // debug-note-re@-2{{{{^}}Tracking condition 'coin()'{{$}}}}
+  if (coin())
     return true;
-  return coin(); // tracking-note-re{{{{^}}Returning value, which participates in a condition later{{$}}}}
+  return coin();
 }
 
 void i(int *ptr) {
   if (ptr) // expected-note-re{{{{^}}Assuming 'ptr' is null{{$}}}}
            // expected-note-re@-1{{{{^}}Taking false branch{{$}}}}
     ;
   if (!flipCoin())
-    // tracking-note-re@-1{{{{^}}Calling 'flipCoin'{{$}}}}
-    // tracking-note-re@-2{{{{^}}Returning from 'flipCoin'{{$}}}}
-    // debug-note-re@-3{{{{^}}Tracking condition '!flipCoin()'{{$}}}}
-    // expected-note-re@-4{{{{^}}Assuming the condition is true{{$}}}}
-    // expected-note-re@-5{{{{^}}Taking true branch{{$}}}}
+    // expected-note-re@-1{{{{^}}Assuming the condition is true{{$}}}}
+    // expected-note-re@-2{{{{^}}Taking true branch{{$}}}}
     *ptr = 5; // expected-warning{{Dereference of null pointer}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace important_returning_value_note
 
 namespace important_returning_value_note_in_linear_function {
 bool coin();
+int flag;
 
 struct super_complicated_template_hackery {
   static constexpr bool value = false;
 };
 
-bool flipCoin() {
+void flipCoin() {
   if (super_complicated_template_hackery::value)
-    // tracking-note-re@-1{{{{^}}'value' is false{{$}}}}
-    // tracking-note-re@-2{{{{^}}Taking false branch{{$}}}}
-    return true;
-  return coin(); // tracking-note-re{{{{^}}Returning value, which participates in a condition later{{$}}}}
+    // expected-note-re@-1{{{{^}}'value' is 0{{$}}}}
+    // expected-note-re@-2{{{{^}}Taking false branch{{$}}}}
+    return;
+  flag = false; // tracking-note-re{{{{^}}The value 0 is assigned to 'flag', which participates in a condition later{{$}}}}
 }
 
 void i(int *ptr) {
+  flag = true;
   if (ptr) // expected-note-re{{{{^}}Assuming 'ptr' is null{{$}}}}
            // expected-note-re@-1{{{{^}}Taking false branch{{$}}}}
     ;
-  if (!flipCoin())
-    // tracking-note-re@-1{{{{^}}Calling 'flipCoin'{{$}}}}
-    // tracking-note-re@-2{{{{^}}Returning from 'flipCoin'{{$}}}}
-    // debug-note-re@-3{{{{^}}Tracking condition '!flipCoin()'{{$}}}}
-    // expected-note-re@-4{{{{^}}Assuming the condition is true{{$}}}}
-    // expected-note-re@-5{{{{^}}Taking true branch{{$}}}}
+  flipCoin();
+  if (!flag)
+    // debug-note-re@-1{{{{^}}Tracking condition '!flag'{{$}}}}
+    // expected-note-re@-2{{{{^}}'flag' is 0{{$}}}}
+    // expected-note-re@-3{{{{^}}Taking true branch{{$}}}}
     *ptr = 5; // expected-warning{{Dereference of null pointer}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace important_returning_value_note_in_linear_function
 
 namespace tracked_condition_is_only_initialized {
 int getInt();
 
if (flag && flag2) // expected-note-re   {{{{^}}Assuming 'flag' is 0{{$}}}}
                      // debug-note-re@-2{{{{^}}Tracking condition 'flag'{{$}}}}
     return;
 
   *x = 5; // expected-warning{{Dereference of null pointer}}
           // expected-note@-1{{Dereference of null pointer}}
 }
 
 } // end of namespace only_track_the_evaluated_condition
+
+namespace operator_call_in_condition_point {
+
+struct Error {
+  explicit operator bool() {
+    return true;
+  }
+};
+
+Error couldFail();
+
+void f(int *x) {
+  x = nullptr;               // expected-note {{Null pointer value stored to 'x'}}
+  if (auto e = couldFail())  // expected-note {{Taking true branch}}
+    *x = 5;                  // expected-warning {{Dereference of null pointer (loaded from variable 'x') [core.NullDereference]}}
+                             // expected-note@-1 {{Dereference}}
+}
+
+} // namespace operator_call_in_condition_point
+
+namespace funcion_call_in_condition_point {
+
+int alwaysTrue() {
+  return true;
+}
+
+void f(int *x) {
+  x = nullptr;      // expected-note {{Null pointer value stored to 'x'}}
+  if (alwaysTrue()) // expected-note {{Taking true branch}}
+    *x = 5;         // expected-warning {{Dereference of null pointer (loaded from variable 'x') [core.NullDereference]}}
+                    // expected-note@-1 {{Dereference}}
+}
+
+} // namespace funcion_call_in_condition_point
+
+namespace funcion_call_negated_in_condition_point {
+
+int alwaysFalse() {
+  return false;
+}
+
+void f(int *x) {
+  x = nullptr;      // expected-note {{Null pointer value stored to 'x'}}
+  if (!alwaysFalse()) // expected-note {{Taking true branch}}
+    *x = 5;         // expected-warning {{Dereference of null pointer (loaded from variable 'x') [core.NullDereference]}}
+                    // expected-note@-1 {{Dereference}}
+}
+
+} // namespace funcion_call_negated_in_condition_point