I'm learning about compiler optimizations on ssa form. One difficulty I'm having is how to retain/repair/reconstruct the ssa form after modifying the structure of the call-flow graph.
Suppose I have the following cfg (the a, b, c variables are dummies, disregard them):
Now I want to insert a node that preceedes the while-node so that the result becomes:
As seen, the new node changes the dominance frontiers for x_1 and x_2 and requires the phi-node for the while-block to be "split" into two.
What algorithms can accomplish this? I have looked in books and slides but not found anything that explains how to do this efficiently.
I'm probably late to the party, but there's a chapter "SSA Reconstruction" in Inria Forge's SSA book (mirror) that talks about this topic.