Re: Papers on dealing with aliases during SSA construction

Sergey Solyanik wrote:


> The subject says it all - I am looking for work related to dealing
> with aliases during the construction of SSA form.


There was one by Chase, Wegman, and Zadeck in PLDI in 1990. I'm
pretty sure that there is at least one bug in that paper; there's a
non-monotonic glitch in the name-reassignment at loop headers. I
don't think that is a problem for simple one-level aliasing; it had to
do with pointers some distance into linked lists.


Ron Cytron had a different approach some years later, I think.


> Any insight is greatly appreciated.


Our paper conveyed less insight than I would have liked. The two
insights that are very important are


(1) remember is that it is easier to add than it is to delete


(2) you should choose a proper modelling of erroneous states
        (dereferencing a "top" (*) or null value is an error).
        Two models that work are
        (a) halt execution down this path.
        (b) ALL values go to top.


(*) data flow top, abstract interpretation bottom.


We also avoided the renaming step by using a scope-lookup trick that
was discovered by Paul Dietz (STOC 1980, I think). It worked here
because in SSA every input to an expression (except for phi functions)
has a single input, and that single input dominates the expression.
Thus, no names are assigned while the analysis is running, which means
adding new assignments is not so costly (otherwise, you may do a bunch
of renaming). Afterwards, you can assign names.
--
David Chase, chase@world.std.com
--

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