Changeset 280849 in webkit

Timestamp:

Aug 10, 2021, 10:08:20 AM (5 years ago)

Author:

Russell Epstein

Message:

Cherry-pick r280507. rdar://problem/79730568

Improve OSR entry into Wasm loops with arguments
​https://bugs.webkit.org/show_bug.cgi?id=228595

Reviewed by Yusuke Suzuki.

JSTests:

Just a straightforward test that counts to 1M in a loop, to exercise both OSR entry and a loop with an argument at the same time.
100k iterations was not enough to reliably complete an OSR entry.

• wasm/stress/osr-entry-with-loop-arguments.js: Added. (async test):

Source/JavaScriptCore:

This patch has two parts:

• improve the Wasm OSR code to fully support loop arguments (just some plumbing to make sure that the right values are propagated)
• improve the B3 validator to fix a hole I noticed while writing the first part: we were not detecting code that introduce Upsilons in the wrong blocks. Naturally, this caused hard to debug issues, as B3 has no well-defined semantics for a Phi that is reached before the corresponding Upsilon(s).

• b3/B3Validate.cpp:
• wasm/WasmAirIRGenerator.cpp: (JSC::Wasm::AirIRGenerator::emitLoopTierUpCheck): (JSC::Wasm::AirIRGenerator::addLoop):
• wasm/WasmB3IRGenerator.cpp: (JSC::Wasm::B3IRGenerator::emitLoopTierUpCheck): (JSC::Wasm::B3IRGenerator::addLoop):
• wasm/WasmLLIntGenerator.cpp: (JSC::Wasm::LLIntGenerator::addLoop):

git-svn-id: ​https://svn.webkit.org/repository/webkit/trunk@280507 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Location:

branches/safari-611.3.10.0-branch

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/wasm/stress/osr-entry-with-loop-arguments.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/b3/B3Validate.cpp (modified) (2 diffs)
• Source/JavaScriptCore/wasm/WasmAirIRGenerator.cpp (modified) (4 diffs)
• Source/JavaScriptCore/wasm/WasmB3IRGenerator.cpp (modified) (6 diffs)
• Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp (modified) (1 diff)

branches/safari-611.3.10.0-branch/JSTests/ChangeLog

@@ +1 @@
+2021-08-10  Russell Epstein  <repstein@apple.com>
+
+        Cherry-pick r280507. rdar://problem/79730568
+
+    Improve OSR entry into Wasm loops with arguments
+    https://bugs.webkit.org/show_bug.cgi?id=228595
+    
+    Reviewed by Yusuke Suzuki.
+    
+    JSTests:
+    
+    Just a straightforward test that counts to 1M in a loop, to exercise both OSR entry and a loop with an argument at the same time.
+    100k iterations was not enough to reliably complete an OSR entry.
+    
+    * wasm/stress/osr-entry-with-loop-arguments.js: Added.
+    (async test):
+    
+    Source/JavaScriptCore:
+    
+    This patch has two parts:
+    - improve the Wasm OSR code to fully support loop arguments (just some plumbing to make sure that the right values are propagated)
+    - improve the B3 validator to fix a hole I noticed while writing the first part: we were not detecting code that introduce Upsilons in the wrong blocks.
+      Naturally, this caused hard to debug issues, as B3 has no well-defined semantics for a Phi that is reached before the corresponding Upsilon(s).
+    
+    * b3/B3Validate.cpp:
+    * wasm/WasmAirIRGenerator.cpp:
+    (JSC::Wasm::AirIRGenerator::emitLoopTierUpCheck):
+    (JSC::Wasm::AirIRGenerator::addLoop):
+    * wasm/WasmB3IRGenerator.cpp:
+    (JSC::Wasm::B3IRGenerator::emitLoopTierUpCheck):
+    (JSC::Wasm::B3IRGenerator::addLoop):
+    * wasm/WasmLLIntGenerator.cpp:
+    (JSC::Wasm::LLIntGenerator::addLoop):
+    
+    
+    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@280507 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+    2021-07-30  Robin Morisset  <rmorisset@apple.com>
+
+            Improve OSR entry into Wasm loops with arguments
+            https://bugs.webkit.org/show_bug.cgi?id=228595
+
+            Reviewed by Yusuke Suzuki.
+
+            Just a straightforward test that counts to 1M in a loop, to exercise both OSR entry and a loop with an argument at the same time.
+            100k iterations was not enough to reliably complete an OSR entry.
+
+            * wasm/stress/osr-entry-with-loop-arguments.js: Added.
+            (async test):
+
 2021-08-10  Russell Epstein  <repstein@apple.com>
 

