[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 ↗

(On Diff #72252)

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

2994 ↗

(On Diff #72252)

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 ↗

(On Diff #72252)

Thanks

2994 ↗

(On Diff #72252)

Thanks

[dcoughlin]

LGTM. Please commit!

[danielmarjamaki]

r283095

lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp

 
 namespace {
 class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
 public:
   void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
                         ExprEngine &Eng) const;
 private:
   typedef llvm::SmallSet<unsigned, 32> CFGBlocksSet;
+  typedef llvm::SmallSet<const Stmt *, 32> StmtsSet;
 
   static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
   static void FindUnreachableEntryPoints(const CFGBlock *CB,
                                          CFGBlocksSet &reachable,
                                          CFGBlocksSet &visited);
   static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
   static inline bool isEmptyCFGBlock(const CFGBlock *CB);
 };
 }
 
 void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
                                               BugReporter &B,
                                               ExprEngine &Eng) const {
   CFGBlocksSet reachable, visited;
 
   if (Eng.hasWorkRemaining())
     return;
 
+  StmtsSet ReachableStmts;
   const Decl *D = nullptr;
   CFG *C = nullptr;
   ParentMap *PM = nullptr;
   const LocationContext *LC = nullptr;
   // Iterate over ExplodedGraph
   for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
       I != E; ++I) {
     const ProgramPoint &P = I->getLocation();
     LC = P.getLocationContext();
     if (!LC->inTopFrame())
       continue;
 
     if (!D)
       D = LC->getAnalysisDeclContext()->getDecl();
 
     // Save the CFG if we don't have it already
     if (!C)
       C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
     if (!PM)
       PM = &LC->getParentMap();
 
     if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
       const CFGBlock *CB = BE->getBlock();
       reachable.insert(CB->getBlockID());
+      ReachableStmts.insert(getUnreachableStmt(CB));
     }
   }
 
   // Bail out if we didn't get the CFG or the ParentMap.
   if (!D || !C || !PM)
     return;
 
   // Don't do anything for template instantiations.  Proving that code
if (!CB->empty()) {
         continue;
     }
 
     // We found a block that wasn't covered - find the statement to report
     SourceRange SR;
     PathDiagnosticLocation DL;
     SourceLocation SL;
     if (const Stmt *S = getUnreachableStmt(CB)) {
+      if (ReachableStmts.count(S))
+        continue;
       SR = S->getSourceRange();
       DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
       SL = DL.asLocation();
       if (SR.isInvalid() || !SL.isValid())
         continue;
     }
     else
       continue;

test/Analysis/unreachable-code-path.c

void testInlined() {
   int cond = coin();
   if (!cond) {
     inlined(0);
     if (cond) {
       foo(5); // expected-warning {{never executed}}
     }
   }
 }
+
+// Block numbers in the ExplodedGraph and CFG mismatch.
+void test12(int x) {
+  switch (x) {
+  case 1:
+    break;
+  case 2:
+    do { } while (0);
+    break;
+  }
+}