[StaticAnalyser] Don't merge different returns in ExplodedGraph

[danielmarjamaki]

Summary

Returns when calling an inline function should not be merged in the ExplodedGraph unless they are same.

Background post on cfe-dev:
http://lists.llvm.org/pipermail/cfe-dev/2016-October/051001.html

Here is an example patch that solves my false positives and also fixes 2 false negatives in existing tests.

What do you think about this approach?

[zaks.anna]

Daniel, please, add reviewers to this patch.

[NoQ]

Funny facts about the Environment:

(a) Environment allows taking SVals of ReturnStmt, which is not an expression, by transparently converting it into its sub-expression. In fact, it only stores expressions.

Having just noticed (a), i also understand that (a) is not of direct importance to the question, however:

(b) With a similar trick, Environment allows taking SVal of literal expressions, but never stores literal expressions. Instead, it reconstructs the constant value by looking at the literal and returns the freshly constructed value when asked.

This leads to "return 0;" and "return 1;" branches having the same program state. The difference should have been within Environment (return values are different), however return values are literals, and they aren't stored in the Environment, and hence the Environment is equal in both states. If only the function returned, say, 0 and i, the problem wouldn't have been there.

This leaves us with two options:

1. Tell the Environment to store everything. This would make things heavy. However, i do not completely understand the consequences of this bug at the moment - perhaps there would be more problems due to this state merging unless we start storing everything.

2. Rely on the ProgramPoint to remember where we are. After all, why do we merge when program points should clearly be different? The program point that fails us is CallExitBegin - we could construct it with ReturnStmt and its block count to discriminate between different returns. It should fix this issue, and is similar to the approach taken in this patch (just puts things to their own place), however, as i mentioned, there might be more problems with misbehavior (b) of the Environment, need to think.

Finally, i'm not quite sure why CallExitBegin is at all necessary. I wonder if we could just remove it and jump straight to Bind Return Value, also need to think.

[danielmarjamaki]

adding reviewers.

[danielmarjamaki]

In D25326#564082, @NoQ wrote:

Funny facts about the Environment:

(a) Environment allows taking SVals of ReturnStmt, which is not an expression, by transparently converting it into its sub-expression. In fact, it only stores expressions.

Having just noticed (a), i also understand that (a) is not of direct importance to the question, however:

(b) With a similar trick, Environment allows taking SVal of literal expressions, but never stores literal expressions. Instead, it reconstructs the constant value by looking at the literal and returns the freshly constructed value when asked.

This leads to "return 0;" and "return 1;" branches having the same program state. The difference should have been within Environment (return values are different), however return values are literals, and they aren't stored in the Environment, and hence the Environment is equal in both states. If only the function returned, say, 0 and i, the problem wouldn't have been there.

I did not know "a" and "b", thanks for info.

This leaves us with two options:

1. Tell the Environment to store everything. This would make things heavy. However, i do not completely understand the consequences of this bug at the moment - perhaps there would be more problems due to this state merging unless we start storing everything.

2. Rely on the ProgramPoint to remember where we are. After all, why do we merge when program points should clearly be different? The program point that fails us is CallExitBegin - we could construct it with ReturnStmt and its block count to discriminate between different returns. It should fix this issue, and is similar to the approach taken in this patch (just puts things to their own place), however, as i mentioned, there might be more problems with misbehavior (b) of the Environment, need to think.

1. yes sounds heavy.
2. I assume you are right.. however as I understand it the ProgramPoint when CallExitBegin is called is the same (in the exit block). do you suggest that we take the ProgramPoint for the exit block's predecessor?

Finally, i'm not quite sure why CallExitBegin is at all necessary. I wonder if we could just remove it and jump straight to Bind Return Value, also need to think.

me too. however there is much I wonder about when it comes to ExplodedGraph. :-)

[NoQ]

In D25326#564185, @danielmarjamaki wrote:

as I understand it the ProgramPoint when CallExitBegin is called is the same (in the exit block). do you suggest that we take the ProgramPoint for the exit block's predecessor?

CallExitBegin is the program point. I propose to make different exits from the same function be different program points. This could be achieved by adding more members to the CallExitBegin class - return statement and block count would probably be sufficient.

