Implement SSA Destruction

[RealA10N]

We have implemented basic SSA construction in #4 and #23. However, do not have a way to destruct the SSA form back to a representation with less unique registers.

[RealA10N]

In the SSA book, basic SSA destruction is explained in Chapter 3.2, and more advanced (?) destruction in Chapter 21.

[RealA10N]

Chapter 3.2 essentially suggests two algorithms, one is efficient and works if the SSA form is conventional (CSSA), and the other one is general but is the straightforward solution that just removes PHI instructions by appending copy instructions to the end of all corresponding basic blocks.

In the current implementation, we can't rely on the SSA form to be conventional (CSSA), because some optimizations in the SSA form might make it unconventional.

I'm currently thinking of implementing a basic non-conventional SSA destruction (splitting of every critical edge), and then implementing heuristics as described in Chapter 21 to remove the number of copies.

[RealA10N]

From Chapter 21:

The cleanest and simplest way to perform SSA destruction with good code quality
is to first insert copy instructions to make the SSA form conventional, then
take advantage of the SSA form to run efficiently aggressive coalescing (without
breaking the conventional property), before eventually renaming φ-webs and
getting rid of φ-functions.

[RealA10N]

USM enforces strictness (each path from entry -> use(v) must pass through at least one definition of v). Chapter 21.3 describes an efficient method for SSA destruction that required strictness. It sounds good!

According to Chapter 21.4, the paper the whole chapter is based on is Revisiting Out-of-SSA Translation for Correctness, Code
Quality, and Efficiency.

[RealA10N]

Looks like we must first implement a liveness pass. Chapter 9 describes liveness for SSA, but it requires a reducible CFG ("nice" contorl flow, no gotos) which USM does not guarantee.

Then, after computing a datastructe that we can query for liveness (is variable X live on instruction Y?), we should implement the interference check as described in Chapter 21.

Using this, we can implement "De-coalescing in linear time", which de-coalesces already merged phi blocks. Coalescing of the PHI blocks is done by coalescing all PHI-webs, a trivial algorithm that uses the union-find data structure (Algorithm 21.2 in the book).