Support muxing if statements

[cacay]

We need a function to compile if statements to straight-line programs. The function should have signature close to:

fun IfNode.asStraightLine(): List<SimpleStatementNode>

The "muxing" needs to be smart, and should try to merge the two branches. For example, the code

if (c) {
    output tmp1 to alice;
} else {
    output tmp2 to alice;
}

should get compiled to

val tmp = if (c) tmp1 else tmp2;
output tmp to alice;

In fact, there is no other way of compiling this code since we cannot duplicate the effectful output statement. Even operations that can be turned into no-ops would benefit from merging. For example:

if (c) {
    a[index] = tmp1;
} else {
    a[index] = tmp2;
}

can be compiled inefficiently as

a[index] = if (c) tmp1 else a[index];
a[index] = if (c) a[index] else tmp2; 

or more efficiently as

a[index] = if (c) tmp1 else tmp2;

I assume this merging would use dynamic programming, and might work similarly to diff code.

One thing to consider is nested control structures like ifs and loops. They don't necessarily have to be made into straight-line code. We only need to mux ifs with a secret guard. If they happen to contain control structures with public guards, we might be able to get away with not muxing those. Here is a contrived example:

if (secret) {
    if (public) {
        output result to alice;
    } else {
        output result to bob;
    }
} else {
    if (public) {
        output result to alice;
    } else {
        output result to bob;
    }
}

There is no way to mux the inner if because the two branches output to different hosts. But if we allow returning code with conditionals, the following code is equivalent to what we have above:

if (public) {
    output result to alice;
} else {
    output result to bob;
}

Essentially, there was no reason to case on secret.

This is a very contrived example, so I'm not sure that we have to worry about this case. But not having to unroll inner loops that use public guards would be nice. Additionally, there might be another, standard analysis that can hoist such code outside the if.

#45 might be related.

[rolph-recto]

closed by #85