[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 think this is a general problem that comes with the (very powerful) flexibility of the model. It's generally difficult to set boundaries what a valid input code model is for a specific transformation operation, and then there might still be two options: 1) In such case, do not touch that variable and only transform the rest, or 2) throw an exception if an unsupported code element is encountered. Both might make sense in specific scenarios, or both variants could be combined depending _what kind of_ unsupported elements are encountered.

Yes, since it is specific to the operations present in the model. I used the current SSA implementation carefully in the Triton example, when translating the operation modeling the Java `for` statement, modeling a counted loop, into a Triton SSA counted loop expression.


> 
> Without trying hard, I also noticed that the current transform API isn't well-suited when trying to clean up e.g. empty blocks or to combine blocks. Especially with the SSA transform, we end up with unneeded blocks in many places, so I thought that could be a potential improvement, but I didn't find a way to do that without a lot of additional work.

Indeed, it's often easier not to do that, and apply as a separate transformation if needed. When a body is built, any empty blocks with no predecessors are removed, and then the blocks are topologically sorted. This will retain non-empty block with no predecessors, occurring at the end, and i am unsure whether it is appropriate to remove them or not -- is it intentional or an error? It was intentional, for simplicity, to retain blocks that unconditionally branch to other blocks that could otherwise be merged, lowering will likely do this.

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

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