How to get a warning for using recursion?

Question

Some rule sets and guidelines of embedded software development forbid recursion entirely. I use arm-none-eabi-gcc with an ARM Cortex-M4 based microcontroller.

I'm looking for a static analysis tool which would warn me about the use of recursion in the code. I have little experience with such tools. Is it possible to use clang-tidy or the clang static analyzer for this? If yes, how can I configure them to warn about recursion?

(A quick look at the gcc option summary tells me that gcc alone can't do this.)

NOTE:

Please don't tell me "just don't recurse". The code base is big and not mine alone. I'd like to be able to prove that there is no recursion in it.
(That is like saying "just don't dereference a null pointer". While nobody does on purpose, tools exist for a reason to verify that it doesn't happen.)

If you need someone watching over your sholder programming, do a peer-review. Otherwise, just don't write recursive code! By desing, the compiler **cannot** warn you about recursion - unless you only use `static` functions and no function pointers. — too honest for this site, Jul 19 '17 at 15:09
@Olaf well it could warn you if you use recursion with static functions (which is the kind of recursion that is done most of the time). — Jabberwocky, Jul 19 '17 at 15:13
`gcc` is first and foremost a compiler, and could but does not do a number of static analysis functions. There are, however, a number of available 3rd party static analysis tools that generate call graphs, etc. This would be most useful if you've inherited or must analyze a large body of source code. If it's new code, then design practice and peer reviews is the appropriate way to achieve it. — lurker, Jul 19 '17 at 15:15
As written, I think this question is either too broad or requesting a tool recommendation. Certainly, the clang library could be used to implement a static analysis which would detect *some* recursive calls. If you are interested, it might make for a good starter project, and if you run into trouble, specific questions would be welcome. — rici, Jul 19 '17 at 15:49
I don't understand. Are you a split personality guy? You wake up in the morning and notice that the second you has written something when you were sleeping. Just do not recurse. — 0___________, Jul 19 '17 at 15:52
@MichaelWalz: Either SO delivers comments differently to different users, or your browser suppressed part of my comment or you didn't read it completely. I'm pretty sure I already stated that: "unless you only use static functions and no function pointers" (note you forgot about the second part) — too honest for this site, Jul 19 '17 at 16:05
Related: [is there a tool that will detect a recursive function call in C code](https://stackoverflow.com/questions/7909148/is-there-a-tool-that-will-detect-a-recursive-function-call-in-c-code) — Mark Plotnick, Jul 19 '17 at 17:12
Possible duplicate of [is there a tool that will detect a recursive function call in C code?](https://stackoverflow.com/questions/7909148/is-there-a-tool-that-will-detect-a-recursive-function-call-in-c-code) — ugoren, Jul 19 '17 at 21:17

score 5 · Accepted Answer · answered Jul 20 '17 at 04:54

This is solvable using callgraph data generated by Clang.

Step 1. Generate call graph information using clang:

clang -S -emit-llvm SourceFile.c -o - | opt -analyze -print-callgraph

(From Generate calling graph for C++ code, replacing -dot-callgraph with -print-callgraph.)

For an input like:

void a(){}
void b(){a();}
void c(){a(); b();}
void d(){a(); c();}
void e(){e();}

this will produce:

CallGraph Root is: <<null function: 0x0x7fdef25036c0>>
Call graph node <<null function>><<0x7fdef25036c0>>  #uses=0
  CS<0x0> calls function 'a'
  CS<0x0> calls function 'b'
  CS<0x0> calls function 'c'
  CS<0x0> calls function 'd'

Call graph node for function: 'a'<<0x7fdef2503750>>  #uses=4

Call graph node for function: 'b'<<0x7fdef25037d0>>  #uses=2
  CS<0x7fdef2500a38> calls function 'a'

Call graph node for function: 'c'<<0x7fdef2503870>>  #uses=2
  CS<0x7fdef2500cb8> calls function 'a'
  CS<0x7fdef2500d28> calls function 'b'

Call graph node for function: 'd'<<0x7fdef2503970>>  #uses=1
  CS<0x7fdef2500fe8> calls function 'a'
  CS<0x7fdef2501058> calls function 'c'

Call graph node for function: 'e'<<0x7f8912d03c10>>  #uses=2
  CS<0x7f8912d01318> calls function 'e'

(In C++, mangled function names can be cleaned up with c++filt; templates get ugly but are doable.) With that data, it's possible to sketch out how one detects recursion:

Step 2. Parse callgraph data into favorite scripting language to form representation of callgraph.

class Graph(object):

  _callees = []

  def add_callee(self, f):
    self._callees.append(f)
    # etc

Step 3. For each function, walk graph looking for calls to that function. Something kind of like this:

def walkGraph(node,f,stack):
  for callee in node._callees:
    if f == callee:
      print('Recursion!')
      dumpStack(stack,f)
    else:
      walkGraph(callee,f,stack.append(node))

score 2 · Answer 2 · answered Nov 28 '20 at 16:05

2

clang-tidy learned to detect this in version 11.

https://clang.llvm.org/extra/clang-tidy/checks/misc-no-recursion.html

answered Nov 28 '20 at 16:05

Mathias

1,446
2
16
31

score 0 · Answer 3 · answered Jul 19 '17 at 16:16

You can investigate tools to produce call trees. They might have an option to detect recursion, including mutual recursion, otherwise you might be able to patch one to get the functionality you want.

See this reponse

A this commercial tool from Roguewave software: TotalView

How to get a warning for using recursion?

3 Answers3