Can’t translating out of SSA be more trivial?

I’m reading about how to translate out of SSA form from different sources and I’m having hard time about the necessity of different techniques.

First of all looking at Cytron’s SSA paper at section 7 TRANSLATING FROM SSA FORM sub section 7.2 Allocation by Coloring:

At first, it might seem possible simply to map all occurrences of Vi
back to V and to delete all of the ~-functions. However, the new
variables introduced by translation to SSA form cannot always be
eliminated, because optimization may have capitalized on the storage
independence of the new variables. The useful persistence of the new
variables introduced by translation to SSA form can be illustrated by
the code motion example in Figure 18. The source code (Figure 18a)
assigns to V twice and uses it twice. The SSA form (Figure 18b) can be
optimized by moving the invariant assignment out of the loop, yielding
a program with separate variables for separate purposes (Figure 18c).
The dead assignment to V3 will be eliminated. These optimization leave
a region in the program where V1 and V2 are simultaneously live. Thus,
both variables are required: The original variable V cannot substitute
for both renamed variables.

Now after going through code motion pass where V2 is placed outside of the loop one can agree that substituting V1 and V2 with just V won’t keep the semantic of the original code because the assignment to W2 is dependent on the value of V2 and if we just replace both V1 and V2 with V the program will lose it’s original semantics and use the V1 value read from stdin instead of V2, so it’s true that some sort of copies needed for each phi resource used (putting aside the efficiency of minimal number of copies needed).

What I want to challenge is if we compromise on some optimization passes can’t we really just substitute the phi resources with single variable in that case just V? Say in the context of decompiler and not a compiler where you want to show the code as is and not necessarily go through all optimization passes like a compiler, one might argue that if you don’t do any code motion you won’t need copies per phi resource and you could just get away with simple substitution of all phi resources and just removing the phi node.

Now jumping to another paper by Sreedhar on translating out of SSA, he argues that even with Cytron’s approach there’re several problems when SSA is gone through several optimization passes and he calls it TSSA:

Given a CSSA form, optimizations such as copy folding and code motion,
may transform the SSA form to a state in which there are phi resource
interferences. Let us call such an SSA form TSSA (for transformed SSA)
form.

He goes on and present several problems with TSSA that even with Cytron’s naive approach could lead to losing the original semantics of the program and suggests using liveness analysis, interference graph and data flow analysis.

First he presents the Lost copy problem:

Figure 7 illustrates the lost copy problem. Figure 7(a) shows the
original code. Figure 7(b) shows the TSSA form (with copies folded).
If we use the algorithm in 4 to eliminate the phi instruction, the
copy y=x would be lost in the translation.

We can see the TSSA form caused by copy propagation pass that causes x2 to be copied to the assignment in L3 causing an interference between the live ranges of x2 and x3 that if we simply substitute them with a shared resource like x, the program will lose its original semantics because the assignment in L3 will be used with the value of x3 and not the x2 value hence we use the provided algorithm to work out such case.

Then again I want to challenge this solution by saying that what caused this interference was the copy propagation pass and if we made it “SSA Aware” such that if a symbol is being assigned to a phi definition we simply won’t copy propagate it, basically leaving the y = x2 as is. If you think about that the output of the solution in that case produced similar code that essentially replaced the phi symbol x2 -> x2' and then made an assignment statement x2' = x2 and used it for the assignment in L3 which is basically the same as if we just left y = x2 just with different name, but all we did to achieve the same solution was make our copy propagation SSA aware like I said and we didn’t have to go through live analysis at all.

Moving up to the Swap problem:

Let us apply the algorithm to the swap problem in 2 shown in Figure
8. The original code for the swap problem is given in Figure 8(a), and the corresponding CSSA form is given in Figure 8(b). After we perform
copy folding on the CSSA form, we get the TSSA form shown in Figure
8(c).

In this TSSA on the entry of the loop it’s clear to see that on the second phi assignment y1 and x2 interfere with one another and on all other iterations of the loop x2 is being assigned to y2 and y2 being assigned right after to x2 losing its original semantics of the swap. Then again with liveness analysis and the provided algorithm we get to the provided TSSA to CSSA solution:

Which looks familiar as it really does the original swap, but then again what if we made the copy propagation pass SSA aware and just not propagate phi defined values like z = x2 to y3 = z or the x3 = y2 into the first phi assignment in the loop.

I would even go further and extend this phi awareness not to only just the defined phi value in copy propagation but to also the phi resources used in the phi assignment.

For example at the beginning of the paper a simple If-Else control flow construct is used and then one of the values is copy propagated to the phi assignment causing an interference between the phi resources used:

Simply making the copy propagation not propagate a value if the assigned symbol is used in a phi instruction such as in this example x2 = y.

All I see these solutions are doing is just reverse what a not SSA aware optimization pass did and in more expensive manner by calculating liveness and interference graphs.
The idea of transforming IR to SSA was to make our lives easy to do data floe analysis and optimization passes at the first place, so not making them aware of phi instructions seems a bit odd I would say. I know maybe an argument against what I’m saying is that not doing these copy propagation by making them aware to SSA phi instruction would miss some optimization opportunities, but I’m not sure that’s true, or if it can be proven mathematically, in general I can’t be sure if there exists such transformation that would transform CSSA to TSSA that causes interference that can’t be solved by just making these optimization passes aware. The authors just gave these 2 arbitrary “problems” caused by specific optimization pass implemented in an arbitrary way that could be changed to overcome these problems in my eyes. I’m not sure if we can find all solutions to the questions of what transformations can be applied to the program that would cause it to be in TSSA state with interference or is it some sort of an NP-hard problem that we can’t just give all solutions but to verify provided ones and so the best course of actions would just to implement this out of SSA with liveness analysis in any case just to be cautions of the unknown?

I would note that only in the proposed naive solution of Cytron that we should even do the copy assignment as a step of existing SSA in case of a pass like code motion then it might be necessary, but like I’ve stated in the context of decompilers where it’s not necessary and might be considered even harmful to do such optimization (in my eyes) then it still might be redundant and we could get away with just deleting the phi assignment and making sure that the phi resources used in the assignment weren’t copy propagated from their respective definitions (as copy propagation is the only optimization pass that comes to mind that can cause them to disappear besides dead code elimination but in the latter case it makes sense to remove it aswell).

Filed under: Kiến thức lập trình - @ 19:20

Thẻ: compilationcompiler-constructioncompiler-optimizationdecompilerssa

Thiết kế website giá rẻ

Danh mục

Can’t translating out of SSA be more trivial?