jml@wally.altair.fr (10/05/90)
I wonder if there has been any research done on the behavior of records in
dataflow analysis. What I mean is that the algorithms for the building of
ud-chains or alias analysis that I have read about consider only simple
variables and arrays. But field selection introduces significant
complexity. For example:
s1: y = x;
...
s2: y->a = v;
...
s3: return (x->a.b);
There seems to be no definition of x->a.b reaching s3, though s2 is such a
definition, due to aliasing of x to y in s1, even if the field b does not
appear explicitly in s2.
I'd be really grateful if somebody could direct me to literature on this
problem.
[It seems to me that there's no extra complexity here beyond the problems
already introduced by pointers. Record offsets are all known at compile
time, and can be handled the same way as constant subscripts. Am I missing
something here? -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.jml@wally.altair.fr (10/09/90)
jml>The algorithms for the building of ud-chains or alias
jml>analysis that I have read about consider only simple
jml>variables and arrays. But field selection introduces
jml>significant complexity. [example skipped]
[It seems to me that there's no extra complexity here beyond
the problems already introduced by pointers. Record offsets
are all known at compile time, and can be handled the same
way as constant subscripts. Am I missing something here?
-John]
I must admit that the problem was much too hastily formulated. In fact,
although I gave an example in C-like notation, what I really had in mind
was an object-oriented language with lots of access paths involving
objects (i.e. in effect, references) and instance variables (i.e. field
selectors), with possible multiple inheritance over these (so that it may
not always be possible to compute offsets statically), and I had a strong
impression that the aliasing problem due to objects being accessed by
reference was compounded by the presence of those "dynamic" field
selectors. But in fact, this impression was probably wrong, for even if
field selectors are not actually represented by offsets, we could have an
intermediate language that admits only var.selector, and never
exp.selector; so alias analysis does not seem considerably complicated by
field selection. E.g., given the sets of aliases {y, x.b, t1} and
supposing t1.c and v have no aliases so far, the statement
t1.c <- v
would create the alias set {t1.c, v, y.c}, which reflects the aliasing
between y and t1, but not y and x.b, since access to an instance variable
of x.b would necessarily involve a simple variable, typically a temporary,
equal (in the sense of Lisp's eq) to x.b, rather than the expression x.b
itself.
However, the problem which does remain, in my opinion, is that the
pervasiveness of references in languages like Lisp and Smalltalk seems to
require alias analysis to be performed as part of reaching-definition or
available-expression analysis, and not as a complementary analysis whose
results were to be merged with the output of alias-free analysis.
---
Jean-Marie (John) Larcheveque
<jml@bdblues.altair.fr> or <jml@nuri.inria.fr>
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.