In fact, not sure if we need block count. If we're, say, returning from a loop with the same statement, then we're either returning different values, or returning the same literal expression, so Environment would do the job for us well in both cases.

[danielmarjamaki]

ok. As far as I see it's not trivial to know which ReturnStmt there was when CallExitBegin is created. Do you suggest that I move it or that I try to lookup the ReturnStmt? I guess it can be looked up by looking in the predecessors in the ExplodedGraph?

Finally, i'm not quite sure why CallExitBegin is at all necessary. I wonder if we could just remove it and jump straight to Bind Return Value, also need to think.

.. unless that is better apprach

[NoQ]

In D25326#564239, @danielmarjamaki wrote:

ok. As far as I see it's not trivial to know which ReturnStmt there was when CallExitBegin is created.

We're in HandleBlockEdge, just pass down the statement from CFG here?

In D25326#564239, @danielmarjamaki wrote:

.. unless that is better apprach

It seems to have something to do with separation of duties between CoreEngine and ExprEngine. Kind of, CoreEngine explores the CFG, ExprEngine models effects of statements, and noticing end of function is CoreEngine's duty, while binding the return value is ExprEngine's duty, and CallExitBegin acts like a message from CoreEngine to ExprEngine so that they could work together. That's how it seems to me, but i'm not sure of the original intention here.

[danielmarjamaki]

In D25326#564283, @NoQ wrote:

In D25326#564239, @danielmarjamaki wrote:

ok. As far as I see it's not trivial to know which ReturnStmt there was when CallExitBegin is created.

We're in HandleBlockEdge, just pass down the statement from CFG here?

I don't directly see how you mean. Code is:

