Re: UD-chains for fields

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>
--

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