Re: Looking for Dependency Analysis Tool for C

Diego Novillo <dnovillo@redhat.com> wrote:
>On Mon, 2004-08-23 at 12:11, Gerald 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)
>>
>GCC will give you 1-3. From that it shouldn't be hard to get 4 and 5.
>At least an approximation.
>
>You need to get GCC out of CVS or a snapshot, though. We still have not
>released this functionality (expect it for GCC 3.5).


I agree about 1-3 being a suitable basis for producing an
approximation to 4 and 5. But gcc cannot do more than an
approximation to either 1 or 3 and, in the case of some of the more
interesting[*] features of C99, a VERY crude approximation. Let's
consider a couple of examples (this not being comp.std.c):


Counterexample to (1).


#ifdef __STDC_IEC_559__
        #pragma STDC FENV_ACCESS ON
... Usual usage omitted ...
        double a = ..., b;
        b = a+a;
#endif


Now, how do you convert the 'b = a+a;' to single-assignment form?
Depending on the value of a, it may assign to b or assign to b and
the floating-point flags. And, under the conditions I have specified,
those two assignations are atomic. 'b = a/a;' is marginally worse,
in that it assigns to the flags only if a is zero or an infinity.
There are similar issues with some library functions.


Counterexample to (3)


This gets very messy. If you want a longer and perhaps clearer
description of the problem, please ask for my "Objects" diatribe.
I don't have a solution - it merely describes the problem.


        typedef struct {int a; double b; int c;} COMPOSITE;
        COMPOSITE composite = {0,0.0,0};
        int *r;
        r = (int *)(((char *)&composite)+offsetof(COMPOSITE,c));
        composite.a = *r = 0.0;


As the joke goes, what and with which and to whom? Such code really
does exist (and I could name culprits), and no sane compiler is
likely to get far working out the aliasing. Especially as it can be
a LOT for obfuscated than that and even halting problem equivalent.




[*] "May you live in interesting times" - an ancient Chinese curse.




Regards,
Nick Maclaren.

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