[RFC][StaticAnalyser] fix unreachable code false positives when block numbers mismatch

[danielmarjamaki]

Summary

This is a RFC mostly.

There are false positives from the unreachable code check when the block numbers in the ExplodedGraph and CFG mismatch.

If it should be allowed that they mismatch then this patch can handle such situations.

If the block numbers should match, then I'll investigate why they mismatch. Is it guaranteed what block numbers there will be for the CFG blocks for such code:

void test12(int x) {
  switch (x) {
  case 1:
    break;
  case 2:
    do { } while (0);
    break;
  }
}

If so.. what is the correct block numbers?

[zaks.anna]

Sorry, I do not understand the question. What are block numbers?

[dcoughlin]

@danielmarjamaki I see what you mean -- thanks for providing the patch.

I don't think this is the right approach. It should be sufficient to reason about blocks and not individual statements; further some blocks may be non-empty but not have any statements.

Instead, I think the better approach is make sure the optimized and unoptimized CFGs match block IDs. It looks like the only situation where there is currently a mismatch is do { } while (0);.

I sketched out an approach on cfe-dev for hoisting block creation (but not edge creation) in CFGBuilder::VisitDoStmt() during CFG construction to match the other control flow constructs. That is the approach I would recommend taking.

[dcoughlin]

Here is the discussion on cfe-dev. http://lists.llvm.org/pipermail/cfe-dev/2016-September/050800.html

What's going on is that the path-sensitive unreachable code checker traverses blocks in the unoptimized CFG and emits a diagnostic if a block in that CFG is not reachable. But it decides whether a block is reachable by using the exploded node graph, which itself refers to the *optimized* CFG.

Normally this isn't a problem because the difference between the unoptimized and optimized CFGs is that the latter prunes edges that are trivially false (but the two CFGs have the same blocks). Unfortunately, there is a bug in CFG construction for do-while loops that also prunes a block. Since the block ids are constructed sequentially, the block IDs between the two CFGs don't match up and so the unreachable code checker gets confused.

I think the best fix here is to change construction of the optimized CFG to not prune the block in VisitDoStmt(). This matches what I think is the expected meaning of the 'PruneTriviallyFalseEdges' CFG option.

[danielmarjamaki]

Thanks!

I somehow missed your answer in cfe-dev.

I will continue working on this and hopefully have a proper patch soon.

[danielmarjamaki]

Updated CFGBuilder::VisitDoStmt

[danielmarjamaki]

My change is causing a false negative in the test/Analysis/uninit-sometimes.cpp. As far as I see my change anyway makes the unoptimized CFG better.

[dcoughlin]

lib/Analysis/CFG.cpp

2986

You need to keep this check so that the optimized CFG still removes edges that are trivially known to be false.

2994

To keep the unoptimized and optimized blocks in sync, this block creation needs to be done regardless of whether the branch condition is known to be false. My advice would be to hoist the creation (and the FIXME comments) to above the check for whether KnownVal is false.

[danielmarjamaki]

Fixed review comments by Devin. It works better now!

lib/Analysis/CFG.cpp

2986

Thanks

2994

Thanks

[dcoughlin]

LGTM. Please commit!

[danielmarjamaki]

r283095

lib/Analysis/CFG.cpp

CFGBlock *BodyBlock = nullptr;
 
     if (!BodyBlock)
       BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
     else if (Block) {
       if (badCFG)
         return nullptr;
     }
 
-    if (!KnownVal.isFalse()) {
-      // Add an intermediate block between the BodyBlock and the
-      // ExitConditionBlock to represent the "loop back" transition.  Create an
-      // empty block to represent the transition block for looping back to the
-      // head of the loop.
-      // FIXME: Can we do this more efficiently without adding another block?
-      Block = nullptr;
-      Succ = BodyBlock;
-      CFGBlock *LoopBackBlock = createBlock();
-      LoopBackBlock->setLoopTarget(D);
 
+    if (!KnownVal.isFalse())
       // Add the loop body entry as a successor to the condition.
       addSuccessor(ExitConditionBlock, LoopBackBlock);
-    }
     else
       addSuccessor(ExitConditionBlock, nullptr);
   }
 
   // Link up the condition block with the code that follows the loop.
   // (the false branch).
   addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
 

test/Analysis/unreachable-code-path.c

void testInlined() {
   int cond = coin();
   if (!cond) {
     inlined(0);
     if (cond) {
       foo(5); // expected-warning {{never executed}}
     }
   }
 }
+
+// Ensure that ExplodedGraph and unoptimized CFG match.
+void test12(int x) {
+  switch (x) {
+  case 1:
+    break; // not unreachable
+  case 2:
+    do { } while (0);
+    break;
+  }
+}