[analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value

[Szelethus]

Summary

During the evaluation of D62883, I noticed a bunch of totally meaningless notes with the pattern of "Calling 'A'" -> "Returning value" -> "Returning from 'A'", which added no value to the report at all.

This patch (not only affecting tracked conditions mind you) prunes diagnostic messages to functions that return a value not constrained to be 0, and are also linear.

[NoQ]

I guess this makes sense. The results look good. I'm slightly worried that we're fighting the symptoms rather than the root cause here: why were these values tracked that far in the first place when we already have no interest in tracking them at the end of the function? I.e., i suspect that your "mild tracking mode" would get rid of a lot of those automagically.

clang/test/Analysis/uninit-vals.c

181

Huh, so there's not even a note in getHalfPoint(), just calling..returning? This definitely needs some attention from NoStoreFuncVisitor.

Generally, i think this is probably the single place where we do really want some info about what happens in getHalfPoint(). The report that consists only of "p is initialized..." and "...p is uninitialized" is pretty weird. Btw, could you write down the full warning text in this test? How bad this actually is?

[Szelethus]

In D64232#1570938, @NoQ wrote:

I'm slightly worried that we're fighting the symptoms rather than the root cause here: why were these values tracked that far in the first place when we already have no interest in tracking them at the end of the function?

Could you please elaborate? Which of the modified test cases (or any other) do you think falls under "being tracked too far" and why? Whenever the CFG where the value isn't linear, I think the information could be valuable, see the inline.

I.e., i suspect that your "mild tracking mode" would get rid of a lot of those automagically.

A lot of those, correct, all of them, nope. I've been slacking on publishing the moderate tracking I've been working on, I'll get that done during the day.

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

185

This note is meaningful, the bug would not have occurred if coin() wasn't assumed to be false.

clang/test/Analysis/uninit-vals.c

181

Wild idea: UninitializedObjectChecker exposes it's main logic through a header file, how about we use it when we find a read of an uninitialized region?

[Szelethus]

Rebase.

[Szelethus]

Gentle ping.

[Szelethus]

clang/test/Analysis/uninit-vals.c

181

Passed-by-value struct argument contains uninitialized data (e.g., field: 'y')

Quite good imo.

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1052

This time i'd rather go for "has exactly 3 blocks", because we're mostly interested in the CFG being "syntactically linear" rather than "semantically linear". I.e., if the CFG has an if-statement with a compile-time-constant condition, i'd rather show the path, because who knows what does the programmer think about this condition.

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

185

Mmmmm. Mmmmm. Dunno, this is getting complicated very quickly. Say, if you replace return true with return false on the previous line, the note becomes meaningless again. I don't see a direct connection between meaningfulness and linearness.

The note in this example is relatively meaningful indeed, but i'm not sure it's so much meaningful that it's worth the noise. It's still not surprising for me that flipCoin() occasionally returns false. I do believe that it may be sometimes surprising that flipCoin() may return false on the *current path*, which would make the note meaningful. However, note that we don't prove that it may return false, we only push the assumption one step deeper, i.e. put the blame on coin() instead of flipCoin(), but we still fully trust our assumption about coin() which may have the same problem. And if we had an actual proof that it may return false, we would have had a concrete-false return value, so the patch wouldn't apply.

I guess some experimental data would be great to have.

clang/test/Analysis/uninit-vals.c

181

What specific logic are you talking about? You mean it'd scan the structure for uninitialized fields and present the results of the scan to the user in a note?

[Szelethus]

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

185

Oh yea, I see where you are going. As I understand correctly, these are two separate problems: trying to somehow argue about other execution paths and whether dropping all constraints on a symbol is a good approach.

I should have all the results by tomorrow if all goes according to plan.

clang/test/Analysis/uninit-vals.c

181

What specific logic are you talking about? You mean it'd scan the structure for uninitialized fields and present the results of the scan to the user in a note?

Nvm, looked at the code, realized that what I said made no sense. What we are really missing here is a trackRegionValue() function :^)

