I have updated the algorithm to fix a few bugs and make it more readable.

I have implemented a simple algorithm to convert PHI instructions into an equivalent sequence of register move and exchange instructions. This is a non-trivial task because PHI instructions are assumed to execute in parallel while actual moves execute in sequence, possibly overwriting values that will still be needed by subsequent moves. To ensure proper semantics we have to order the moves we emit such context slots are only written to after all read dependencies have been satisfied. In case of cycles in the data flow this is not always possible:

int a, b;
for (...) {
    int t = a;
    a = b;
    b = t;
}

In SSA form and after copy propagation has been performed, this loop consists of the PHI instructions (a←b, b←a) only. There is no ordering in which sequential moves can ensure an equivalent data flow. Preston Briggs described using temporary registers to break these cycles.

Continue reading →