Page MenuHomePhabricator

[clang-tidy] misc-no-recursion: a new check
Needs ReviewPublic

Authored by lebedev.ri on Tue, Jan 7, 2:21 PM.

Details

Summary

Recursion is a powerful tool, but like any tool
without care it can be dangerous. For example,
if the recursion is unbounded, you will
eventually run out of stack and crash.

You can of course track the recursion depth
but if it is hardcoded, there can always be some
other environment when that depth is too large,
so said magic number would need to be env-dependent.
But then your program's behavior is suddenly more env-dependent.

Also, recursion, while it does not outright stop optimization,
recursive calls are less great than normal calls,
for example they hinder inlining.

Recursion is banned in some coding guidelines:

  • SEI CERT DCL56-CPP. Avoid cycles during initialization of static objects
  • JPL 2.4 Do not use direct or indirect recursion.
  • I'd say it is frowned upon in LLVM, although not banned

And is plain unsupported in some cases:

  • OpenCL 1.2, 6.9 Restrictions: i. Recursion is not supported.

So there's clearly a lot of reasons why one might want to
avoid recursion, and replace it with worklist handling.
It would be great to have a enforcement for it though.

This implements such a check.
Here we detect both direct and indirect recursive calls,
although since clang-tidy (unlike clang static analyzer)
is CTU-unaware, if the recursion transcends a single standalone TU,
we will naturally not find it :/

The algorithm is pretty straight-forward:

  1. Build call-graph for the entire TU. For that, the existing clang::CallGraph is re-used, although it had to be modified to also track the location of the call.
  2. Then, the hard problem: how do we detect recursion? Since we have a graph, let's just do the sane thing, and look for Strongly Connected Function Declarations - widely known as SCC. For that LLVM provides llvm::scc_iterator, which is internally an Tarjan's DFS algorithm, and is used throught LLVM, so this should be as performant as possible.
  3. Now that we've got SCC's, we discard those that don't contain loops. Note that there may be more than one loop in SCC!
  4. For each loopy SCC, we call out each function, and print a single example call graph that shows recursion -- it didn't seem worthwhile enumerating every possible loop in SCC, although i suppose it could be implemented.
    • To come up with that call graph cycle example, we start at first SCC node, see which callee of the node is within SCC (and is thus known to be in cycle), and recurse into it until we hit the callee that is already in call stack.

Diff Detail

Event Timeline

lebedev.ri created this revision.Tue, Jan 7, 2:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Jan 7, 2:21 PM

It'll be reasonable to add CERT alias.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
214

true

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
9

It'll be reasonable to add links to relevant coding guidelines.

It'll be reasonable to add CERT alias.

I'm not sure about that.
This diagnoses any potential recursion,
while CERT is much more specific than that.
(Avoid cycles during initialization of static objects)

lebedev.ri edited the summary of this revision. (Show Details)Tue, Jan 7, 2:55 PM
lebedev.ri updated this revision to Diff 236843.Wed, Jan 8, 9:05 AM
lebedev.ri marked an inline comment as done.

s/1/true/

So that is were the CTU question comes from? :)

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
21

That should be in the CallGraph code, adding a private operator overload does not feel right.

31

That stuff, too.

67

Why smart?

73

That method name looks confusing. isEmpty()? If not, why?

242

That should be a Note:

287

Please merge these two notes into one.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
28

nit: the private stuff is usually at the bottom in the other clang-tidy code. not sure if there is something in the coding standard though.

clang-tools-extra/docs/ReleaseNotes.rst
149

The technical details should not be in the release notes. Just that it finds recursion and diagnoses it.

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
127

Does the check find recursion through function pointers? (Probably not? Should be noted as limitation).

Please add cases from lambdas. And cases where recursion happens in templates / only with one of multiple instantiations.

lebedev.ri marked 8 inline comments as done.Sat, Jan 11, 10:00 AM

Thanks for taking a look.
Some deflective replies inline.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
21

I didn't want to put this into callgraph, because this
cements the fact that we do not care about sourceloc,
which may not be true for other users.
I can put it there, but if told so by it's code owners (@NoQ ?)

31

(same reasoning)

67

Because if it's just named ImmutableSet, why should it not just be a using ImmutableSet = DenseSet; const ImmutableSet ......?
This denotes it's different behaviour when in small-size mode and in non-small-size mode.

73

See how it's used, e.g. in count(), see SmallSet also.

242

I'm intentionally emitting it as a warning.

If i // NOLINT the main warning, does that not silence the related Notes?
I don't want NOLINTing the "main" function to silence the report for the rest of the functions in SCC.

bader added a subscriber: bader.Mon, Jan 13, 10:38 AM

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

lebedev.ri marked 3 inline comments as done.Mon, Jan 13, 11:12 AM

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

Implementing it elsewhere will be more restrictive in the future - somehow i suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?

bader added a subscriber: Naghasan.Tue, Jan 14, 4:08 AM

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

Implementing it elsewhere will be more restrictive in the future - somehow i suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?

SYCL doesn't require multi-TU support. AFAIK, ComputeCPP implementation is signle-TU. +@Naghasan to confirm/clarify.
The open source implementation I referred to, does support linking separately compiled object files, but still I think detecting single-TU recursion in clang is very useful.
Is it possible to have both: intra-TU diagnostics in clang and inter-TU diagnostics in clang-tidy tool? Share any infrastructure (e.g. recursion detection)?