[<<][meta][>>][..]
Wed Oct 19 10:00:21 EDT 2011

Stuck - control flow / nested scopes.

The problem seems to be that I don't have a good mental picture of
SSA.  I'm trying to use a C model of nested scopes, but I keep running
into arbitrary not-quite-right data representations.

Maybe it is better to bite the bullet and go for a proper SSA rep with
basic blocks and dominator structure.  This is a bit choice though
because I don't think that C can represent arbitrary SSA code, though
it can express some nesting like these:


void foo1(void) {

  a:
    {
        int x = 0;
        int y = 0;
        goto b;
    }
  b:
    {
        int x = 0;
        int y = 0;
        goto a;
    }
}

void foo2(void) {

  a:
    {
        int x = 0;
        int y = 0;
        goto b;

      b:
        {
            int x1 = x;
            int y1 = y;
            goto a;
        }
    }
}


Looks like I'm not going to pull this off before having some deeper
understanding of different nesting forms.  Maybe I have to embrace PHI
and GOTO and their relation to CPS anyway [1].

Reading [1] I'm tempted to just stick to recursion and local function
definitions, replacing the function calls with assignments and jumps
and just dumping out C code.  I have everything in the correct form
already; I don't need dominator analysis.  Also sticking to recursion
makes it possible to formulate combinators in a more abstract way.

I.e. to implement fold

// Initial arguments.
int arg1 = ..;
int arg2 = ..;

fun:

int out1 = op1(arg1, arg2, ...);
int out2 = op2(arg1, arg2, ...);

// recursive call
arg1 = out1;
arg2 = out2;
goto fun;

Using a left fold as a basic building block, it seems possible to
limit the recursion to only tail recursion, where it can be replaced
with assignment and goto (no other stack frames necessary).

In a similar vein, output storage could be seen as a function call
also.  Really, that "fun" function could take some extra "inputs"
which are only visible at the call site, and are represented as output
pointer storage abstracted in the fold.

So really, this is just fold of (s,i) -> (s,o) over some containers C
i, C o.  Let's work on that first.

Morale: don't use "for", use "fold".


Or actually not fold but some combination of cata[2] + anamorphism[3],
hylomorphism[4]... Find the correct way to express this.

See next post.

[1] http://www.cs.princeton.edu/~appel/papers/ssafun.ps
[2] http://en.wikipedia.org/wiki/Catamorphism
[3] http://en.wikipedia.org/wiki/Anamorphism
[4] http://en.wikipedia.org/wiki/Hylomorphism_(computer_science)


[Reply][About]
[<<][meta][>>][..]