[analyzer] ReturnVisitor: Bypass everything to see inlined calls

[Charusso]

Summary

When we traversed backwards on ExplodedNodes to see where we processed the
given statement we break too early. With the current approach we do not
miss the CallExitEnd ProgramPoint which stands for an inlined call.

[Szelethus]

clang/test/Analysis/new-ctor-null-throw.cpp

1–7

Hmm, how come you removed -analyzer-config c++-allocator-inlining=true?

[NoQ]

Aha, that's something! And nice to see we've already had this bug covered with tests. Because, of course, i added these tests a year ago without even thinking about what the correct behavior should look like :/

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

835–865

This iteration may now take us straight to the root of the graph. I don't think it's supposed to be that slow; i think it's supposed to only skip within maybe a full-expression at most.

Which statements in the AST are getting peeled off here that weren't before? Which statements are supposed to get peeled off?

Might it be that we should simply add one more case to peelOffOuterExpr() or something like that?

clang/test/Analysis/new-ctor-null-throw.cpp

1–7

It's on by default these days.

33–36

Let's add a // no-warning here, probably with a comment that this the warning is intentionally suppressed.

clang/test/Analysis/new-ctor-null.cpp

29–30

Let's add a // no-warning here as well.

[Charusso]

• More explicit approach.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

835–865

We have the following sequence in the loop:

"stmt_kind": "DeclStmt", "stmt_point_kind": "PostStmt"
"stmt_kind": "DeclStmt", "stmt_point_kind": "PostStore"
"stmt_kind": "DeclStmt",  "stmt_point_kind": "PreStmtPurgeDeadSymbols"
"pretty": "S *s = new S [10];"

"stmt_kind": "CXXNewExpr", "stmt_point_kind": "PostStmt"
"stmt_kind": "CXXNewExpr", "stmt_point_kind": "PreStmtPurgeDeadSymbols"
"pretty": "new S [10]"

"stmt_kind": "CXXConstructExpr", "stmt_point_kind": "PostStmt"
"stmt_kind": "CXXConstructExpr", "stmt_point_kind": "PreStmt"
"stmt_kind": "CXXConstructExpr", "stmt_point_kind": "PreStmtPurgeDeadSymbols"
"pretty": null

"kind": "CallExitEnd" - found the ReturnStmt, all good.

This ReturnVisitor is totally ProgramPoint-based and I wanted to be super generic. Do you know about more problematic constructing-object?

[Charusso]

• Better wording.

[Charusso]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

835–865

Btw: this cool dump based on D62946

[Charusso]

If I run scan-build on LLVM this is the only non-bypassed case since the first diff:

non-bypassed.html569 KBDownload

I think it is working well.

[NoQ]

Aha, nice, that's much cleaner! Indeed, we have to skip the construct-expression, which is going to be on our way to the program point of new-expression which corresponds to calling the allocator, despite being nested within the new-expression. An annoying corner-case.

I'd like to have a test in which the constructor is inlined. I suspect that we'll have to skip the whole inlined call in this case, and it'll be a lot of various program points. We'll most likely have to consult location contexts to skip everything within the constructor's stack frame.

In the test cases that you've updated the constructor isn't inlined because it's an array-new operator and we don't bother inlining 10 default constructors (@Szelethus: a nice application of data flow analysis might be to find out if the default constructor always initializes the structure in the same way, say all nulls, so we could evaluate one constructor and default-bind it to the whole array in this case; @baloghadamsoftware: this in turn reminds me that i still need to do something about D22374).

[Charusso]

• Added CallExpr as being purged away
• More test

[Charusso]

In D62926#1533560, @NoQ wrote:

I'd like to have a test in which the constructor is inlined.

What do you mean by that test?

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

845–850

Comparing statements is usually insufficient because the same statement may appear multiple times due to recursion. When recursion occurs, you may reach the same statement in a different location context. You should think in terms of (statement, location context) pairs to avoid these problems. Your aim here is to find the CallExitEnd node that corresponds to returning from an inlined operator new to the current location context. You should stop searching when you find an unrelated statement in the current location context or when you exit the current location context entirely.

[Charusso]

• The most generic approach.

[Charusso]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

845–850

I have made a little test when we have a 25-second long Static Analyzer run with predefined names and checker. The loop ran 500 times in summary and we have some serious performance impacts at other places.

We exit the current context to see inlined calls, so that could not work sadly. If you remove that nonsense second condition we run at the same time, so if we have not got any problem since 7 years ago I think it is good to go.

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

845–850

You should break the loop as soon as we go past the new-expression that we've started with in the stack frame that we've started with. That is, you should at most go through the constructor within the new-expression, and then break. You shouldn't explore the whole graph to the root every time the operator-new call isn't inlined.

