Re:pointer elimination in C

Karen Miller writes...


>I am translating C into another language which does not implement pointers.


>Has anyone done any work on understanding what a particular pointer does.
>Does anyone have an algorithm for eliminating or replacing pointers in C
>code?


Pointer elimination in C seems to be a tricky problem. I believe one
would need sophisticated interprocedural alias analysis algorithm to track
down pointer targets. Now to replace a pointer dereference like *p with a
variable name like x, one needs to be sure at compile time that x is the
only possible target of pointer p, at the given program point. In other
words, must-alias information would be needed. Now, it is true that when
pointers are used to effect call-by-reference semantics, the pointer in
the called function remains must-aliased to the parameter whose address is
being passed, almost throughout the function body (as revealed by our
initial study with the points-to(alias) analysis algorithm implemented for
the McCAT C compiler). But the problem here is that the pointer target is
generally a variable, not visible inside the called function. Therefore
it is not obvious as to how to replace the pointer dereference with a
variable name. However, we have found that there are substantial number of
must-aliases which don't pose this problem.


If code size and efficiency is not an issue, pointer elimination can be
done even for pointers with may aliases: by using one conditional for each
possible alias.


For example consider stmt S: x = *p + 1;


Now if p possibly-points-to variables y and z before stmt S, we can have
code like


if (p == &y)
x = y+1;
else if (p==&z)
x = z+1;


I'm not sure, how useful would it be to eliminate pointers with
may-aliases, but it is definitely worth eliminating dereferences to
pointers with only one alias : imagine the number of memory accesses that
can be saved, if such a dereference is inside a deeply nested loop.


Hope this helps.


Rakesh Ghiya.


School of Computer Science,
McGill University,
Montreal, Canada.
[Does anyone have any idea in actual C code what fraction of pointer use
is easily turned into subscripts, what fraction is handled with hacks like
the one above (i.e. references can be shown to something with a local or
global name) and what fraction is to anonymous data? My guess is that the
third category, e.g. anything using malloc(), would dominate, making it
pretty hard to see how to turn it into non-subscript code other than by
putting everything in a big array and making the pointers subscripts into
that array. -John]
--

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