Re: Looking for Dependency Analysis Tool for C

Gerald <grtmail@patmedia.net> wrote:
>I am looking for a tool that will take as input a C program
>1) Convert the code to a single assignment form like SSA
>2) Output the single assignment form as C code
>3) Perform alias analysis for stack-directed and heap-directed pointers
> (type-based, flow-insensitive analysis is sufficient)
>4) Perform dependency analysis between atomic blocks
> (def-use, def-def, use-def)
>5) Output the dependency as a relation on atomic blocks
> (each atomic block could have a unique label, then
> the dependency relation would be on the labels)


Well, that is a LITTLE easier than asking for one that will correct
your errors :-)


More seriously, the Fortran equivalent is Toolpack. There are many
reasons no such tool has ever been written for C, one of which is that
it isn't possible even to parse and analyse C without writing the
front-end of a C compiler. That is a LOT of work.


Now, such a tool could be built out of gcc, but that would mean it was
semi-specific to gcc - C codes for other compilers might not behave in
quite the same way, and ones that were particularly horrible would be
mishandled or rejected. Still, that's not an absolutely fatal
problem.


The real problem is that you want it to do dependency analysis. You
don't know what you are asking for :-(


The problem with C is that the language is SERIOUSLY undefined at that
level - and, by "the language", I mean ISO/ANSI C90 and C99. There
isn't even a concept of an atomic block, for a start (see C99, 5.1.2.3
#8, #9, and many other places). Also, the language is not fully
reducible to single assignment (think floating-point exception flags,
library functions like modf etc.) And, perhaps worst, there are
serious ambiguities about what an object is and what object access
means.


There have been several attempts to produce precise specifications of
the sequence point rules (the closest approximation to atomic blocks),
over many years, and the debate is still unresolved. The
ill-definition of an object is, as far as I know, not even on the list
to consider.


Sorry, but ....




Regards,
Nick Maclaren.

Return to the comp.compilers page.
Search the comp.compilers archives again.