Btw, I wasted soooo much time on figuring out that you don't get ANY notes whatsoever if you make this a cpp file rather than a c file, only the warning... Is this intended?

[Szelethus]

Rebase on top master. Putting this on the bottom of the patch stack because this really deserves it's own analysis. (Side note, I completely messed up like ~40 hrs worth of analysis because I didn't check which branches do I have stacked on top of each other, so this might take a while...)

[xazax.hun]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1052

Yeah, this is a hard question, both sides can have its own reasons.

One of my concern is that functions that does seem to be linear to people are actually not linear CFG wise. One example is single one liner functions with an assert preceding the line in question.

Other interesting note is that once we add exception support and edges for exception handling in the CFG, all the analyzer budgets and CFG node count based heuristics need to be redone. But this is not something we should worry about at this point.

[Szelethus]

LLVM+Clang (A total of 207 reports changed)

with "track-conditions" set to true (bug length)	with "track-conditions" set to true and this patch applied (bug length)
InstrTypes.cpp (9)	InstrTypes.cpp (5)
APInt.h (17)	APInt.h (13)
ASTDiagnostic.cpp (19)	ASTDiagnostic.cpp (15)
ASTImporter.cpp (43)	ASTImporter.cpp (34)
ASTImporter.cpp (45)	ASTImporter.cpp (35)
ASTImpoter.cpp (23)	ASTImpoter.cpp (17)
ASMPrinter.cpp (28)	ASMPrinter.cpp (24)
AutoUpgrade.cpp (20)	AutoUpgrade (12) This one is pretty cool.
BasicObjCFoundationChecks.cpp (37)	BasicObjCFoundationChecks.cpp (25) Even cooler.
BasicTTIImpl.h (30)	BasicTTIImpl.h (19)
BinaryStreamReader.cpp (6)	BinaryStreamReader.cpp (3)
BinaryStreamReader.h (16)	BinaryStreamReader.h (13)
List of files that changed	Where the results can be checked by changing the run the left corner

Bitcoin (only 1 changed)

with "track-conditions" set to true (bug length)	with "track-conditions" set to true and this patch applied (bug length)
net_processing.cpp (27)	net_processing.cpp (21)

Xerces (A total of 11 reports changed):

with "track-conditions" set to true (bug length)	with "track-conditions" set to true and this patch applied (bug length)
XSAXMLScanner.cpp ( 14)	XSAXMLScanner.cpp (10)
ReaderMgr.cpp (12)	ReaderMgr.cpp (8)
SGXMLScanner.cpp (20)	SGXMLScanner.cpp (16)
DFAContentModel.cpp (16)	DFAContentModel.cpp (12)
List of files that changed	Where the results can be checked by changing the run the left corner

I like how things look like with this patch.

[Szelethus]

• Be even more strict on the rule: mark the note as prunable even if the note message says .*(loaded from '<varname>'). This is okay, because ReturnVisitor will track the return value anyways, and if at least a single non-prunable note is added to the function, it won't be pruned (see the test case in the namespace important_returning_pointer_loaded_from).
• Add test cases for when the return value is function-local (unimportant_returning_pointer_loaded_from), and when it's the parameter (unimportant_returning_pointer_loaded_from_through_cast, creduced and then manually reduced from an ASTImporter.cpp report).

[Szelethus]

Use size() == 3 instead if isLinear(), add a related test case.

[NoQ]

Sry, should have approved this ages ago >.<

clang/test/Analysis/uninit-vals.c

181

Btw, I wasted soooo much time on figuring out that you don't get ANY notes whatsoever if you make this a cpp file rather than a c file, only the warning... Is this intended?

