AST inlining breaks capture semantics

[smarr]

@eregon found a bug in the AST inlining in SOMns. The following test does not result in the correct output:

class Test usingPlatform: platform = Value (
| private Array = platform kernel Array. |
)(
  public main: args = (
    | arr b |
    arr := Array new: 10.
    args from: 2 to: args size do: [ :arg | arg print. ' ' print ].

    'Correct Semantics' println.
    b := [ :i  |
        arr at: i put: [ i ]].
    1 to: 10 do: b.

    1 to: 10 do: [ :i  |
        (arr at: i) value println ].

    'Broken Semantics' println.
    1 to: 10 do: [ :i  |
        arr at: i put: [ i ]].

    1 to: 10 do: [ :i  |
        (arr at: i) value println ].
    ^ 0
  ) 
)

This issue is very likely to be a problem for TruffleSOM, too.

[charig]

I commited a patch for TruffleSOM here.
I had never worked with the inliner before so it tooked me a lot of time to properly understand the bug. There are lot of things to improve in the patch (naming, performance, and even perhaps still correctness in some cases), but I first would like to check if it the solution is going in the proper direction. In case it is not, I hope the patch serves, at least, as a spin-off for another solution. I will be available in skype to discuss the patch whenever you put your hands in this issue.

[smarr]

Could you describe what the patch is doing? (would be great if the commit message for a complicated problem could outline the solution)

I think, there only needs to be a fix for inlined blocks that have embedded blocks (transitively). And probably only in loops.
If I recall correctly, I already count whether methods have embedded blocks, so it should be possible to check.

If I read the patch correctly, you added a node that instantiates a frame object.
For me that would mean, if an embedded block is detected, inlining for its outer scope should either be ignored or done differently so that its nodes are not rewritten to slots in the outer scope of the embedded block.

This is indeed fairly intricate.

One other approach to the problem would be to see whether there is any code that is actually broken by that. I guess, by introducing the checks for the condition (nested block with access to outer scope variable that got inlined in a loop, and that escape themselves). The condition is likely rare enough.

[charig]

Following your paragraphs...

1. Yes, I should have outlined the solution, my fault sorry.
2. From what I understood, the problem is for inlined blocks that have embedded blocks using the arguments of the inlined block. And to be more precise, the problem is only when this embedded block "escapes" and is executed later. I have not worked so much with the parser and compiler yet so I did not find quickly the information for just applying my changes only to that scenario.
3. The patch does exactly what you say but only for NonLocalArgumentReadNodes in the embedded block. Previously the inliner was also replacing them, but for NonLocalReadNodes to gather the argument that becomes a local of the outer frame after inlining. This is actually the problem because that frame is the same between iterations after inlining and so if the embedded block "escapes" it is binded to the last value of the iteration. Now instead of a NonLocalReadNode I added an special node that reads the value from the new frame that is capturing the inlined block args. For all the other variables that access the outer scope the code is the same and I think that is the proper semantics.
4. For the intricate part, yes, I agree, and it could be refined to make it more clear. I mentioned that there were naming and performance issues. But it took me quite a lot of time to arrive to a solution and I wanted to know if it was in the direction of what is expected.
5. Do not completely got the condition. I only checked with the the standard test suite.

[smarr]

Hmm, the bug is also a problem for local variables:

1 to: 10 do: [ :i  |
  | local |
  local isNil ifTrue: [ local := 0 ] ifFalse: [ local := local + 1 ].
  local println ].

And that's an issue even without any blocks involved, because the previous value of the previous iteration should not be visible. local should be a fresh variable for each block activation, I think.

The last bit I mentioned before was about checking whether the bug is triggered in the existing code. In the sense of adding assertions in the interpreter, that trigger when the bug would occur.

[smarr]

There is another aspect that is broken here. The expression above evaluates incorrectly, because local can be evaluated under the right conditions to null because the slot is not marked as uninitialized anymore, because we saw a value before at some point.

[charig]

I see. Well in this case I would say that the solution proposed in my patch can be extended to include local vars also, but apparently, for complying with the proper semantics, the creation of a new frame is mandatory. An alternative (optimization) would be to only capture the variables really used inside the embedded blocks. I would have to check if nested blocks are accesible to check for that information. Then, All NonLocalVariableReads inside the methods of the embedded blocks must be replace to nodes similar to the one I proposed in the patch, that first checks for the variable in the new created frame, and if not there, continue with the standard binding.

But, considering that the inlining is mainly for optimizing performance, and that probably one of the main factors of overhead is the frame creation, perhaps a plausible alternative is to find all the scenarios where the inlining fails and do not inline. However I guess that a precise selection of this scenarios is not easy either.

[smarr]

A new frame might not be necessary. But, the slot needs to be reset to an uninitialized value before the next iteration. That's likely problematic for primitive slots.

When we bite the bullet to create a frame, it likely simpler and potentially faster to not separate subsets of slots. At least in the interpreter, one would still need to go one more context level out to reach the slots that got inlined in the outer context.

[smarr]

I might have a look at this end of next week. Until then, I won't be able to touch code related to this issue.

[charig]

It may not be mandatory in the second example you introduced, but in the original one where the embedded block escapes I think it is not enough to reset slots.

[smarr]

Resetting of slots is only for local variables that are not captured. It is somewhat a separate issue. Resetting doesn't solve the issues when vars are captured.