[analyzer] A better CFG-based suppress-on-sink.

[NoQ]

Summary

Because D28023 wasn't enough, as i've just seen an assertion-like macro with as many as 12 CFG blocks (including do..while(false) loops), i mocked up a quick CFG depth-first search to easily detect blocks dominated by noreturn blocks.

[a.sidorin]

Just a minor nit.

lib/StaticAnalyzer/Core/BugReporter.cpp

3332

The check for visited can be placed into the loop below so we won't even add such blocks to the worklist.

[NoQ]

Reduce stack operations as Alexey suggested.

[dcoughlin]

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

3313 ↗

(On Diff #108024)

Do you really mean "is dominated by"? That is, "every path from the entry to N's block goes through a no-return block"? Or do you mean "the exit block is not reachable from N's block"?

lib/StaticAnalyzer/Core/BugReporter.cpp

static const CFGBlock *findBlockForNode(const ExplodedNode *N) {
   // Find the node's current statement in the CFG.
   if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
     return N->getLocationContext()->getAnalysisDeclContext()
                                   ->getCFGStmtMap()->getBlock(S);
 
   return nullptr;
 }
 
+static bool isDominatedByNoReturnBlocks(const ExplodedNode *N) {
+  const CFG &Cfg = N->getCFG();
+
+  const CFGBlock *StartBlk = findBlockForNode(N);
+  if (!StartBlk)
+    return false;
+
+  llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
+  llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
+
+  DFSWorkList.push_back(StartBlk);
+  while (!DFSWorkList.empty()) {
+    const CFGBlock *Blk = DFSWorkList.back();
+    DFSWorkList.pop_back();
+
+    if (Blk->hasNoReturnElement()) {
+      // Nice, this block is noreturn. What about other blocks?
+      continue;
+    }
+
+    if (Blk == &Cfg.getExit()) {
+      // We're leaving the current CFG. We're no longer sure what happens next.
+      return false;
+    }
+
+    if (Visited.count(Blk)) {
+      // We've encountered a loop. We won't see anything new here anymore.
+      continue;
+    }
+    Visited.insert(Blk);
+
+    for (const auto &Succ : Blk->succs()) {
+      // See what's going on in reachable child blocks.
+      if (const CFGBlock *SuccBlk = Succ.getReachableBlock())
+        DFSWorkList.push_back(SuccBlk);
+    }
+  }
+
+  // Nothing reached the exit. It can only mean one thing: there's no return.
+  return true;
+}
+
 static BugReport *
 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
                              SmallVectorImpl<BugReport*> &bugReports) {
 
   BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
   assert(I != E);
   BugType& BT = I->getBugType();
 
for (; I != E; ++I) {
     // See if we are in a no-return CFG block. If so, treat this similarly
     // to being post-dominated by a sink. This works better when the analysis
     // is incomplete and we have never reached a no-return function
     // we're post-dominated by.
     // This is not quite enough to handle the incomplete analysis case.
     // We may be post-dominated in subsequent blocks, or even
     // inter-procedurally. However, it is not clear if more complicated
     // cases are generally worth suppressing.
-    if (const CFGBlock *B = findBlockForNode(errorNode))
-      if (B->hasNoReturnElement())
-        continue;
+    if (isDominatedByNoReturnBlocks(errorNode))
 
     // At this point we know that 'N' is not a sink and it has at least one
     // successor.  Use a DFS worklist to find a non-sink end-of-path node.
     typedef FRIEC_WLItem WLItem;
     typedef SmallVector<WLItem, 10> DFSWorkList;
     llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
 
     DFSWorkList WL;

test/Analysis/max-nodes-suppress-on-sink.c

 
 typedef __typeof(sizeof(int)) size_t;
 void *malloc(size_t);
 
 extern void exit(int) __attribute__ ((__noreturn__));
 
 void clang_analyzer_warnIfReached(void);
 
+int coin();
+
 void test_single_cfg_block_sink() {
   void *p = malloc(1); // no-warning (wherever the leak warning may occur here)
 
   // Due to max-nodes option in the run line, we should reach the first call
   // but bail out before the second call.
   // If the test on these two lines starts failing, see if modifying
   // the max-nodes run-line helps.
   clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
   clang_analyzer_warnIfReached(); // no-warning
 
   // Even though we do not reach this line, we should still suppress
   // the leak report.
   exit(0);
 }
+
+// A similar test with more complicated control flow before the no-return thing,
+// so that the no-return thing wasn't in the same CFG block.
+void test_more_complex_control_flow_before_sink() {
+  void *p = malloc(1); // no-warning
+
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+  clang_analyzer_warnIfReached(); // no-warning
+
+  if (coin())
+    exit(0);
+  else
+    exit(1);
+}
+
+// A loop before the no-return function, to make sure that
+// the dominated-by-sink analysis doesn't hang.
+void test_loop_before_sink(int n) {
+  void *p = malloc(1); // no-warning
+
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+  clang_analyzer_warnIfReached(); // no-warning
+
+  for (int i = 0; i < n; ++i) {
+  }
+  exit(1);
+}
+
+// We're not sure if this is no-return.
+void test_loop_with_sink(int n) {
+  void *p = malloc(1); // expected-warning@+2{{Potential leak of memory}}
+
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+  clang_analyzer_warnIfReached(); // no-warning
+
+  for (int i = 0; i < n; ++i)
+    if (i == 0)
+      exit(1);
+}
+
+// Handle unreachable blocks correctly.
+void test_unreachable_successor_blocks() {
+  void *p = malloc(1); // no-warning
+
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+  clang_analyzer_warnIfReached(); // no-warning
+
+  if (1) // no-crash
+    exit(1);
+}