At a glance, the behavior of this code in C and C++ is ridiculously different. The way structures are returned-by-value is one of the glaring differences between C and C++. Even at runtime / ABI / calling convention level: in C it's acceptable to simply pass the structure through registers (or put it on the stack, wherever the return value normally lives), however in C++ the calling convention usually requres you to pass return address as a separate hidden parameter so that to use it as "this" in the structure's constructor (and then later use it for RVO and NRVO which may span multiple stack frames) . And the Static Analyzer also deals with completely different ASTs. So i'm not surprised that there's a difference.

But i would also probably not want there to be a difference. If you could turn it into a sensible bug report i guess it could be helpful.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

 /// Emits an extra note at the return statement of an interesting stack frame.
 ///
 /// The returned value is marked as an interesting value, and if it's null,
 /// adds a visitor to track where it became null.
 ///
 /// This visitor is intended to be used when another visitor discovers that an
 /// interesting value comes from an inlined function call.
 class ReturnVisitor : public BugReporterVisitor {
-  const StackFrameContext *StackFrame;
+  const StackFrameContext *CalleeSFC;
   enum {
     Initial,
     MaybeUnsuppress,
     Satisfied
   } Mode = Initial;
 
   bool EnableNullFPSuppression;
   bool ShouldInvalidate = true;
   AnalyzerOptions& Options;
 
 public:
   ReturnVisitor(const StackFrameContext *Frame,
                 bool Suppressed,
                 AnalyzerOptions &Options)
-      : StackFrame(Frame), EnableNullFPSuppression(Suppressed),
+      : CalleeSFC(Frame), EnableNullFPSuppression(Suppressed),
         Options(Options) {}
 
   static void *getTag() {
     static int Tag = 0;
     return static_cast<void *>(&Tag);
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     ID.AddPointer(ReturnVisitor::getTag());
-    ID.AddPointer(StackFrame);
+    ID.AddPointer(CalleeSFC);
     ID.AddBoolean(EnableNullFPSuppression);
   }
 
   /// Adds a ReturnVisitor if the given statement represents a call that was
   /// inlined.
   ///
   /// This will search back through the ExplodedGraph, starting from the given
   /// node, looking for when the given statement was processed. If it turns out
static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S,
     AnalyzerOptions &Options = State->getAnalysisManager().options;
 
     bool EnableNullFPSuppression = false;
     if (InEnableNullFPSuppression &&
         Options.ShouldSuppressNullReturnPaths)
       if (Optional<Loc> RetLoc = RetVal.getAs<Loc>())
         EnableNullFPSuppression = State->isNull(*RetLoc).isConstrainedTrue();
 
-    BR.markInteresting(CalleeContext);
     BR.addVisitor(llvm::make_unique<ReturnVisitor>(CalleeContext,
                                                    EnableNullFPSuppression,
                                                    Options));
   }
 
   std::shared_ptr<PathDiagnosticPiece>
   visitNodeInitial(const ExplodedNode *N,
                    BugReporterContext &BRC, BugReport &BR) {
     // Only print a message at the interesting return statement.
-    if (N->getLocationContext() != StackFrame)
+    if (N->getLocationContext() != CalleeSFC)
       return nullptr;
 
     Optional<StmtPoint> SP = N->getLocationAs<StmtPoint>();
     if (!SP)
       return nullptr;
 
     const auto *Ret = dyn_cast<ReturnStmt>(SP->getStmt());
     if (!Ret)
       return nullptr;
 
     // Okay, we're at the right return statement, but do we have the return
     // value available?
     ProgramStateRef State = N->getState();
-    SVal V = State->getSVal(Ret, StackFrame);
+    SVal V = State->getSVal(Ret, CalleeSFC);
     if (V.isUnknownOrUndef())
       return nullptr;
 
     // Don't print any more notes after this one.
     Mode = Satisfied;
 
     const Expr *RetE = Ret->getRetValue();
     assert(RetE && "Tracking a return value for a void function");
visitNodeInitial(const ExplodedNode *N,
 
     // If we're returning 0, we should track where that 0 came from.
     bugreporter::trackExpressionValue(N, RetE, BR, EnableNullFPSuppression);
 
     // Build an appropriate message based on the return value.
     SmallString<64> Msg;
     llvm::raw_svector_ostream Out(Msg);
 
+    bool WouldEventBeMeaningless = false;
+
     if (State->isNull(V).isConstrainedTrue()) {
       if (V.getAs<Loc>()) {
 
         // If we have counter-suppression enabled, make sure we keep visiting
         // future nodes. We want to emit a path note as well, in case
         // the report is resurrected as valid later on.
         if (EnableNullFPSuppression &&
             Options.ShouldAvoidSuppressingNullArgumentPaths)
           Mode = MaybeUnsuppress;
 
         if (RetE->getType()->isObjCObjectPointerType()) {
           Out << "Returning nil";
         } else {
           Out << "Returning null pointer";
         }
       } else {
         Out << "Returning zero";
       }
 
     } else {
       if (auto CI = V.getAs<nonloc::ConcreteInt>()) {
         Out << "Returning the value " << CI->getValue();
-      } else if (V.getAs<Loc>()) {
-        Out << "Returning pointer";
       } else {
+        // There is nothing interesting about returning a value, when it is
+        // plain value without any constraints, and the function is guaranteed
+        // to return that every time.
+        if (N->getCFG().isLinear())
+          WouldEventBeMeaningless = true;
+
+        if (V.getAs<Loc>())
+          Out << "Returning pointer";
+        else
           Out << "Returning value";
       }
     }
 
     if (LValue) {
       if (const MemRegion *MR = LValue->getAsRegion()) {
         if (MR->canPrintPretty()) {
+          WouldEventBeMeaningless = false;
           Out << " (reference to ";
           MR->printPretty(Out);
           Out << ")";
         }
       }
     } else {
       // FIXME: We should have a more generalized location printing mechanism.
-      if (const auto *DR = dyn_cast<DeclRefExpr>(RetE))
-        if (const auto *DD = dyn_cast<DeclaratorDecl>(DR->getDecl()))
+      if (const auto *DR = dyn_cast<DeclRefExpr>(RetE)) {
+        if (const auto *DD = dyn_cast<DeclaratorDecl>(DR->getDecl())) {
+          WouldEventBeMeaningless = false;
           Out << " (loaded from '" << *DD << "')";
         }
+      }
+    }
 
-    PathDiagnosticLocation L(Ret, BRC.getSourceManager(), StackFrame);
+    PathDiagnosticLocation L(Ret, BRC.getSourceManager(), CalleeSFC);
     if (!L.isValid() || !L.asLocation().isValid())
       return nullptr;
 
-    return std::make_shared<PathDiagnosticEventPiece>(L, Out.str());
+    auto EventPiece = std::make_shared<PathDiagnosticEventPiece>(L, Out.str());
+
+    // If we determined that the note is meaningless, make it prunable, and
+    // don't mark the stackframe interesting.
+    if (WouldEventBeMeaningless)
+      EventPiece->setPrunable(true);
+    else
+      BR.markInteresting(CalleeSFC);
+
+    return EventPiece;
   }
 
   std::shared_ptr<PathDiagnosticPiece>
   visitNodeMaybeUnsuppress(const ExplodedNode *N,
                            BugReporterContext &BRC, BugReport &BR) {
 #ifndef NDEBUG
     assert(Options.ShouldAvoidSuppressingNullArgumentPaths);
 #endif
 
     // Are we at the entry node for this call?
     Optional<CallEnter> CE = N->getLocationAs<CallEnter>();
     if (!CE)
       return nullptr;
 
-    if (CE->getCalleeContext() != StackFrame)
+    if (CE->getCalleeContext() != CalleeSFC)
       return nullptr;
 
     Mode = Satisfied;
 
     // Don't automatically suppress a report if one of the arguments is
     // known to be a null pointer. Instead, start tracking /that/ null
     // value back to its origin.
     ProgramStateManager &StateMgr = BRC.getStateManager();
     CallEventManager &CallMgr = StateMgr.getCallEventManager();
 
     ProgramStateRef State = N->getState();
-    CallEventRef<> Call = CallMgr.getCaller(StackFrame, State);
+    CallEventRef<> Call = CallMgr.getCaller(CalleeSFC, State);
     for (unsigned I = 0, E = Call->getNumArgs(); I != E; ++I) {
       Optional<Loc> ArgV = Call->getArgSVal(I).getAs<Loc>();
       if (!ArgV)
         continue;
 
       const Expr *ArgE = Call->getArgExpr(I);
       if (!ArgE)
         continue;
std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
     }
 
     llvm_unreachable("Invalid visit mode!");
   }
 
   void finalizeVisitor(BugReporterContext &, const ExplodedNode *,
                        BugReport &BR) override {
     if (EnableNullFPSuppression && ShouldInvalidate)
-      BR.markInvalid(ReturnVisitor::getTag(), StackFrame);
+      BR.markInvalid(ReturnVisitor::getTag(), CalleeSFC);
   }
 };
 
 } // end of anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // Implementation of FindLastStoreBRVisitor.
 //===----------------------------------------------------------------------===//

