Re: SSA construction and aliased variables

Sergey Solyanik <sergey@solyanik.com> wrote:
> I have a question of how SSA form should treat aliased variables and
> globals. I was unable to find any mention of the problem in all works
> on SSA that I've read.
>
> Scenarion:
> ...
> However, if the code is
>
> if (a)
> {
> p = 1;
> }
> else
> {
> p = 2;
>
> function_call();
> }
>
> the result from translation back from SSA in the form
>
> if (a)
> {
> p1 = 1;
> p3 = p1;
> }
> else
> {
> p2 = 2;
> p3 = p1;
> function_call ();
> }
>
> is incorrect because function_call may change p.


One solution to this problem that we use in our optimizing compiler is
to introduce two pseudo instructions 'collect' and 'restore'.


if (a)
        {
        p1 = 1;
        }
else
        {
        p2 = 2;
        collect p2
        function_call ();
        p3 = restore
        }


A 'collect' instruction is inserted before every call to a
procedure. It forces every global variable that is accessed within the
callee back to memory. Correspondingly, a 'restore' instruction is
inserted after every call to a procedure. It forces every global
variable that is changed within the called to be reloaded. You can
either use interprocedural dataflow analysis to determine which
variables to store and restore or you can take a conservative approach
and store and restore every global variable.


Later, the 'collect' and 'restore' instructions are translated into
loads and stores. This is done in a special compilation phase because
some 'collect' and 'restore' sequences can be optimized away, e.g.


        {
        p2 = 2;
        collect p2
        function_call ();
        p3 = restore
        ...
        // p is not used between these two function calls
        ...
        collect p3
        function_call ();
        p4 = restore
        }


becomes the following after removal of the first 'restore'
and second 'collect' instruction.


        {
        p2 = 2;
        collect p2
        function_call ();
        ...
        function_call ();
        p3 = restore
        }


Another note: Translation out of SSA form can be done much easier
during register allocation instead of in a separate pass. During
register allocation both interference and liveness information are
available and do not have to be constructed separately.


Thomas Kistler
Information and Computer Science
University of California, Irvine


--

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