This might still be slow in some rare cases, but it should be much faster.

[Charusso]

• I have used LocationContext::isParentOf()which is not worked well, so I thought we are out of our context.
• With that I made some misleading assumptions about our code.

[Charusso]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

845–850

Sorry, I was dumb and I have used isParentOf() before, I think it is the most simple approach now truly.

[NoQ]

All right, it seems that i'm completely misunderstanding this problem and we've been talking past each other this whole time.

The problem is not that we need to skip the CXXConstructExpr. The problem is that we need to skip CXXNewExpr (!!). CFG elements for an operator-new call go like this:

1. CFGAllocatorCall
2. CXXConstructExpr
3. CXXNewExpr

We're staring at element 3. The original loop says "hey, that's our statement! we've found it!". However, even though this is the statement that's taken as the call site, the respective ExplodedNode does not correspond to the end of the call. Instead, it corresponds to a moment of time after construction has finished and the new-expression is fully evaluated. So we need to ignore element 3. Then, element 2 is ignored automatically because the statements don't match. Then, we need to learn to recognize that element 1 is the right element, which is going to be either a CallExitEnd (if the allocator call was inlined) or dunno-but-definitely-not-PostStmt if the allocator was evaluated conservatively.

Bonus: the constructor is never inlined in our scenario, so it's easy to skip element 2, as it's going to be just PreStmt/PostStmt and no inlined call within it. Why? Because how the hell do you inline a constructor of a null pointer. The Standard guarantees that when the allocator returns a null pointer, the constructor is gracefully omitted. We currently have a FIXME in prepareForObjectConstruction() to implement this behavior:

179         // TODO: Detect when the allocator returns a null pointer.
180         // Constructor shall not be called in this case.

The current incorrect behavior is to instead evaluate the constructor conservatively, with a fake temporary region instead of the null pointer (this is generally the conservative approach to evaluating the constructor when object-under-construction is not known).

So my request to come up with a test case in which the constructor is going to be inlined was completely pointless. But in the general case we aren't really sure that it's going to be a null pointer (we may want to track an arbitrary value), so we shouldn't rely on that.

clang/test/Analysis/new-ctor-null.cpp

37

This is essentially the same FIXME: the constructor should not have been evaluated, so in particular we should not invalidate globals.

[Charusso]

In D62926#1539191, @NoQ wrote:

All right, it seems that i'm completely misunderstanding this problem and we've been talking past each other this whole time.

The problem is not that we need to skip the CXXConstructExpr. The problem is that we need to skip CXXNewExpr (!!). CFG elements for an operator-new call go like this:

I really wanted to create a generic approach without any overhead. I have added the proper test case what is going on: we enter into another contexts and that should be modeled properly. I was not sure about how to do so, but after a while it has been born. It contains all of your ideas from all the comments and now we only bypassing CXXNewExprs.

[NoQ]

Yup, this makes sense now! I'll do some nit-picking for a little longer.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

839

For now this hack is clearly only for CXXNewExpr. And it happens because our AST is weird and there's no separate sub-expression dedicated entirely to invoking the allocator. Therefore let's give this variable a better name, maybe BypassCXXNewExprEvaluation or something like that.

855–859

Branches here are unnecessary because there's no performance win here. Let's just

CurrentSFC = Node->getStackFrame();

861–865

This code would currently bypass the call site for the conservatively evaluated allocator. It doesn't seem to be immediately important but let's add a FIXME.

[Charusso]

• Fixed comments.

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

855

Mmm, wait a sec. This way the loop condition is trivially true. The second check on line 862 is also trivially true. I think you want to make it a separate variable.

[Charusso]

• Whoops.

[Charusso]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

855

I was never cool in algorithms, thanks!

[NoQ]

Great, thanks!! Let's commit this.

[hintonda]

This test fails to compile on Windows 64 bit builds. Please see http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/77

cfe/trunk/test/Analysis/inlining/placement-new-fp-suppression.cpp

16 ↗

