Improve -Winfinite-recursion

[CodaFi]

Summary

Rewrites -Winfinite-recursion to remove the state dictionary and explore paths in loops - especially infinite loops. The new check now detects recursion in loop bodies dominated by a recursive call.

[lebedev.ri]

Please upload patches with full diff (-U999999)

[rtrieu]

Can you explain the new algorithm for checking recursive calls?

From the test, this code looks like what you are testing for, but it doesn't trigger the warning.

void f() {
  while(true) {
    f();
  }
}

[rtrieu]

lib/Sema/AnalysisBasedWarnings.cpp

255–257 ↗

(On Diff #135827)

This is likely what is causing my previous code example to fail.

[CodaFi]

Can you explain the new algorithm for checking recursive calls?

The idea is to de-clutter as much of the existing algorithm as possible. The state dictionary is done away with now in favor of just not enqueueing successors of CFG blocks that have recursive calls. Given an arbitrary CFG, the algorithm attempts DFS for a path from the entry node to the exit node - terminating search on any path dominated by a recursive call.

but it doesn't trigger the warning.

There's a condition around the reachability of the exit node hindering that that I didn't want to touch. I believe you were around this code last, so can you remember why it was there?

[rtrieu]

I believe you were around this code last, so can you remember why it was there?

Yes, that's an early exit to speed up the check. You can remove that check and add a test case for it.

This was a little confusing for me, so let's refactor it a little. These changes will make it so that any CFGBlock in the WorkList has already been checked, so it can go straight to checking the successors.

lib/Sema/AnalysisBasedWarnings.cpp

203–204 ↗

(On Diff #135827)

Update comment to reflect your changes.

224–225 ↗

(On Diff #135827)

The entry CFGBlock is special. It will never trigger on any of the conditions we are checking for. Just push it into WorkList and Visited. It has no statements, so it can't have a recursive call.

http://clang.llvm.org/docs/InternalsManual.html#entry-and-exit-blocks

Technically, it has no incoming edges, so you don't even need to insert it into Visited.

232–233 ↗

(On Diff #135827)

ID is not longer needed as an index so it is only needed here, so it should be inlined.

Also, move this check in the loop over the successors, so there are no checks on the current CFG block. This way, all checks happen at the same place.

237 ↗

(On Diff #135827)

Since the lambda isn't needed for seeding the WorkList, this is the only use and it should be inlined here.

Also, use:

if (cond)
  foundRecursion = true;

instead of:

foundRecursion |= true;

[CodaFi]

Respond to code review

[rtrieu]

Two more changes, then everything is good to commit.

lib/Sema/AnalysisBasedWarnings.cpp

218–220 ↗

(On Diff #138302)

Move this to checking the ID of the successor block instead of the current block.

227–233 ↗

(On Diff #138302)

This would make more sense if you flip the conditional:

if (hasRecursiveCallInPath(FD, *SuccBlock)) {
  foundRecursion = true;
  continue;
}

WorkList.push_back(SuccBlock);

[rtrieu]

Looks good. Ready to commit.

[steven_wu]

Sorry for following up late on the patch. Removing the reachability testing for the exit block causes false positive for infinite loop cases like this:

void l() {
  static int count = 5;
  if (count >0) {
    count--;
    l();
  }
  while (true) {}
}

Can you take a look? I was attempting to write a fix but then I figure out it is very much the same as old algorithm.

cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp

for (const auto &B : Block) {
     const CXXMemberCallExpr *MCE = dyn_cast<CXXMemberCallExpr>(CE);
     if (!MCE || isa<CXXThisExpr>(MCE->getImplicitObjectArgument()) ||
         !MCE->getMethodDecl()->isVirtual())
       return true;
   }
   return false;
 }
 
-// All blocks are in one of three states.  States are ordered so that blocks
-// can only move to higher states.
-enum RecursiveState {
-  FoundNoPath,
-  FoundPath,
-  FoundPathWithNoRecursiveCall
-};
-
-// Returns true if there exists a path to the exit block and every path
-// to the exit block passes through a call to FD.
+// Returns true if every path from the entry block passes through a call to FD.
 static bool checkForRecursiveFunctionCall(const FunctionDecl *FD, CFG *cfg) {
+  llvm::SmallPtrSet<CFGBlock *, 16> Visited;
+  llvm::SmallVector<CFGBlock *, 16> WorkList;
+  // Keep track of whether we found at least one recursive path.
+  bool foundRecursion = false;
 
   const unsigned ExitID = cfg->getExit().getBlockID();
 
-  // Mark all nodes as FoundNoPath, then set the status of the entry block.
-  SmallVector<RecursiveState, 16> States(cfg->getNumBlockIDs(), FoundNoPath);
-  States[cfg->getEntry().getBlockID()] = FoundPathWithNoRecursiveCall;
-
-  // Make the processing stack and seed it with the entry block.
-  SmallVector<CFGBlock *, 16> Stack;
-  Stack.push_back(&cfg->getEntry());
+  // Seed the work list with the entry block.
+  WorkList.push_back(&cfg->getEntry());
 
-  while (!Stack.empty()) {
-    CFGBlock *CurBlock = Stack.back();
-    Stack.pop_back();
+  while (!WorkList.empty()) {
+    CFGBlock *Block = WorkList.pop_back_val();
 
-    unsigned ID = CurBlock->getBlockID();
-    RecursiveState CurState = States[ID];
+    for (auto I = Block->succ_begin(), E = Block->succ_end(); I != E; ++I) {
+      if (CFGBlock *SuccBlock = *I) {
+        if (!Visited.insert(SuccBlock).second)
+          continue;
 
-    if (CurState == FoundPathWithNoRecursiveCall) {
         // Found a path to the exit node without a recursive call.
-      if (ExitID == ID)
+        if (ExitID == SuccBlock->getBlockID())
           return false;
 
-      // Only change state if the block has a recursive call.
-      if (hasRecursiveCallInPath(FD, *CurBlock))
-        CurState = FoundPath;
+        // If the successor block contains a recursive call, end analysis there.
+        if (hasRecursiveCallInPath(FD, *SuccBlock)) {
+          foundRecursion = true;
+          continue;
         }
 
-    // Loop over successor blocks and add them to the Stack if their state
-    // changes.
-    for (auto I = CurBlock->succ_begin(), E = CurBlock->succ_end(); I != E; ++I)
-      if (*I) {
-        unsigned next_ID = (*I)->getBlockID();
-        if (States[next_ID] < CurState) {
-          States[next_ID] = CurState;
-          Stack.push_back(*I);
-        }
-      }
+        WorkList.push_back(SuccBlock);
   }
-
-  // Return true if the exit node is reachable, and only reachable through
-  // a recursive call.
-  return States[ExitID] == FoundPath;
+  return foundRecursion;
 }
 
 static void checkRecursiveFunction(Sema &S, const FunctionDecl *FD,
                                    const Stmt *Body, AnalysisDeclContext &AC) {
   FD = FD->getCanonicalDecl();
 
   // Only run on non-templated functions and non-templated members of
   // templated classes.
   if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate &&
       FD->getTemplatedKind() != FunctionDecl::TK_MemberSpecialization)
     return;
 
   CFG *cfg = AC.getCFG();
   if (!cfg) return;
 
-  // If the exit block is unreachable, skip processing the function.
-  if (cfg->getExit().pred_empty())
-    return;
-
   // Emit diagnostic if a recursive function call is detected for all paths.
   if (checkForRecursiveFunctionCall(FD, cfg))
     S.Diag(Body->getLocStart(), diag::warn_infinite_recursive_function);
 }
 
 //===----------------------------------------------------------------------===//
 // Check for throw in a non-throwing function.
 //===----------------------------------------------------------------------===//

cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp

 
 // Doesn't warn on mutually recursive functions
 void e();
 void f();
 
 void e() { f(); }
 void f() { e(); }
 
-// Don't warn on infinite loops
-void g() {
+void g() {  // expected-warning{{call itself}}
   while (true)
     g();
 
   g();
 }
 
 void h(int x) {
   while (x < 5) {
     h(x+1);
   }
 }
 
 void i(int x) {  // expected-warning{{call itself}}
   while (x < 5) {
     --x;
   }
   i(0);
 }
 
 int j() {  // expected-warning{{call itself}}
   return 5 + j();
 }
 
+void k() {  // expected-warning{{call itself}}
+  while(true) {
+    k();
+  }
+}
+
+// Don't warn on infinite loops
+void l() {
+  while (true) {}
+
+  l();
+}
+
 class S {
   static void a();
   void b();
 };
 
 void S::a() {  // expected-warning{{call itself}}
   return a();
 }