Page MenuHomePhabricator

Improve -Winfinite-recursion

Authored by CodaFi on Feb 24 2018, 8:11 PM.



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.

Diff Detail


Event Timeline

CodaFi created this revision.Feb 24 2018, 8:11 PM

Please upload patches with full diff (-U999999)

CodaFi updated this revision to Diff 135827.Feb 25 2018, 8:03 AM

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) {
rtrieu added inline comments.Feb 27 2018, 9:45 PM
255–257 ↗(On Diff #135827)

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

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?

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.

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.

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 updated this revision to Diff 138302.Mar 13 2018, 11:44 PM

Respond to code review

CodaFi marked 5 inline comments as done.Mar 13 2018, 11:44 PM

Two more changes, then everything is good to commit.

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;

CodaFi updated this revision to Diff 139325.Mar 21 2018, 10:28 AM
CodaFi marked 2 inline comments as done.
rtrieu accepted this revision.Mar 21 2018, 4:05 PM

Looks good. Ready to commit.

This revision is now accepted and ready to land.Mar 21 2018, 4:05 PM
This revision was automatically updated to reflect the committed changes.

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) {
  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.

Herald added a project: Restricted Project. · View Herald TranscriptFeb 7 2019, 11:34 AM