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

[Paul Sandoz]

On Thu, 24 Oct 2024 15:40:49 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.
>
> Hannes Greule has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains three additional commits since the last revision:
> 
>  - Merge branch 'code-reflection' into feature/simple-ssa
>  - test both SSA implementations
>  - alternative SSA construction algorithm

This looks good. I verified it fixes uninitialized pattern variables mentioned in #264.

Here's a patch that i believe fixes the algorithm to support uninitialized variables.


diff --git a/src/java.base/share/classes/java/lang/reflect/code/analysis/SSAConstruction.java b/src/java.base/share/classes/java/lang/reflect/code/analysis/SSAConstruction.java
index e5133490128..25de41e9691 100644
--- a/src/java.base/share/classes/java/lang/reflect/code/analysis/SSAConstruction.java
+++ b/src/java.base/share/classes/java/lang/reflect/code/analysis/SSAConstruction.java
@@ -70,8 +70,12 @@ private void prepare(Op nestedOp) {
                 }
                 case CoreOp.VarAccessOp.VarStoreOp store ->
                         writeVariable(store.varOp(), store.parentBlock(), new Holder(store.storeOperand()));
-                case CoreOp.VarOp initialStore ->
-                        writeVariable(initialStore, initialStore.parentBlock(), new Holder(initialStore.initOperand()));
+                case CoreOp.VarOp initialStore -> {
+                    Val val = initialStore.isUninitialized()
+                            ? Uninitialized.VALUE
+                            : new Holder(initialStore.initOperand());
+                    writeVariable(initialStore, initialStore.parentBlock(), val);
+                }
                 case Op.Terminating _ -> {
                     Block block = op.parentBlock();
                     // handle the sealing, i.e. only now make this block a predecessor of its successors
@@ -183,6 +187,7 @@ private void sealBlock(Block block) {
 
     private Value resolveValue(CopyContext context, Val val) {
         return switch (val) {
+            case Uninitialized _ -> throw new IllegalStateException("Uninitialized variable");
             case Holder holder -> context.getValueOrDefault(holder.value(), holder.value());
             case Phi phi -> {
                 List<Phi> phis = this.additionalParameters.get(phi.block());
@@ -253,6 +258,10 @@ sealed interface Val {
     record Holder(Value value) implements Val {
     }
 
+    enum Uninitialized implements Val {
+        VALUE;
+    }
+
     record Phi(CoreOp.VarOp variable, Block block, List<Val> operands, Set<Object> users) implements Val {
         Phi(CoreOp.VarOp variable, Block block) {
             this(variable, block, new ArrayList<>(), new HashSet<>());
``` 

Using `IllegalStateException` might be too broad in general. `TestUninitializedVariable` checks it encounters it, but it might be thrown by something else. The test passed without these changes because the SSA algorithm fails for different reasons, on the call to `initialStore.initOperand()`.

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

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