void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {

  const CFGBlock *Blk = L.getDst();

The Blk->dump() says:

[B0 (EXIT)]
   Preds (2): B1 B2

[NoQ]

In D25326#564291, @danielmarjamaki wrote:

The Blk->dump() says:

[B0 (EXIT)]
   Preds (2): B1 B2

What about the source block?

[danielmarjamaki]

In D25326#564291, @danielmarjamaki wrote:

In D25326#564283, @NoQ wrote:

In D25326#564239, @danielmarjamaki wrote:

ok. As far as I see it's not trivial to know which ReturnStmt there was when CallExitBegin is created.

We're in HandleBlockEdge, just pass down the statement from CFG here?

I don't directly see how you mean. Code is:

void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {

  const CFGBlock *Blk = L.getDst();

The Blk->dump() says:

[B0 (EXIT)]
   Preds (2): B1 B2

Sorry... I think I see. L.getSrc() will give me the cfg block I am interested in.

[danielmarjamaki]

Refactoring.

[NoQ]

Yay, this is great. Thanks for investigating all those loss of coverage issues!

lib/StaticAnalyzer/Core/CoreEngine.cpp

610 ↗

(On Diff #73926)

Space after ",".

639 ↗

(On Diff #73926)

Space after ",".

lib/StaticAnalyzer/Core/ExprEngine.cpp

1792 ↗

(On Diff #73926)

Space after ",".

[zaks.anna]

Please, fix the style issues before committing.

include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

266 ↗

(On Diff #73926)

Add spaces around '=.'

[dcoughlin]

Can you also add a test that tests this more directly (i.e., with clang_analyzer_warnIfReached). I don't think it is good to have the only test for this core coverage issue to be in tests for an alpha checker. Adding the direct test would also make it easier to track down any regression if it happens. The 'func.c' test file might be a good place for such a test.

[a.sidorin]

test/Analysis/unreachable-code-path.c

201 ↗

(On Diff #73926)

I have a small question. Is it possible to simplify this sample with removing of table[] array? Like putting something like i != 0 into condition. As I understand, the problem is not array-related.

[NoQ]

test/Analysis/unreachable-code-path.c

201 ↗

(On Diff #73926)

Any UnknownVal in the condition would trigger this issue.

[danielmarjamaki]

test/Analysis/unreachable-code-path.c

201 ↗

(On Diff #73926)

Is it possible to simplify this sample with removing of table[] array?

I tried to simplify as much as possible. But as NoQ says an UnknownVal is required here for this test.

[danielmarjamaki]

In D25326#564584, @zaks.anna wrote:

Please, fix the style issues before committing.

Sorry I missed that.

Ideally it would be possible to run clang-format on the files before committing. but currently I get lots of unrelated changes then.

Would it be ok to run clang-format on some files to clean up the formatting? At least some minor changes like removing trailing spaces.

[NoQ]

In D25326#565919, @danielmarjamaki wrote:

Ideally it would be possible to run clang-format on the files before committing. but currently I get lots of unrelated changes then.

Would it be ok to run clang-format on some files to clean up the formatting? At least some minor changes like removing trailing spaces.

clang-format should be able to format small sections of the code, keeping in mind the rest of the file but not touching it. In vim, i use a hotkey for formatting the statement under cursor. I've seen a plugin for Xcode that clang-format's selected text. Also, there's this git clang-format thingy, which should be able to clang-format git changes and only them, i didn't try, but it might be universally useful.

[dcoughlin]

test/Analysis/unreachable-code-path.c

201 ↗

(On Diff #73926)

This is worth a comment in the test then, so that if we ever add symbolic reasoning we'll know how to adjust the test.

You could also try to add a canary with clang analyzer eval after the if statement to force the test to fail if we do add this symbolic reasoning.

[dcoughlin]

In D25326#565919, @danielmarjamaki wrote:

In D25326#564584, @zaks.anna wrote:

Please, fix the style issues before committing.

Would it be ok to run clang-format on some files to clean up the formatting? At least some minor changes like removing trailing spaces.

We generally try to avoid large-scale fixes of formatting and spacing issues if they are not on lines already modified by a patch. This makes it a bit easier to track down the original commit for a line and also reduces merge conflicts.

[danielmarjamaki]

I agree with the comments from you dcoughlin but I am not sure how to do it.

Can you also add a test that tests this more directly (i.e., with clang_analyzer_warnIfReached). I don't think it is good to have the only test for this core coverage issue to be in tests for an alpha checker. Adding the direct test would also make it easier to track down any regression if it happens. The 'func.c' test file might be a good place for such a test.

I totally agree.

In func.c there such comments:
// expected-warning{{FALSE|TRUE|UNKNOWN}}

what does those FALSE|TRUE|UNKNOWN do?

I don't see what this will do:

clang_analyzer_eval(!f);

I want that both returns are reached. and I want to ensure that result from function is both 1 and 0.

You could also try to add a canary with clang analyzer eval after the if statement to force the test to fail if we do add this symbolic reasoning.

sounds good. sorry but I don't see how to do it.

[dcoughlin]

In D25326#569061, @danielmarjamaki wrote:

You could also try to add a canary with clang analyzer eval after the if statement to force the test to fail if we do add this symbolic reasoning.

sounds good. sorry but I don't see how to do it.

The trick is to not first store the UnknownVal into a local (the analyzer will automatically create a symbol for that when read).

Instead you can do something like:

if (table[i] != 0) { }
clang_analyzer_eval((table[i] != 0)) // expected-warning {{UNKNOWN}}

This way if the analyzer ever starts generating symbols for a read from table[i] then the case split will change the eval to emit TRUE on one path and FALSE on the other.

cfe/trunk/include/clang/Analysis/ProgramPoint.h

 /// two program points:
 /// - CallExitBegin
 /// - Bind the return value
 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
 /// - CallExitEnd
 class CallExitBegin : public ProgramPoint {
 public:
   // CallExitBegin uses the callee's location context.
-  CallExitBegin(const StackFrameContext *L)
-    : ProgramPoint(nullptr, CallExitBeginKind, L, nullptr) {}
+  CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS)
+    : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { }
 
 private:
   friend class ProgramPoint;
   CallExitBegin() {}
   static bool isKind(const ProgramPoint &Location) {
     return Location.getKind() == CallExitBeginKind;
   }
 };

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h

private:
   /// Handle conditional logic for running static initializers.
   void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
                         ExplodedNode *Pred);
 
 private:
   CoreEngine(const CoreEngine &) = delete;
   void operator=(const CoreEngine &) = delete;
 
-  ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
+  ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
+                                          const ReturnStmt *RS);
 
 public:
   /// Construct a CoreEngine object to analyze the provided CFG.
   CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS)
       : SubEng(subengine), WList(WorkList::makeDFS()),
         BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
 
   /// getGraph - Returns the exploded graph.
public:
   void enqueue(ExplodedNodeSet &Set);
 
   /// \brief Enqueue nodes that were created as a result of processing
   /// a statement onto the work list.
   void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
 
   /// \brief enqueue the nodes corresponding to the end of function onto the
   /// end of path / work list.
-  void enqueueEndOfFunction(ExplodedNodeSet &Set);
+  void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
 
   /// \brief Enqueue a single node created as a result of statement processing.
   void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
 };
 
 // TODO: Turn into a calss.
 struct NodeBuilderContext {
   const CoreEngine &Eng;

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

public:
   /// function has begun. Called for both inlined and and top-level functions.
   void processBeginOfFunction(NodeBuilderContext &BC,
                               ExplodedNode *Pred, ExplodedNodeSet &Dst,
                               const BlockEdge &L) override;
 
   /// Called by CoreEngine.  Used to notify checkers that processing a
   /// function has ended. Called for both inlined and and top-level functions.
   void processEndOfFunction(NodeBuilderContext& BC,
-                            ExplodedNode *Pred) override;
+                            ExplodedNode *Pred,
+                            const ReturnStmt *RS=nullptr) override;
 
   /// Remove dead bindings/symbols before exiting a function.
   void removeDeadOnEndOfFunction(NodeBuilderContext& BC,
                                  ExplodedNode *Pred,
                                  ExplodedNodeSet &Dst);
 
   /// Generate the entry node of the callee.
   void processCallEnter(NodeBuilderContext& BC, CallEnter CE,

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h

public:
   virtual void processBeginOfFunction(NodeBuilderContext &BC,
                                       ExplodedNode *Pred,
                                       ExplodedNodeSet &Dst,
                                       const BlockEdge &L) = 0;
 
   /// Called by CoreEngine.  Used to notify checkers that processing a
   /// function has ended. Called for both inlined and and top-level functions.
   virtual void processEndOfFunction(NodeBuilderContext& BC,
-                                    ExplodedNode *Pred) = 0;
+                                    ExplodedNode *Pred,
+                                    const ReturnStmt *RS = nullptr) = 0;
 
   // Generate the entry node of the callee.
   virtual void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
                                 ExplodedNode *Pred) = 0;
 
   // Generate the first post callsite node.
   virtual void processCallExit(ExplodedNode *Pred) = 0;
 

cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp

FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
                                            LC->getCFG()->getNumBlockIDs());
 
   // Check if we are entering the EXIT block.
   if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
 
     assert (L.getLocationContext()->getCFG()->getExit().size() == 0
             && "EXIT block cannot contain Stmts.");
 
+    // Get return statement..
+    const ReturnStmt *RS = nullptr;
+    if (!L.getSrc()->empty()) {
+      if (Optional<CFGStmt> LastStmt = L.getSrc()->back().getAs<CFGStmt>()) {
+        if (RS = dyn_cast<ReturnStmt>(LastStmt->getStmt())) {
+          if (!RS->getRetValue())
+            RS = nullptr;
+        }
+      }
+    }
+
     // Process the final state transition.
-    SubEng.processEndOfFunction(BuilderCtx, Pred);
+    SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
 
     // This path is done. Don't enqueue any more nodes.
     return;
   }
 
   // Call into the SubEngine to process entering the CFGBlock.
   ExplodedNodeSet dstNodes;
   BlockEntrance BE(Blk, Pred->getLocationContext());
void CoreEngine::enqueueStmtNode(ExplodedNode *N,
   bool IsNew;
   ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
   Succ->addPredecessor(N, G);
 
   if (IsNew)
     WList->enqueue(Succ, Block, Idx+1);
 }
 
-ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N) {
+ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
+                                                    const ReturnStmt *RS) {
   // Create a CallExitBegin node and enqueue it.
   const StackFrameContext *LocCtx
                          = cast<StackFrameContext>(N->getLocationContext());
 
   // Use the callee location context.
-  CallExitBegin Loc(LocCtx);
+  CallExitBegin Loc(LocCtx, RS);
 
   bool isNew;
   ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
   Node->addPredecessor(N, G);
   return isNew ? Node : nullptr;
 }
 
 
 void CoreEngine::enqueue(ExplodedNodeSet &Set) {
   for (ExplodedNodeSet::iterator I = Set.begin(),
                                  E = Set.end(); I != E; ++I) {
     WList->enqueue(*I);
   }
 }
 
 void CoreEngine::enqueue(ExplodedNodeSet &Set,
                          const CFGBlock *Block, unsigned Idx) {
   for (ExplodedNodeSet::iterator I = Set.begin(),
                                  E = Set.end(); I != E; ++I) {
     enqueueStmtNode(*I, Block, Idx);
   }
 }
 
-void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) {
+void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
   for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
     ExplodedNode *N = *I;
     // If we are in an inlined call, generate CallExitBegin node.
     if (N->getLocationContext()->getParent()) {
-      N = generateCallExitBeginNode(N);
+      N = generateCallExitBeginNode(N, RS);
       if (N)
         WList->enqueue(N);
     } else {
       // TODO: We should run remove dead bindings here.
       G.addEndOfPath(N);
       NumPathsExplored++;
     }
   }

cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp

void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
                                         const BlockEdge &L) {
   SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
   getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
 }
 
 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
 ///  nodes when the control reaches the end of a function.
 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
-                                      ExplodedNode *Pred) {
+                                      ExplodedNode *Pred,
+                                      const ReturnStmt *RS) {
   // FIXME: Assert that stackFrameDoesNotContainInitializedTemporaries(*Pred)).
   // We currently cannot enable this assert, as lifetime extended temporaries
   // are not modelled correctly.
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   StateMgr.EndPath(Pred->getState());
 
   ExplodedNodeSet Dst;
   if (Pred->getLocationContext()->inTopFrame()) {
     // Remove dead symbols.
     ExplodedNodeSet AfterRemovedDead;
     removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
 
     // Notify checkers.
     for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
         E = AfterRemovedDead.end(); I != E; ++I) {
       getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this);
     }
   } else {
     getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this);
   }
 
-  Engine.enqueueEndOfFunction(Dst);
+  Engine.enqueueEndOfFunction(Dst, RS);
 }
 
 /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
 ///  nodes by processing the 'effects' of a switch statement.
 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
   typedef SwitchNodeBuilder::iterator iterator;
   ProgramStateRef state = builder.getState();
   const Expr *CondE = builder.getCondition();

cfe/trunk/test/Analysis/inlining/InlineObjCClassMethod.m

