[code-reflection] RFR: Experiment: Alternative SSA construction algorithm

[Paul Sandoz]

On Wed, 14 Aug 2024 07:58:53 GMT, Hannes Greule <hgreule at openjdk.org> wrote:

> 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.
>   - `Value`s (operands) and `Reference`s (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.

I have a better grasp now (not complete). This algorithm really leans on the mutability of a phi node's operand list and user list, and replacement of uses of a phi with another value. I don't see how we can make it work in one pass with the current code model design. However, its still rather good in two passes, better than the Cytron implementation IMO.

My suggestion would be to lean into the two passes and make the second pass simpler for the resolution of values, for load operation results and additional successor arguments. Its either replacement with another `Value` or a say `BlockParameterHolder` that holds the actual `Block.Parameter` to use. When a `Block` is processed to append the additional block parameters given the list of the holders it will update the holders.

In our current approach it is possible to SSA transform models with nested operations, but the constraint is variables declared outside a body can only be loaded from within a body. This obviously works well for lambdas. But it means we cannot support say the SSA transformation of the high-level model while retaining the structure e.g. the model for this code snippet:

int x =0;
if (...) {
  x = 42;
} else {
  x = -42;
}

We would have to transform the operation modeling the if statement into one that yields the resulting value of x. I explored that and it quickly became complex. So instead we throw an exception.

There is also another case, not currently supported, where we cannot fully SSA transform - if a variable is updated in a try block and accessed in a catch or finally block, or updated in a catch block and accessed in a finally block. We should either fail on such cases or leave the variable intact (perhaps via some configuration parameter). This requires analysis of stores within exception regions. We might be able to transform and split the code, but that is harder and may not be worth the effort given the likely edge case nature.

-------------

PR Comment: https://git.openjdk.org/babylon/pull/214#issuecomment-2294437961