Compilers - Help with alias analysis framework

Author

Help with alias analysis framework

BerPast

2004-08-13, 8:57 pm

In the paper "Interprocedural may-alias analysis for pointers: beyond
k-limiting", the author presents a parametric framework for the
analysis of pointer aliases.
The framework is parametrised by a numeric lattice V#.
The lattice has to have some abstract operators; the 4th are 5th are
for me the most complex:
4) resolution of a linear system: given a system S, I need to compute
a member of the lattice which is an upper approximation of the integer
solutions to S;
5) intersection with a linear system: if S is a system of linear
equations and K is a member of the lattice, I need to compute an upper
approximation of the solutions to S that are also in K (no empty
intersection with K I guess).

I need to implement the lattice operators, but I have no idea of how
to do this. Probably using Fourier-Motzkin projection I can solve the
problem for the lattice obtained by the smash product of the interval
lattice (any other, more efficient method?), but how can this problem
be solved for a generic lattice?
Can someone point out to me some documentation and (if available code
implemenation) explaining how to solve this problem for a generic
lattice?

Thanks in advance for your help.
Regards,
Ber

Roberto Bagnara

2004-08-16, 3:57 am

BerPast wrote:
> In the paper "Interprocedural may-alias analysis for pointers: beyond
> k-limiting", the author presents a parametric framework for the
> analysis of pointer aliases.
> The framework is parametrised by a numeric lattice V#.
> [...]
>
> I need to implement the lattice operators [...] but how can this problem
> be solved for a generic lattice?

I am not sure I understand what you mean by "[solving] this problem [...]
for a generic lattice." All the numerical abstractions provided by the
Parma Polyhedra Library (http://www.cs.unipr.it/ppl/) come with the
operations that a numeric lattice must possess in Alain Deutsch's framework.
All the best,

Roberto Bagnara

--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@cs.unipr.it

Sponsored Links