else
       return 1;
 }
 @end
 @interface MyClassSelf : MyParentSelf
 @end
 @implementation MyClassSelf
 + (int)testClassMethodByKnownVarDecl {
   int y = [MyParentSelf testSelf];
-  return 5/y; // Should warn here.
+  return 5/y; // expected-warning{{Division by zero}}
 }
 @end
 int foo2() {
   int y = [MyParentSelf testSelf];
-  return 5/y; // Should warn here.
+  return 5/y; // expected-warning{{Division by zero}}
 }
 
 // TODO: We do not inline 'getNum' in the following case, where the value of 
 // 'self' in call '[self getNum]' is available and evaualtes to 
 // 'SelfUsedInParentChild' if it's called from fooA.
 // Self region should get created before we call foo and yje call to super 
 // should keep it live. 
 @interface SelfUsedInParent : NSObject

cfe/trunk/test/Analysis/unreachable-code-path.c

void test12(int x) {
   switch (x) {
   case 1:
     break; // not unreachable
   case 2:
     do { } while (0);
     break;
   }
 }
+
+// Don't merge return nodes in ExplodedGraph unless they are same.
+extern int table[];
+static int inlineFunction(const int i) {
+  if (table[i] != 0)
+    return 1;
+  return 0;
+}
+void test13(int i) {
+  int x = inlineFunction(i);
+  x && x < 10; // no-warning
+}