Run backwards propagation before we prune the graph after ForceOSRExit nodes in BytecodeParser

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Lukas Bernhard]

Differential testing identifies the following samples to trigger a miscomputation in FTL.
Tested on 29c8d02c3b11c096cc67d89e5cfe8c16be42b3b7 (Fri Sep 24 09:39:18 2021 +0000)

Release/bin/jsc --validateOptions=true --useConcurrentJIT=false --useConcurrentGC=false --thresholdForJITSoon=10 --thresholdForJITAfterWarmUp=10 --thresholdForOptimizeAfterWarmUp=100 --thresholdForOptimizeAfterLongWarmUp=100 --thresholdForOptimizeSoon=100 --thresholdForFTLOptimizeAfterWarmUp=1000 --thresholdForFTLOptimizeSoon=1000 --validateBCE=true --useFTLJIT=true diff.js

function main() {
    let v38;
    let v40;

    async function v24() {
        const v33 = false;
        const v34 = -v33;
        const v37 = typeof search;
        const v39 = v38 ? v30 : 1;
        v40 = v34;
            
        for(let v41 = 0; v41 != 100000; v41++) { } 
    }   
    [1,1,1].filter(v24);
    print(Object.is(v40, 0)); // v40 should be -0, but is 0 in FTL (hence prints true in FTL, false without FTL or in v8)
}
main();

[Radar WebKit Bug Importer]

<rdar://problem/83565088>

[Saam Barati]

Lukas, your fuzzer is producing some really amazing spec implementation bugs. Please keep the bug reports coming.

[Saam Barati]

The bug here is the code inside the bytecode parser that does liveness preservation for all live values after a ForceOSRExit does not properly keep around the program in such a way that the backwards prop flags are properly maintained.

Specifically, we end up with a program like:
```
a: ArithNegate(...)
SetLocal(@a, loc6)
PhantomLocal(loc6)
```

But, this doesn't tell backwards prop that we care about negative zero.

I'm beginning to think that instead of all PhantomLocals, we should just emit Phantom(GetLocal) for all live things that aren't flushed.

[Saam Barati]

Created attachment 439698 [details]
test EWS

[Saam Barati]

FWIW, this is both a DFG/FTL bug. This test just happens to require the FTL because it'll OSR exit with a bad constant value because of this bad code inside bytecode parser.

[Saam Barati]

Created attachment 439802 [details]
test EWS

[Saam Barati]

Created attachment 439806 [details]
test EWS

[Saam Barati]

Created attachment 439815 [details]
test EWS

[Saam Barati]

Created attachment 439885 [details]
patch

[Robin Morisset]

Comment on attachment 439885 [details]
patch

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

r=me.
Overall I'm very happy to see that the ugly hack at the end of BytecodeParser which removes some of the code after OSRExits but not all is at least partly gone.

> Source/JavaScriptCore/ChangeLog:19
> +        That way, the phase sees the graph as if its an IR over the whole bytecode

nit: its => it's

> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:50
> +        for (size_t i = 0; i < m_graph.numBlocks(); ++i) {

trivial simplification: you can do
```
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
  m_flagsAtHead[block] = ...
```
blocksInNaturalOrder is exactly this pattern of iterating them in order and skipping any null one.

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:9027
> +    performBackwardsPropagation(m_graph);

Would it be possible/safe to flash a GC safe point before this? While backwards propagation is pretty quick, the bytecode parser is already responsible for many of our worst GC pauses, so I'd really like to avoid making its impact on the GC any worse.

[Saam Barati]

Comment on attachment 439885 [details]
patch

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

>> Source/JavaScriptCore/ChangeLog:19
>> +        That way, the phase sees the graph as if its an IR over the whole bytecode
> 
> nit: its => it's

will fix.

>> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:50
>> +        for (size_t i = 0; i < m_graph.numBlocks(); ++i) {
> 
> trivial simplification: you can do
> ```
> for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>   m_flagsAtHead[block] = ...
> ```
> blocksInNaturalOrder is exactly this pattern of iterating them in order and skipping any null one.

will fix.

>> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:9027
>> +    performBackwardsPropagation(m_graph);
> 
> Would it be possible/safe to flash a GC safe point before this? While backwards propagation is pretty quick, the bytecode parser is already responsible for many of our worst GC pauses, so I'd really like to avoid making its impact on the GC any worse.

I'm not 100% sure if it's safe. My guess would be yes, but it requires some analysis of what happens in bytecode parser after this code runs. If we do it, I think it should be done in its own patch.

[Saam Barati]

Created attachment 439894 [details]
patch for landing

[Saam Barati]

Created attachment 440264 [details]
patch for landing

[EWS]

Committed r283623 (242575@main): <https://commits.webkit.org/242575@main>

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

[Saam Barati]

Comment on attachment 440264 [details]
patch for landing

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

> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:225
> +            variableAccessData->mergeFlags(flagsRef & ~NodeBytecodeUsesAsInt); // We don't care about cross-block uses-as-int for this.

I think this logic is actually slightly off, since we incorporate the value from m_currentFlags in SetLocal.

I was trying to avoid having a separate bit to represent "is alive". But, I should just add that bit.

[Saam Barati]

Created attachment 440527 [details]
followup patch

[Saam Barati]

Doing a follow up

[Yusuke Suzuki]

Comment on attachment 440527 [details]
followup patch

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

r=me

> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:218
> +    static constexpr NodeFlags VariableIsUsed = 1 << (1 + WTF::getMSBSetConstexpr(NodeBytecodeBackPropMask));

Can we have a static_assert that `1 << (1 + WTF::getMSBSetConstexpr(NodeBytecodeBackPropMask))` does not exceed NodeFlags size?

[Saam Barati]

Created attachment 440695 [details]
followup patch for landing

[EWS]

Committed r283862 (242739@main): <https://commits.webkit.org/242739@main>

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