Experiment: Alternative SSA construction algorithm

[SirYwell]

Hi,

this is mainly an experiment, I wanted to play around with the API and see how an alternative SSA construction algorithm can be implemented. There are a few notable problems I encountered:

• The original algorithm is supposed to work on-the-fly in a single step. This does not work with the current API.
  • Values (operands) and References (successor arguments) are bound eagerly. I assume terminating ops could be emitted only after everything else was done, but that's not easy to achieve currently either. For operands, I don't see any way to say "oh, please use a different value" after the operation is passed to the builder. I'm not sure how relevant this is for other transformations, but if we find a simple solution to this without giving up immutability, I could imagine it to be very powerful.
  • I'm currently using more data structures to cope with the two-step variant than the original algorithm itself requires.
    • The predecessors map could be avoided at the cost of additional computation whenever only filled blocks should be considered
    • The loads map is required as we can't replace the loads directly during the analysis step
    • The additionalParameters could probably be removed if Block.Builder allowed removing parameters
    • The deletedPhis set is also needed to cope with the fact that we look up current defs in both steps
• I noticed that for the method in TestTraverse, this implementation gets rid of one parameter that the existing implementation does not get rid of. I'm not sure if it is designed to produce minimal SSA, but that looks odd. (c is passed to the while body, but it is never read there before being written)

I think the algorithm itself is pretty straightforward, but the extra steps needed to adapt to the API somewhat nullify that. I tried to document the implementation details that differ from the paper, but if there are any questions or suggestions how this could be improved, please let me know.

---

Progress

• [x] Change must not contain extraneous whitespace

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/babylon.git pull/214/head:pull/214
$ git checkout pull/214

Update a local copy of the PR:
$ git checkout pull/214
$ git pull https://git.openjdk.org/babylon.git pull/214/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 214

View PR using the GUI difftool:
$ git pr show -t 214

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/babylon/pull/214.diff

Webrev

Link to Webrev Comment