(On Diff #204910)

I don't believe this is really ever portable, but definitely not on 64 bit Windows where a long is 32 bits.

Can't you just #include <stdint.h> instead?

[Szelethus]

cfe/trunk/test/Analysis/inlining/placement-new-fp-suppression.cpp

16 ↗

(On Diff #204910)

In the test, I'm pretty sure that he can't.

I grepped test/Analysis, and found that malloc.cpp does the following:

typedef unsigned __INTPTR_TYPE__ uintptr_t

Maybe that's worth a shot?

[Szelethus]

cfe/trunk/test/Analysis/inlining/placement-new-fp-suppression.cpp

16 ↗

(On Diff #204910)

I seem to have been proven wrong. :)

[Charusso]

In D62926#1545163, @hintonda wrote:

This test fails to compile on Windows 64 bit builds. Please see http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/77

Thanks you! I have not got a mail, now it passes on my side: http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/80/steps/stage%201%20check/logs/stdio
But some unrelated error occurs: http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/80/steps/stage%202%20build/logs/stdio

Sorry for all the inconveniences it caused.

[Charusso]

@NoQ, thanks for the review! Now everything is working by rL363515.

cfe/trunk/test/Analysis/inlining/placement-new-fp-suppression.cpp

16 ↗

(On Diff #204910)

I was a little-bit surprised as well. Thanks for the idea!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

public:
   /// the statement is a call that was inlined, we add the visitor to the
   /// bug report, so it can print a note later.
   static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S,
                                     BugReport &BR,
                                     bool InEnableNullFPSuppression) {
     if (!CallEvent::isCallStmt(S))
       return;
 
     // First, find when we processed the statement.
+    // If we work with a 'CXXNewExpr' that is going to be purged away before
+    // its call take place. We would catch that purge in the last condition
+    // as a 'StmtPoint' so we have to bypass it.
+    const bool BypassCXXNewExprEval = isa<CXXNewExpr>(S);
+
+    // This is moving forward when we enter into another context.
+    const StackFrameContext *CurrentSFC = Node->getStackFrame();
+
     do {
-      if (auto CEE = Node->getLocationAs<CallExitEnd>())
+      // If that is satisfied we found our statement as an inlined call.
+      if (Optional<CallExitEnd> CEE = Node->getLocationAs<CallExitEnd>())
         if (CEE->getCalleeContext()->getCallSite() == S)
           break;
-      if (auto SP = Node->getLocationAs<StmtPoint>())
-        if (SP->getStmt() == S)
-          break;
 
+      // Try to move forward to the end of the call-chain.
       Node = Node->getFirstPred();
-    } while (Node);
+      if (!Node)
+        break;
+
+      CurrentSFC = Node->getStackFrame();
+
+      // If that is satisfied we found our statement.
+      // FIXME: This code currently bypasses the call site for the
+      //        conservatively evaluated allocator.
+      if (!BypassCXXNewExprEval)
+        if (Optional<StmtPoint> SP = Node->getLocationAs<StmtPoint>())
+          if (SP->getStmt() == S && SP->getStackFrame() == CurrentSFC)
+            break;
+
+    } while (Node->getStackFrame() == CurrentSFC);
 
     // Next, step over any post-statement checks.
     while (Node && Node->getLocation().getAs<PostStmt>())
       Node = Node->getFirstPred();
     if (!Node)
       return;
 
     // Finally, see if we inlined the call.

clang/test/Analysis/inlining/placement-new-fp-suppression.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core.CallAndMessage \
+// RUN:  -analyzer-config suppress-null-return-paths=false \
+// RUN:  -verify %s
+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core.CallAndMessage \
+// RUN:  -DSUPPRESSED \
+// RUN:  -verify %s
+
+#ifdef SUPPRESSED
+// expected-no-diagnostics
+#endif
+
+#include "../Inputs/system-header-simulator-cxx.h"
+
+typedef unsigned long uintptr_t;
+
+void error();
+void *malloc(size_t);
+
+
+// From llvm/include/llvm/Support/MathExtras.h
+inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
+  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
+}
+
+inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
+  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
+}
+
+
+// From llvm/include/llvm/Support/MemAlloc.h
+inline void *safe_malloc(size_t Sz) {
+  void *Result = malloc(Sz);
+  if (Result == nullptr)
+    error();
+
+  return Result;
+}
+
+
+// From llvm/include/llvm/Support/Allocator.h
+class MallocAllocator {
+public:
+  void *Allocate(size_t Size, size_t /*Alignment*/) {
+    return safe_malloc(Size);
+  }
+};
+
+class BumpPtrAllocator {
+public:
+  void *Allocate(size_t Size, size_t Alignment) {
+    BytesAllocated += Size;
+    size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
+    size_t SizeToAllocate = Size;
+
+    size_t PaddedSize = SizeToAllocate + Alignment - 1;
+    uintptr_t AlignedAddr = alignAddr(Allocator.Allocate(PaddedSize, 0),
+                                      Alignment);
+    char *AlignedPtr = (char*)AlignedAddr;
+
+    return AlignedPtr;
+  }
+
+private:
+  char *CurPtr = nullptr;
+  size_t BytesAllocated = 0;
+  MallocAllocator Allocator;
+};
+
+
+// From clang/include/clang/AST/ASTContextAllocate.h
+class ASTContext;
+
+void *operator new(size_t Bytes, const ASTContext &C, size_t Alignment = 8);
+void *operator new[](size_t Bytes, const ASTContext &C, size_t Alignment = 8);
+
+
+// From clang/include/clang/AST/ASTContext.h
+class ASTContext {
+public:
+  void *Allocate(size_t Size, unsigned Align = 8) const {
+    return BumpAlloc.Allocate(Size, Align);
+  }
+
+  template <typename T>
+  T *Allocate(size_t Num = 1) const {
+    return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T)));
+  }
+
+private:
+  mutable BumpPtrAllocator BumpAlloc;
+};
+
+
+// From clang/include/clang/AST/ASTContext.h
+inline void *operator new(size_t Bytes, const ASTContext &C,
+                          size_t Alignment /* = 8 */) {
+  return C.Allocate(Bytes, Alignment);
+}
+
+inline void *operator new[](size_t Bytes, const ASTContext &C,
+                            size_t Alignment /* = 8 */) {
+  return C.Allocate(Bytes, Alignment);
+}
+
+
+// From clang/include/clang/AST/Attr.h
+void *operator new(size_t Bytes, ASTContext &C,
+                   size_t Alignment = 8) noexcept {
+  return ::operator new(Bytes, C, Alignment);
+}
+
+
+class A {
+public:
+  void setValue(int value) { Value = value; }
+private:
+  int Value;
+};
+
+void f(const ASTContext &C) {
+  A *a = new (C) A;
+  a->setValue(13);
+#ifndef SUPPRESSED
+  // expected-warning@-2 {{Called C++ object pointer is null}}
+#endif
+} 
+
+void g(const ASTContext &C) {
+  A *a = new (C) A[1];
+  a[0].setValue(13);
+#ifndef SUPPRESSED
+  // expected-warning@-2 {{Called C++ object pointer is null}}
+#endif
+}
+