branches/safari-611.3.10.0-branch/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2021-08-10  Russell Epstein  <repstein@apple.com>
+
+        Cherry-pick r280507. rdar://problem/79730568
+
+    Improve OSR entry into Wasm loops with arguments
+    https://bugs.webkit.org/show_bug.cgi?id=228595
+    
+    Reviewed by Yusuke Suzuki.
+    
+    JSTests:
+    
+    Just a straightforward test that counts to 1M in a loop, to exercise both OSR entry and a loop with an argument at the same time.
+    100k iterations was not enough to reliably complete an OSR entry.
+    
+    * wasm/stress/osr-entry-with-loop-arguments.js: Added.
+    (async test):
+    
+    Source/JavaScriptCore:
+    
+    This patch has two parts:
+    - improve the Wasm OSR code to fully support loop arguments (just some plumbing to make sure that the right values are propagated)
+    - improve the B3 validator to fix a hole I noticed while writing the first part: we were not detecting code that introduce Upsilons in the wrong blocks.
+      Naturally, this caused hard to debug issues, as B3 has no well-defined semantics for a Phi that is reached before the corresponding Upsilon(s).
+    
+    * b3/B3Validate.cpp:
+    * wasm/WasmAirIRGenerator.cpp:
+    (JSC::Wasm::AirIRGenerator::emitLoopTierUpCheck):
+    (JSC::Wasm::AirIRGenerator::addLoop):
+    * wasm/WasmB3IRGenerator.cpp:
+    (JSC::Wasm::B3IRGenerator::emitLoopTierUpCheck):
+    (JSC::Wasm::B3IRGenerator::addLoop):
+    * wasm/WasmLLIntGenerator.cpp:
+    (JSC::Wasm::LLIntGenerator::addLoop):
+    
+    
+    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@280507 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+    2021-07-30  Robin Morisset  <rmorisset@apple.com>
+
+            Improve OSR entry into Wasm loops with arguments
+            https://bugs.webkit.org/show_bug.cgi?id=228595
+
+            Reviewed by Yusuke Suzuki.
+
+            This patch has two parts:
+            - improve the Wasm OSR code to fully support loop arguments (just some plumbing to make sure that the right values are propagated)
+            - improve the B3 validator to fix a hole I noticed while writing the first part: we were not detecting code that introduce Upsilons in the wrong blocks.
+              Naturally, this caused hard to debug issues, as B3 has no well-defined semantics for a Phi that is reached before the corresponding Upsilon(s).
+
+            * b3/B3Validate.cpp:
+            * wasm/WasmAirIRGenerator.cpp:
+            (JSC::Wasm::AirIRGenerator::emitLoopTierUpCheck):
+            (JSC::Wasm::AirIRGenerator::addLoop):
+            * wasm/WasmB3IRGenerator.cpp:
+            (JSC::Wasm::B3IRGenerator::emitLoopTierUpCheck):
+            (JSC::Wasm::B3IRGenerator::addLoop):
+            * wasm/WasmLLIntGenerator.cpp:
+            (JSC::Wasm::LLIntGenerator::addLoop):
+
 2021-08-10  Russell Epstein  <repstein@apple.com>
 

branches/safari-611.3.10.0-branch/Source/JavaScriptCore/b3/B3Validate.cpp

@@ -573 +573 @@
             VALIDATE(block->numPredecessors() == predecessors.size(), ("At ", *block));
         }
+
+        validatePhisAreDominatedByUpsilons();
     }
 
@@ -653 +655 @@
         VALIDATE(memory->offset() >= 0, ("At ", *value));
     }
-    
+
+    // A simple backwards analysis to check that we cannot reach a Phi without going through a corresponding Upsilon
+    // We cannot use the dominator tree, since we are checking that each Phi is dominated by a the set of all of its upsilons, and not by a single node.
+    void validatePhisAreDominatedByUpsilons()
+    {
+        bool changed = true;
+        BitVector blocksToVisit;
+        IndexMap<BasicBlock*, HashSet<Value*>> undominatedPhisAtTail(m_procedure.size());
+        for (BasicBlock* block : m_procedure)
+            blocksToVisit.set(block->index());
+        while (changed) {
+            changed = false;
+            for (BasicBlock* block : m_procedure.blocksInPostOrder()) {
+                if (!blocksToVisit.quickClear(block->index()))
+                    continue;
+                HashSet<Value*> undominatedPhis = undominatedPhisAtTail[block];
+                for (unsigned index = block->size()-1; index--;) {
+                    Value* value = block->at(index);
+                    switch (value->opcode()) {
+                    case Upsilon:
+                        undominatedPhis.remove(value->as<UpsilonValue>()->phi());
+                        break;
+                    case Phi:
+                        VALIDATE(!undominatedPhis.contains(value), ("At ", *value));
+                        undominatedPhis.add(value);
+                        break;
+                    default:
+                        break;
+                    }
+                }
+                for (BasicBlock* predecessor : block->predecessors()) {
+                    bool changedSet = false;
+                    for (Value* phi : undominatedPhis)
+                        changedSet |= undominatedPhisAtTail[predecessor].add(phi).isNewEntry;
+                    if (changedSet) {
+                        blocksToVisit.quickSet(predecessor->index());
+                        changed = true;
+                    }
+                }
+                if (!block->index())
+                    VALIDATE(undominatedPhis.isEmpty(), ("Undominated phi at top of entry block: ", **undominatedPhis.begin()));
+            }
+        }
+    }
+
     NO_RETURN_DUE_TO_CRASH void fail(
         const char* filename, int lineNumber, const char* function, const char* condition,

branches/safari-611.3.10.0-branch/Source/JavaScriptCore/wasm/WasmAirIRGenerator.cpp

@@ -657 +657 @@
 
     void emitEntryTierUpCheck();
-    void emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack);
+    void emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack, const Stack& newStack);
 
     void emitWriteBarrierForJSWrapper();