clang/test/Analysis/diagnostics/find_last_store.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-output=text -verify %s
 typedef struct { float b; } c;
 void *a();
 void *d() {
-  return a(); // expected-note{{Returning pointer}}
+  return a();
 }
 
 void no_find_last_store() {
-  c *e = d(); // expected-note{{Calling 'd'}}
-              // expected-note@-1{{Returning from 'd'}}
-              // expected-note@-2{{'e' initialized here}}
+  c *e = d(); // expected-note{{'e' initialized here}}
 
   (void)(e || e->b); // expected-note{{Assuming 'e' is null}}
       // expected-note@-1{{Left side of '||' is false}}
       // expected-note@-2{{Access to field 'b' results in a dereference of a null pointer (loaded from variable 'e')}}
       // expected-warning@-3{{Access to field 'b' results in a dereference of a null pointer (loaded from variable 'e')}}
 }

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

if (flag) // expected-note   {{Assuming 'flag' is not equal to 0}}
               // expected-note@-1{{Dereference of null pointer}}
 }
 } // end of namespace global_variable_invalidation
 
 namespace variable_declaration_in_condition {
 bool coin();
 
 bool foo() {
-  return coin(); // tracking-note{{Returning value}}
+  return coin();
 }
 
 int bar;
 
 void test() {
   int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
 
-  if (int flag = foo()) // tracking-note{{Calling 'foo'}}
-                        // tracking-note@-1{{Returning from 'foo'}}
-                        // debug-note@-2{{Tracking condition 'flag'}}
-                        // expected-note@-3{{Assuming 'flag' is not equal to 0}}
-                        // expected-note@-4{{Taking true branch}}
+  if (int flag = foo()) // debug-note{{Tracking condition 'flag'}}
+                        // expected-note@-1{{Assuming 'flag' is not equal to 0}}
+                        // expected-note@-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 {
 bool coin();
 
 struct ConvertsToBool {
-  operator bool() const { return coin(); } // tracking-note{{Returning value}}
+  operator bool() const { return coin(); }
 };
 
 void test() {
   int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
 
   if (ConvertsToBool())
-    // tracking-note@-1 {{Calling 'ConvertsToBool::operator bool'}}
-    // tracking-note@-2{{Returning from 'ConvertsToBool::operator bool'}}
-    // debug-note@-3{{Tracking condition 'ConvertsToBool()'}}
-    // expected-note@-4{{Assuming the condition is true}}
-    // expected-note@-5{{Taking true branch}}
+    // debug-note@-1{{Tracking condition 'ConvertsToBool()'}}
+    // expected-note@-2{{Assuming the condition is true}}
+    // expected-note@-3{{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 unimportant_returning_value_note {
 bool coin();
 
-bool flipCoin() { return coin(); } // tracking-note{{Returning value}}
+bool flipCoin() { return coin(); }
 
 void i(int *ptr) {
   if (ptr) // expected-note{{Assuming 'ptr' is null}}
            // expected-note@-1{{Taking false branch}}
     ;
   if (!flipCoin())
-    // tracking-note@-1{{Calling 'flipCoin'}}
-    // tracking-note@-2{{Returning from 'flipCoin'}}
-    // debug-note@-3{{Tracking condition '!flipCoin()'}}
-    // expected-note@-4{{Assuming the condition is true}}
-    // expected-note@-5{{Taking true branch}}
+    // debug-note@-1{{Tracking condition '!flipCoin()'}}
+    // expected-note@-2{{Assuming the condition is true}}
+    // expected-note@-3{{Taking true branch}}
     *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{{Assuming the condition is false}}
               // tracking-note@-1{{Taking false branch}}
               // debug-note@-2{{Tracking condition 'coin()'}}
     return true;
   return coin(); // tracking-note{{Returning value}}
 }
 
 void i(int *ptr) {
   if (ptr) // expected-note{{Assuming 'ptr' is null}}
            // expected-note@-1{{Taking false branch}}
     ;
   if (!flipCoin())
     // tracking-note@-1{{Calling 'flipCoin'}}

clang/test/Analysis/uninit-vals.c

 
 void foo_radar12278788_fp() { return; }
 typedef int (*RetIntFuncType)();
 typedef void (*RetVoidFuncType)();
 int test_radar12278788_FP() {
   RetVoidFuncType f = foo_radar12278788_fp;
   return ((RetIntFuncType)f)(); //expected-warning {{Undefined or garbage value returned to caller}}
                                 //expected-note@-1 {{Undefined or garbage value returned to caller}}
-                                //expected-note@-2 {{Calling 'foo_radar12278788_fp'}}
-                                //expected-note@-3 {{Returning from 'foo_radar12278788_fp'}}
 }
 
 void rdar13665798() {
   ^() {
     return foo_radar12278788(); // no-warning
   }();
   ^void() {
     return foo_radar12278788(); // no-warning
   }();
   ^int() { // expected-note{{Calling anonymous block}}
     RetVoidFuncType f = foo_radar12278788_fp;
     return ((RetIntFuncType)f)(); //expected-warning {{Undefined or garbage value returned to caller}}
                                   //expected-note@-1 {{Undefined or garbage value returned to caller}}
-                                  //expected-note@-2 {{Calling 'foo_radar12278788_fp'}}
-                                  //expected-note@-3 {{Returning from 'foo_radar12278788_fp'}}
   }();
 }
 
 struct Point {
   int x, y;
 };
 
 struct Point getHalfPoint() {
   struct Point p;
   p.x = 0;
   return p;
 }
 
 void use(struct Point p); 
 
 void testUseHalfPoint() {
-  struct Point p = getHalfPoint(); // expected-note{{Calling 'getHalfPoint'}}
-                                   // expected-note@-1{{Returning from 'getHalfPoint'}}
-                                   // expected-note@-2{{'p' initialized here}}
+  struct Point p = getHalfPoint(); // expected-note{{'p' initialized here}}
   use(p); // expected-warning{{uninitialized}}
           // expected-note@-1{{uninitialized}}
 }
 
 void testUseHalfPoint2() {
   struct Point p;
-  p = getHalfPoint(); // expected-note{{Calling 'getHalfPoint'}}
-                      // expected-note@-1{{Returning from 'getHalfPoint'}}
-                      // expected-note@-2{{Value assigned to 'p'}}
+  p = getHalfPoint(); // expected-note{{Value assigned to 'p'}}
   use(p); // expected-warning{{uninitialized}}
           // expected-note@-1{{uninitialized}}
 }