Bug 215672 – OSR availability validation should run for any node with exitOK

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Keith Miller]

OSR availability validation should run for any node with exitOK

[Keith Miller]

Created attachment 406893 [details]
Patch

[Keith Miller]

Created attachment 406894 [details]
Patch

[Saam Barati]

Comment on attachment 406894 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=406894&action=review

> Source/JavaScriptCore/ChangeLog:17
> +        First, OpGetScope, should not mark it's first argument as used

it's => its

> Source/JavaScriptCore/ChangeLog:20
> +        since it's not. This is problematic because we could have a loop
> +        where OpGetScope is the first bytecode, namely when doing tail
> +        recursive inlining.

this doesn't say why this is bad. Talk about the issue w.r.t variables, CPS, and SSA conversion

> Source/JavaScriptCore/ChangeLog:32
> +        Fourth, MovHint removal phase had a second bug where a MovHint
> +        that was not killed in the current block would be zombied, which

always? This didn't lead to bugs?

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:129
> +            // We may have made the graph invalid with the above transformation. It's possible that we have a node marked exitOK on while there's an operand we have ZombieHinted live in bytecode. If we transform our graph to insert something at that point we will no longer have all the information we need to OSR. For example, consider the following block:

weird wording: "on while there's an operand"

Also, please split this across more than 1 line

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:144
> +            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {

this whole loop looks arbitrary. How is that exitValid is never flipped back to true over the entire block? What if we cross a point where we can exit again?

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:158
> +                        for (size_t i = 0; i < currentZombies.size(); ++i)
> +                            exitValid &= !currentZombies[i];

this loop looks super expensive and easily avoidable by keeping a count or something

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:170
> +                    currentZombies.operand(node->unlinkedOperand()) = true;

shouldn't a MovHint to this local set this to false?

[Saam Barati]

Comment on attachment 406894 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=406894&action=review

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:167
> +                node->origin.exitOK &= exitValid;

isn't this gonna just lead to us marking a bunch fo stuff that needs to exit as exitInvalid? I'm kinda not believing in what's preventing that from happening

[Saam Barati]

Comment on attachment 406894 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=406894&action=review

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:132
> +            // @3 KillStack(loc1, bc#2, ExitValid)

what if this weren't a KillStack, but something that exited? How would this transformation be sound?

> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:141
> +            // But it would be perfectly valid to later insert some exiting node between @2 and @3. We no longer have availability for loc1 at that point, however, thus we need to mark @3 as ExitInvalid so we don't do that.

Can you also write the graph you expect to have?

[Saam Barati]

Comment on attachment 406894 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=406894&action=review

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:132
>> +            // @3 KillStack(loc1, bc#2, ExitValid)
> 
> what if this weren't a KillStack, but something that exited? How would this transformation be sound?

oh, I guess that means we wouldn't have made this is a ZombieHint...

[Keith Miller]

Comment on attachment 406894 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=406894&action=review

I commented on Saam's comments on MovHintRemoval even though we opted to remove that phase in a different patch.

>> Source/JavaScriptCore/ChangeLog:32
>> +        that was not killed in the current block would be zombied, which
> 
> always? This didn't lead to bugs?

No, only if there was no exit after the MovHint in the block.

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:141
>> +            // But it would be perfectly valid to later insert some exiting node between @2 and @3. We no longer have availability for loc1 at that point, however, thus we need to mark @3 as ExitInvalid so we don't do that.
> 
> Can you also write the graph you expect to have?

Sure, although, the only difference is that @3 is just ExitInvalid.

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:144
>> +            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
> 
> this whole loop looks arbitrary. How is that exitValid is never flipped back to true over the entire block? What if we cross a point where we can exit again?

If we passed a point where we can exit then we shouldn't have any zombies since that would be invalid. If you want I can add an assertion.

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:158
>> +                            exitValid &= !currentZombies[i];
> 
> this loop looks super expensive and easily avoidable by keeping a count or something

Sure, I thought Clang would convert it into a word loop since Operand<bool> is equivalent to FastBitVector but I guess I was misremembering.

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:167
>> +                node->origin.exitOK &= exitValid;
> 
> isn't this gonna just lead to us marking a bunch fo stuff that needs to exit as exitInvalid? I'm kinda not believing in what's preventing that from happening

No, if something needed exit then mayExit should have returned !DoesNotExit so the above assert would have failed.

>> Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp:170
>> +                    currentZombies.operand(node->unlinkedOperand()) = true;
> 
> shouldn't a MovHint to this local set this to false?

I expected it would be handled on by the forAllKilledOperands on the next iteration of the loop but it appears you are correct.

[Keith Miller]

Created attachment 407166 [details]
Patch

[Keith Miller]

Created attachment 407167 [details]
Patch

[Saam Barati]

Comment on attachment 407167 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=407167&action=review

r=me

> Source/JavaScriptCore/ChangeLog:14
> +        Relaxing our criteria revealed a number of bugs however. Which I

nit: I get what you're trying to say here, but I think we're strengthening our criteria, not relaxing it.

> Source/JavaScriptCore/ChangeLog:21
> +        Second, OpGetScope, should not mark it's first argument as used

it's => its

> Source/JavaScriptCore/ChangeLog:30
> +        since it's not. This is problematic because we could have a loop
> +        where OpGetScope is the first bytecode, namely when doing tail
> +        recursive inlining. If we were in that position, there could be a
> +        local that was used at a merge point at the loop backedge that had
> +        two MovHint defs from both predecessors. When we do CPS conversion
> +        those two defs will be seen as different variables. Then during
> +        SSA conversion we won't insert a phi connecting, making the
> +        argument to OpGetScope unrecoverable as we never PutStacked the
> +        values.

this would all be a lot easier to understand with an IR graph

[Radar WebKit Bug Importer]

<rdar://problem/67838875>

[Keith Miller]

Created attachment 407412 [details]
Patch for landing

[EWS]

Committed r266242: <https://trac.webkit.org/changeset/266242>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 407412 [details].

[Darin Adler]

Comment on attachment 407412 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=407412&action=review

> Source/JavaScriptCore/dfg/DFGSSACalculator.cpp:118
> +    out.print("], \nDefs: [");

Trailing space before newline?

[Keith Miller]

Comment on attachment 407412 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=407412&action=review

>> Source/JavaScriptCore/dfg/DFGSSACalculator.cpp:118
>> +    out.print("], \nDefs: [");
> 
> Trailing space before newline?

Fair enough, not sure how much it matters since this is debugging code anyway.