423,321 Members | 1,167 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 423,321 IT Pros & Developers. It's quick & easy.

detect recursive C code

P: n/a
Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E
Nov 14 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
In article <68**************************@posting.google.com >,
Einar ?rn <or******@yahoo.se> wrote:
is there a good way to detect recursive C code in large systems? A
method or a free tool?


I don't know of anything specifically for that purpose, but many
profilers indicate recursive cycles in their output. This will only
detect recursive functions that are actually called of course.

-- Richard
Nov 14 '05 #2

P: n/a
On 28 Oct 2004 07:22:53 -0700, or******@yahoo.se (Einar ?rn) wrote:
Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E


I don't know if it meets the exact purpose, but I think GLOBAL is a
suitable tool to reverse engineer C source code and caller/callee
dependencies (http://www.gnu.org/software/global). You can of course
try doxygen (http://www.doxygen.org), it can create call-trees and
therefore should find recursions (although I never tried that)

Mark

Nov 14 '05 #3

P: n/a

In article <68**************************@posting.google.com >, or******@yahoo.se (Einar ?rn) writes:

is there a good way to detect recursive C code in large systems? A
method or a free tool?


There are a number of static-analysis tools that generate call graphs
from C source. Loops in the call graph indicate recursion. They're
not guaranteed, though:

- If the recursion only occurs in dead code which is never actually
executed, you may have a false positive (depending on how you define
"recursive C code" for your purposes).

- It's hard for analyzers to detect recursion through function
pointers, since they'd have to check every value such a pointer can
be set to by the program; so if the code uses function pointers you
could get false negatives.

Dynamic (runtime) analysis obviously suffers from flow coverage
issues - you can't rule out recursion until you've tested all
possible flow paths through the code.

In short, it's very difficult (maybe impossible, though I don't
offhand see a proof of that; this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

--
Michael Wojcik mi************@microfocus.com

When most of what you do is a bit of a fraud, the word "profession"
starts to look like the Berlin Wall. -- Tawada Yoko (t. M. Mitsutani)
Nov 14 '05 #4

P: n/a
mw*****@newsguy.com (Michael Wojcik) wrote in message news:<cl*********@news4.newsguy.com>...
(...) this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

Actually, it is. Informally, you need to determine that the program
can reach another particular point in the code (which is trivially
equivalent to the halting problem), given a particular starting point
before reaching another point (eg. the next line), which is an
additional complication.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

While quite implementation dependant (and using very undefined
behavior), if you can, on your implementation, walk the stack of
activation records, it's usually pretty easy to write a routine that
saves the callers address in an auto, and then looks through all the
stack frames looking for a duplicate. All you need in each routine is
something like "{void *RecurseTest; CheckRecursion(&RecurseTest,
__LINE__);}"
Nov 14 '05 #5

P: n/a
> dependencies (http://www.gnu.org/software/global). You can of course
try doxygen (http://www.doxygen.org), it can create call-trees and


Thanks for the answers, however I never found out how to use these
tools so I used the excelent tool cflow instead.

http://www.opengroup.org/onlinepubs/...ies/cflow.html

It prints a callgraph and marks the recursive functions.
E.
Nov 14 '05 #6

P: n/a
On 29 Oct 2004 15:48:59 GMT, mw*****@newsguy.com (Michael Wojcik)
wrote:
<snip>
A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.


Or a static flag, (as little as) one bit, for each function.

With somewhat simpler code; but still worth hiding, and also
automating which helps prevent cut&paste or other editing errors.
- David.Thompson1 at worldnet.att.net
Nov 14 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.