@@ -2641 +2641 @@
 }
 
-void AirIRGenerator::emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack)
+void AirIRGenerator::emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack, const Stack& newStack)
 {
     uint32_t outerLoopIndex = this->outerLoopIndex();
@@ -2680 +2680 @@
     }
     for (TypedExpression value : enclosingStack)
+        patchArgs.append(ConstrainedTmp(value.value(), B3::ValueRep::ColdAny));
+    for (TypedExpression value : newStack)
         patchArgs.append(ConstrainedTmp(value.value(), B3::ValueRep::ColdAny));
 
@@ -2732 +2734 @@
 
     m_currentBlock = body;
-    emitLoopTierUpCheck(loopIndex, enclosingStack);
+    emitLoopTierUpCheck(loopIndex, enclosingStack, newStack);
 
     return { };

branches/safari-611.3.10.0-branch/Source/JavaScriptCore/wasm/WasmB3IRGenerator.cpp

@@ -296 +296 @@
 
     void emitEntryTierUpCheck();
-    void emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack);
+    void emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack, const Stack& newStack);
 
     void emitWriteBarrierForJSWrapper();
@@ -1809 +1809 @@
 }
 
-void B3IRGenerator::emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack)
+void B3IRGenerator::emitLoopTierUpCheck(uint32_t loopIndex, const Stack& enclosingStack, const Stack& newStack)
 {
     uint32_t outerLoopIndex = this->outerLoopIndex();
@@ -1835 +1835 @@
     }
     for (TypedExpression value : enclosingStack)
+        stackmap.append(value);
+    for (TypedExpression value : newStack)
         stackmap.append(value);
 
@@ -1886 +1888 @@
 
     block = ControlData(m_proc, origin(), signature, BlockType::Loop, continuation, body);
-
-    ExpressionList args;
-    {
-        unsigned offset = enclosingStack.size() - signature->argumentCount();
-        for (unsigned i = 0; i < signature->argumentCount(); ++i) {
-            TypedExpression value = enclosingStack.at(offset + i);
-            auto* upsilon = m_currentBlock->appendNew<UpsilonValue>(m_proc, origin(), value);
-            Value* phi = block.phis[i];
-            body->append(phi);
-            upsilon->setPhi(phi);
-            newStack.constructAndAppend(value.type(), phi);
-        }
-        enclosingStack.shrink(offset);
+    unsigned offset = enclosingStack.size() - signature->argumentCount();
+    for (unsigned i = 0; i < signature->argumentCount(); ++i) {
+        TypedExpression value = enclosingStack.at(offset + i);
+        auto* upsilon = m_currentBlock->appendNew<UpsilonValue>(m_proc, origin(), value);
+        Value* phi = block.phis[i];
+        body->append(phi);
+        upsilon->setPhi(phi);
+        newStack.constructAndAppend(value.type(), phi);
     }
 
@@ -1959 +1956 @@
             connectControlEntry(data, expressionStack);
         }
+        for (unsigned i = 0; i < signature->argumentCount(); ++i) {
+            TypedExpression value = enclosingStack.at(offset + i);
+            Value* phi = block.phis[i];
+            m_currentBlock->appendNew<UpsilonValue>(m_proc, value->origin(), loadFromScratchBuffer(value->type()), phi);
+        }
+        enclosingStack.shrink(offset);
         connectControlEntry(block, enclosingStack);
 
@@ -1964 +1967 @@
         m_currentBlock->appendNewControlValue(m_proc, Jump, origin(), body);
         body->addPredecessor(m_currentBlock);
-    }
+    } else
+        enclosingStack.shrink(offset);
 
     m_currentBlock = body;
-    emitLoopTierUpCheck(loopIndex, enclosingStack);
+    emitLoopTierUpCheck(loopIndex, enclosingStack, newStack);
     return { };
 }

branches/safari-611.3.10.0-branch/Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp

@@ -886 +886 @@
     for (TypedExpression expression : enclosingStack)
         osrEntryData.append(expression);
+    for (TypedExpression expression : newStack)
+        osrEntryData.append(expression);
 
     WasmLoopHint::emit(this);