Re: SSA in the presence of procedure calls

Edsko de Vries wrote on 09/28/06 22:51:


> int* global_a;
>
> void f()
> {
> *global_a = 2;
> }
>
> void g()
> {
> int a, b;
> global_a = &a;
> a = 1;
> f();
> b = a;
> }
>
> How do I translate g() into SSA form? The problem is, of course, the
> last assignment - what subscript do we give to a? Do we need to insert
> a phi-function after the call to f (since without interprocedural
> analysis we have no way of knowing whether f does or does not modify
> a)? Let me emphasize that I'm not looking for an interprocedural SSA: a
> "simple" intraprocedural SSA is okay, but I need to be able to deal
> with function calls.


It depends on whether the compiler you are using represents memory in
SSA form or not. GCC does it using a mechanism similar to the SGI
compiler (we call it Virtual SSA form). You can read details about this
in http://people.redhat.com/dnovillo/Papers/#gcc2004 or in the Tree SSA
section of the GCC internals manual starting with version 4.0.


Essentially, GCC rewrites into traditional SSA form all the variables
that it deems "registers" (variables of scalar types with local scope
and non-addressable). Everything else is deemed "memory" and it's
represented using virtual definition and virtual use operators (VDEF and
VUSES in GCC's parlance). The operands in these operators are renamed
using Factored Use-Def chains to keep both UD and DD chains.


> To my surprise, gcc simply generated
>
> a.0 = 1;
> f();
> b.0 = a.0;


That's indeed wrong. Which version of the compiler were you using? GCC
4.1 generates:


f ()
{
    # BLOCK 0 freq:10000
    # PRED: ENTRY [100.0%] (fallthru,exec)
    *global_a = 2;
    return;
    # SUCC: EXIT [100.0%]
}


g ()
{
    int a;


    # BLOCK 0 freq:10000
    # PRED: ENTRY [100.0%] (fallthru,exec)
    global_a = &a;
    a = 1;
    f ();
    return;
    # SUCC: EXIT [100.0%]
}


(b is killed during the first DCE pass). To see both forms, use the
-fdump-tree-all-vops switch. All the IL dumps generated will show both
the SSA and the Virtual SSA forms generated.


In this case, you should see for g() something like this for the initial
SSA form (after alias analysis):


g ()
{
    int b;
    int a;


    # BLOCK 0
    # PRED: ENTRY (fallthru)
    # global_a_2 = V_MUST_DEF <global_a_1>;
    global_a = &a;
    # a_4 = V_MUST_DEF <a_3>;
    a = 1;
    # global_a_6 = V_MAY_DEF <global_a_2>;
    # a_7 = V_MAY_DEF <a_4>;
    f ();
    # VUSE <a_7>;
    b_5 = a;
    return;
    # SUCC: EXIT
}


Future versions of GCC are going to include changes to the Virtual SSA
form, but up to version 4.2 you should get something like the above.

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