clang/test/Analysis/new-ctor-null-throw.cpp

-// RUN: %clang_analyze_cc1 -w -analyzer-checker=core,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core \
+// RUN:  -analyzer-config suppress-null-return-paths=false \
+// RUN:  -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core \
+// RUN:  -DSUPPRESSED \
+// RUN:  -verify %s
 
 void clang_analyzer_eval(bool);
 
 typedef __typeof__(sizeof(int)) size_t;
 
 
 // These are ill-formed. One cannot return nullptr from a throwing version of an
 // operator new.
 void *operator new(size_t size) {
   return nullptr;
+  // expected-warning@-1 {{'operator new' should not return a null pointer unless it is declared 'throw()' or 'noexcept'}}
 }
 void *operator new[](size_t size) {
   return nullptr;
+  // expected-warning@-1 {{'operator new[]' should not return a null pointer unless it is declared 'throw()' or 'noexcept'}}
 }
 
 struct S {
   int x;
   S() : x(1) {}
   ~S() {}
+  int getX() const { return x; }
 };
 
 void testArrays() {
   S *s = new S[10]; // no-crash
-  s[0].x = 2; // expected-warning{{Dereference of null pointer}}
+  s[0].x = 2;
+#ifndef SUPPRESSED
+  // expected-warning@-2 {{Dereference of null pointer}}
+#endif
 }
+
+void testCtor() {
+  S *s = new S();
+  s->x = 13;
+#ifndef SUPPRESSED
+  // expected-warning@-2 {{Access to field 'x' results in a dereference of a null pointer (loaded from variable 's')}}
+#endif
+}
+
+void testMethod() {
+  S *s = new S();
+  const int X = s->getX();
+#ifndef SUPPRESSED
+  // expected-warning@-2 {{Called C++ object pointer is null}}
+#endif
+}
+

clang/test/Analysis/new-ctor-null.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,debug.ExprInspection \
+// RUN:  -verify %s
 
 void clang_analyzer_eval(bool);
 void clang_analyzer_warnIfReached();
 
 typedef __typeof__(sizeof(int)) size_t;
 
 void *operator new(size_t size) throw() {
   return nullptr;
S() : x(1) {
     // returned by operator new().
     clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
   }
   ~S() {}
 };
 
 void testArrays() {
   S *s = new S[10]; // no-crash
-  s[0].x = 2; // expected-warning{{Dereference of null pointer}}
+  s[0].x = 2;
+  // no-warning: 'Dereference of null pointer' suppressed by ReturnVisitor.
 }
 
 int global;
 void testInvalidationOnConstructionIntoNull() {
   global = 0;
   S *s = new S();
   // FIXME: Should be FALSE - we should not invalidate globals.
   clang_analyzer_eval(global); // expected-warning{{UNKNOWN}}
 }