[JSC] OSRExit recovery for SpeculativeAdd does not consier "A = A + A" pattern
authorysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 6 Apr 2019 01:57:16 +0000 (01:57 +0000)
committerysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 6 Apr 2019 01:57:16 +0000 (01:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196582

Reviewed by Saam Barati.

JSTests:

* stress/add-overflow-check-with-three-same-registers.js: Added.
(foo):
(Number.prototype.valueOf):
(runWithNumber):

Source/JavaScriptCore:

In DFG, our ArithAdd with overflow is executed speculatively, and we recover the value when overflow flag is set.
The recovery is subtracting the operand from the destination to get the original two operands. Our recovery code
handles A + B = A, A + B = B cases. But it misses A + A = A case (here, A and B are GPRReg). Our recovery code
attempts to produce the original operand by performing A - A, and it always produces zero accidentally.

This patch adds the recovery code for A + A = A case. Because we know that this ArithAdd overflows, and operands were
same values, we can calculate the original operand from the destination value by `((int32_t)value >> 1) ^ 0x80000000`.

We also found that FTL recovery code is dead. We remove them in this patch.

* dfg/DFGOSRExit.cpp:
(JSC::DFG::OSRExit::executeOSRExit):
(JSC::DFG::OSRExit::compileExit):
* dfg/DFGOSRExit.h:
(JSC::DFG::SpeculationRecovery::SpeculationRecovery):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileArithAdd):
* ftl/FTLExitValue.cpp:
(JSC::FTL::ExitValue::dataFormat const):
(JSC::FTL::ExitValue::dumpInContext const):
* ftl/FTLExitValue.h:
(JSC::FTL::ExitValue::isArgument const):
(JSC::FTL::ExitValue::hasIndexInStackmapLocations const):
(JSC::FTL::ExitValue::adjustStackmapLocationsIndexByOffset):
(JSC::FTL::ExitValue::recovery): Deleted.
(JSC::FTL::ExitValue::isRecovery const): Deleted.
(JSC::FTL::ExitValue::leftRecoveryArgument const): Deleted.
(JSC::FTL::ExitValue::rightRecoveryArgument const): Deleted.
(JSC::FTL::ExitValue::recoveryFormat const): Deleted.
(JSC::FTL::ExitValue::recoveryOpcode const): Deleted.
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::preparePatchpointForExceptions):
(JSC::FTL::DFG::LowerDFGToB3::appendOSRExit):
(JSC::FTL::DFG::LowerDFGToB3::exitValueForNode):
(JSC::FTL::DFG::LowerDFGToB3::addAvailableRecovery): Deleted.
* ftl/FTLOSRExitCompiler.cpp:
(JSC::FTL::compileRecovery):

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

JSTests/ChangeLog
JSTests/stress/add-overflow-check-with-three-same-registers.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGOSRExit.cpp
Source/JavaScriptCore/dfg/DFGOSRExit.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/ftl/FTLExitValue.cpp
Source/JavaScriptCore/ftl/FTLExitValue.h
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp

index d6979fb..e4b6796 100644 (file)
@@ -1,3 +1,15 @@
+2019-04-05  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] OSRExit recovery for SpeculativeAdd does not consier "A = A + A" pattern
+        https://bugs.webkit.org/show_bug.cgi?id=196582
+
+        Reviewed by Saam Barati.
+
+        * stress/add-overflow-check-with-three-same-registers.js: Added.
+        (foo):
+        (Number.prototype.valueOf):
+        (runWithNumber):
+
 2019-04-05  Ryan Haddad  <ryanhaddad@apple.com>
 
         Unreviewed, rolling out r243665.
diff --git a/JSTests/stress/add-overflow-check-with-three-same-registers.js b/JSTests/stress/add-overflow-check-with-three-same-registers.js
new file mode 100644 (file)
index 0000000..6c145d4
--- /dev/null
@@ -0,0 +1,52 @@
+//@ runDefault("--useDoublePredictionFuzzerAgent=1", "--useFTLJIT=0", "--useConcurrentJIT=0")
+
+function foo(a, b) {
+    var result = a + b;
+    if (result)
+        return (a + b) + result + this;
+    else
+        return this.f;
+}
+
+noInline(foo);
+
+var x;
+Number.prototype.valueOf = function() { return x; };
+
+var globalCounter = 0;
+function runWithNumber(num) {
+    var test = Function(`this_, a, b, x_`, `
+        x = x_;
+        var result = foo.call(this_, a, b);
+        if (result != (a + b) * 2 + x_)
+            throw new Error("Error: bad result: " + result);
+        return ${globalCounter++};
+    `);
+    noInline(test);
+
+    for (var i = 0; i < 10000; ++i)
+        test(5, 1, 2, 100);
+
+    test(5, 2000000000, 2000000000, 1);
+    try {
+        test(5, num, num, 1000);
+    } catch (error) {
+        print(String(error));
+    }
+}
+
+runWithNumber(536870911);
+runWithNumber(536870912);
+runWithNumber(536870913);
+runWithNumber(536870914);
+runWithNumber(1073741773);
+runWithNumber(1073741774);
+runWithNumber(1073741775);
+runWithNumber(1073741776);
+runWithNumber(-536870913);
+runWithNumber(-536870914);
+runWithNumber(-536870915);
+runWithNumber(-1073741823);
+runWithNumber(-1073741824);
+runWithNumber(-1073741825);
+runWithNumber(-1073741826);
index 42731a2..43cd884 100644 (file)
@@ -1,3 +1,49 @@
+2019-04-05  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] OSRExit recovery for SpeculativeAdd does not consier "A = A + A" pattern
+        https://bugs.webkit.org/show_bug.cgi?id=196582
+
+        Reviewed by Saam Barati.
+
+        In DFG, our ArithAdd with overflow is executed speculatively, and we recover the value when overflow flag is set.
+        The recovery is subtracting the operand from the destination to get the original two operands. Our recovery code
+        handles A + B = A, A + B = B cases. But it misses A + A = A case (here, A and B are GPRReg). Our recovery code
+        attempts to produce the original operand by performing A - A, and it always produces zero accidentally.
+
+        This patch adds the recovery code for A + A = A case. Because we know that this ArithAdd overflows, and operands were
+        same values, we can calculate the original operand from the destination value by `((int32_t)value >> 1) ^ 0x80000000`.
+
+        We also found that FTL recovery code is dead. We remove them in this patch.
+
+        * dfg/DFGOSRExit.cpp:
+        (JSC::DFG::OSRExit::executeOSRExit):
+        (JSC::DFG::OSRExit::compileExit):
+        * dfg/DFGOSRExit.h:
+        (JSC::DFG::SpeculationRecovery::SpeculationRecovery):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileArithAdd):
+        * ftl/FTLExitValue.cpp:
+        (JSC::FTL::ExitValue::dataFormat const):
+        (JSC::FTL::ExitValue::dumpInContext const):
+        * ftl/FTLExitValue.h:
+        (JSC::FTL::ExitValue::isArgument const):
+        (JSC::FTL::ExitValue::hasIndexInStackmapLocations const):
+        (JSC::FTL::ExitValue::adjustStackmapLocationsIndexByOffset):
+        (JSC::FTL::ExitValue::recovery): Deleted.
+        (JSC::FTL::ExitValue::isRecovery const): Deleted.
+        (JSC::FTL::ExitValue::leftRecoveryArgument const): Deleted.
+        (JSC::FTL::ExitValue::rightRecoveryArgument const): Deleted.
+        (JSC::FTL::ExitValue::recoveryFormat const): Deleted.
+        (JSC::FTL::ExitValue::recoveryOpcode const): Deleted.
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
+        (JSC::FTL::DFG::LowerDFGToB3::preparePatchpointForExceptions):
+        (JSC::FTL::DFG::LowerDFGToB3::appendOSRExit):
+        (JSC::FTL::DFG::LowerDFGToB3::exitValueForNode):
+        (JSC::FTL::DFG::LowerDFGToB3::addAvailableRecovery): Deleted.
+        * ftl/FTLOSRExitCompiler.cpp:
+        (JSC::FTL::compileRecovery):
+
 2019-04-05  Ryan Haddad  <ryanhaddad@apple.com>
 
         Unreviewed, rolling out r243665.
index ab6f4b9..f1db5dc 100644 (file)
@@ -475,6 +475,14 @@ void OSRExit::executeOSRExit(Context& context)
 #endif
                 break;
 
+            case SpeculativeAddSelf:
+                cpu.gpr(recovery->dest()) = static_cast<uint32_t>(cpu.gpr<int32_t>(recovery->dest()) >> 1) ^ 0x80000000U;
+#if USE(JSVALUE64)
+                ASSERT(!(cpu.gpr(recovery->dest()) >> 32));
+                cpu.gpr(recovery->dest()) |= TagTypeNumber;
+#endif
+                break;
+
             case SpeculativeAddImmediate:
                 cpu.gpr(recovery->dest()) = (cpu.gpr<uint32_t>(recovery->dest()) - recovery->immediate());
 #if USE(JSVALUE64)
@@ -1117,6 +1125,15 @@ void OSRExit::compileExit(CCallHelpers& jit, VM& vm, const OSRExit& exit, const
 #endif
             break;
 
+        case SpeculativeAddSelf:
+            // If A + A = A (int32_t) overflows, A can be recovered by ((static_cast<int32_t>(A) >> 1) ^ 0x8000000).
+            jit.rshift32(AssemblyHelpers::TrustedImm32(1), recovery->dest());
+            jit.xor32(AssemblyHelpers::TrustedImm32(0x80000000), recovery->dest());
+#if USE(JSVALUE64)
+            jit.or64(GPRInfo::tagTypeNumberRegister, recovery->dest());
+#endif
+            break;
+
         case SpeculativeAddImmediate:
             jit.sub32(AssemblyHelpers::Imm32(recovery->immediate()), recovery->dest());
 #if USE(JSVALUE64)
index ca913ca..f5422ea 100644 (file)
@@ -59,6 +59,7 @@ struct Node;
 // may need be performed should a speculation check fail.
 enum SpeculationRecoveryType : uint8_t {
     SpeculativeAdd,
+    SpeculativeAddSelf,
     SpeculativeAddImmediate,
     BooleanSpeculationCheck
 };
@@ -74,7 +75,7 @@ public:
         , m_dest(dest)
         , m_type(type)
     {
-        ASSERT(m_type == SpeculativeAdd || m_type == BooleanSpeculationCheck);
+        ASSERT(m_type == SpeculativeAdd || m_type == SpeculativeAddSelf || m_type == BooleanSpeculationCheck);
     }
 
     SpeculationRecovery(SpeculationRecoveryType type, GPRReg dest, int32_t immediate)
index c956405..036cb92 100644 (file)
@@ -4306,7 +4306,9 @@ void SpeculativeJIT::compileArithAdd(Node* node)
         else {
             MacroAssembler::Jump check = m_jit.branchAdd32(MacroAssembler::Overflow, gpr1, gpr2, gprResult);
                 
-            if (gpr1 == gprResult)
+            if (gpr1 == gprResult && gpr2 == gprResult)
+                speculationCheck(Overflow, JSValueRegs(), 0, check, SpeculationRecovery(SpeculativeAddSelf, gprResult, gpr2));
+            else if (gpr1 == gprResult)
                 speculationCheck(Overflow, JSValueRegs(), 0, check, SpeculationRecovery(SpeculativeAdd, gprResult, gpr2));
             else if (gpr2 == gprResult)
                 speculationCheck(Overflow, JSValueRegs(), 0, check, SpeculationRecovery(SpeculativeAdd, gprResult, gpr1));
index 7004b9b..b36db04 100644 (file)
@@ -75,9 +75,6 @@ DataFormat ExitValue::dataFormat() const
             
     case ExitValueInJSStackAsDouble:
         return DataFormatDouble;
-            
-    case ExitValueRecovery:
-        return recoveryFormat();
     }
         
     RELEASE_ASSERT_NOT_REACHED();
@@ -110,9 +107,6 @@ void ExitValue::dumpInContext(PrintStream& out, DumpContext* context) const
     case ExitValueInJSStackAsDouble:
         out.print("InJSStackAsDouble:", virtualRegister());
         return;
-    case ExitValueRecovery:
-        out.print("Recovery(", recoveryOpcode(), ", arg", leftRecoveryArgument(), ", arg", rightRecoveryArgument(), ", ", recoveryFormat(), ")");
-        return;
     case ExitValueMaterializeNewObject:
         out.print("Materialize(", WTF::RawPointer(objectMaterialization()), ")");
         return;
index c9946b2..838da64 100644 (file)
@@ -54,7 +54,6 @@ enum ExitValueKind {
     ExitValueInJSStackAsInt32,
     ExitValueInJSStackAsInt52,
     ExitValueInJSStackAsDouble,
-    ExitValueRecovery,
     ExitValueMaterializeNewObject
 };
 
@@ -124,17 +123,6 @@ public:
         return result;
     }
     
-    static ExitValue recovery(RecoveryOpcode opcode, unsigned leftArgument, unsigned rightArgument, DataFormat format)
-    {
-        ExitValue result;
-        result.m_kind = ExitValueRecovery;
-        result.u.recovery.opcode = opcode;
-        result.u.recovery.leftArgument = leftArgument;
-        result.u.recovery.rightArgument = rightArgument;
-        result.u.recovery.format = format;
-        return result;
-    }
-    
     static ExitValue materializeNewObject(ExitTimeObjectMaterialization*);
     
     ExitValueKind kind() const { return m_kind; }
@@ -154,9 +142,8 @@ public:
     }
     bool isConstant() const { return kind() == ExitValueConstant; }
     bool isArgument() const { return kind() == ExitValueArgument; }
-    bool isRecovery() const { return kind() == ExitValueRecovery; }
     bool isObjectMaterialization() const { return kind() == ExitValueMaterializeNewObject; }
-    bool hasIndexInStackmapLocations() const { return isArgument() || isRecovery(); }
+    bool hasIndexInStackmapLocations() const { return isArgument(); }
     
     ExitArgument exitArgument() const
     {
@@ -164,40 +151,11 @@ public:
         return ExitArgument(u.argument);
     }
     
-    unsigned leftRecoveryArgument() const
-    {
-        ASSERT(isRecovery());
-        return u.recovery.leftArgument;
-    }
-    
-    unsigned rightRecoveryArgument() const
-    {
-        ASSERT(isRecovery());
-        return u.recovery.rightArgument;
-    }
-
     void adjustStackmapLocationsIndexByOffset(unsigned offset)
     {
         ASSERT(hasIndexInStackmapLocations());
-        if (isArgument())
-            u.argument.argument += offset;
-        else {
-            ASSERT(isRecovery());
-            u.recovery.rightArgument += offset;
-            u.recovery.leftArgument += offset;
-        }
-    }
-    
-    DataFormat recoveryFormat() const
-    {
-        ASSERT(isRecovery());
-        return static_cast<DataFormat>(u.recovery.format);
-    }
-    
-    RecoveryOpcode recoveryOpcode() const
-    {
-        ASSERT(isRecovery());
-        return static_cast<RecoveryOpcode>(u.recovery.opcode);
+        ASSERT(isArgument());
+        u.argument.argument += offset;
     }
     
     JSValue constant() const
@@ -246,12 +204,6 @@ private:
         ExitArgumentRepresentation argument;
         EncodedJSValue constant;
         int virtualRegister;
-        struct {
-            uint16_t leftArgument;
-            uint16_t rightArgument;
-            uint16_t opcode;
-            uint16_t format;
-        } recovery;
         ExitTimeObjectMaterialization* newObjectMaterializationData;
     } u;
 };
index 9dfd810..bc0d675 100644 (file)
@@ -676,8 +676,6 @@ private:
         if (verboseCompilationEnabled())
             dataLog("Lowering ", m_node, "\n");
         
-        m_availableRecoveries.shrink(0);
-        
         m_interpreter.startExecuting();
         m_interpreter.executeKnownEdgeTypes(m_node);
 
@@ -16744,11 +16742,7 @@ private:
         if (!willCatchException)
             return PatchpointExceptionHandle::defaultHandle(m_ftlState);
 
-        if (verboseCompilationEnabled()) {
-            dataLog("    Patchpoint exception OSR exit #", m_ftlState.jitCode->osrExitDescriptors.size(), " with availability: ", availabilityMap(), "\n");
-            if (!m_availableRecoveries.isEmpty())
-                dataLog("        Available recoveries: ", listDump(m_availableRecoveries), "\n");
-        }
+        dataLogLnIf(verboseCompilationEnabled(), "    Patchpoint exception OSR exit #", m_ftlState.jitCode->osrExitDescriptors.size(), " with availability: ", availabilityMap());
 
         bool exitOK = true;
         NodeOrigin origin = m_origin.withForExitAndExitOK(opCatchOrigin, exitOK);
@@ -16802,11 +16796,7 @@ private:
         ExitKind kind, FormattedValue lowValue, const MethodOfGettingAValueProfile& profile, LValue failCondition, 
         NodeOrigin origin, bool isExceptionHandler = false)
     {
-        if (verboseCompilationEnabled()) {
-            dataLog("    OSR exit #", m_ftlState.jitCode->osrExitDescriptors.size(), " with availability: ", availabilityMap(), "\n");
-            if (!m_availableRecoveries.isEmpty())
-                dataLog("        Available recoveries: ", listDump(m_availableRecoveries), "\n");
-        }
+        dataLogLnIf(verboseCompilationEnabled(), "    OSR exit #", m_ftlState.jitCode->osrExitDescriptors.size(), " with availability: ", availabilityMap());
 
         DFG_ASSERT(m_graph, m_node, origin.exitOK);
 
@@ -17000,18 +16990,6 @@ private:
             }
         }
         
-        for (unsigned i = 0; i < m_availableRecoveries.size(); ++i) {
-            AvailableRecovery recovery = m_availableRecoveries[i];
-            if (recovery.node() != node)
-                continue;
-            ExitValue result = ExitValue::recovery(
-                recovery.opcode(), arguments.size(), arguments.size() + 1,
-                recovery.format());
-            arguments.append(recovery.left());
-            arguments.append(recovery.right());
-            return result;
-        }
-        
         LoweredNodeValue value = m_int32Values.get(node);
         if (isValid(value))
             return exitArgument(arguments, DataFormatInt32, value.value());
@@ -17078,18 +17056,6 @@ private:
         DFG_CRASH(m_graph, m_node, toCString("Cannot find value for node: ", node).data());
     }
 
-    void addAvailableRecovery(
-        Node* node, RecoveryOpcode opcode, LValue left, LValue right, DataFormat format)
-    {
-        m_availableRecoveries.append(AvailableRecovery(node, opcode, left, right, format));
-    }
-    
-    void addAvailableRecovery(
-        Edge edge, RecoveryOpcode opcode, LValue left, LValue right, DataFormat format)
-    {
-        addAvailableRecovery(edge.node(), opcode, left, right, format);
-    }
-    
     void setInt32(Node* node, LValue value)
     {
         m_int32Values.set(node, LoweredNodeValue(value, m_highBlock));
@@ -17350,8 +17316,6 @@ private:
     
     LocalOSRAvailabilityCalculator m_availabilityCalculator;
     
-    Vector<AvailableRecovery, 3> m_availableRecoveries;
-    
     InPlaceAbstractState m_state;
     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
     DFG::BasicBlock* m_highBlock;
index 08ae463..d94390f 100644 (file)
@@ -124,44 +124,6 @@ static void compileRecovery(
         jit.load64(AssemblyHelpers::addressFor(value.virtualRegister()), GPRInfo::regT0);
         break;
             
-    case ExitValueRecovery:
-        Location::forValueRep(valueReps[value.rightRecoveryArgument()]).restoreInto(
-            jit, registerScratch, GPRInfo::regT1);
-        Location::forValueRep(valueReps[value.leftRecoveryArgument()]).restoreInto(
-            jit, registerScratch, GPRInfo::regT0);
-        switch (value.recoveryOpcode()) {
-        case AddRecovery:
-            switch (value.recoveryFormat()) {
-            case DataFormatInt32:
-                jit.add32(GPRInfo::regT1, GPRInfo::regT0);
-                break;
-            case DataFormatInt52:
-                jit.add64(GPRInfo::regT1, GPRInfo::regT0);
-                break;
-            default:
-                RELEASE_ASSERT_NOT_REACHED();
-                break;
-            }
-            break;
-        case SubRecovery:
-            switch (value.recoveryFormat()) {
-            case DataFormatInt32:
-                jit.sub32(GPRInfo::regT1, GPRInfo::regT0);
-                break;
-            case DataFormatInt52:
-                jit.sub64(GPRInfo::regT1, GPRInfo::regT0);
-                break;
-            default:
-                RELEASE_ASSERT_NOT_REACHED();
-                break;
-            }
-            break;
-        default:
-            RELEASE_ASSERT_NOT_REACHED();
-            break;
-        }
-        break;
-        
     case ExitValueMaterializeNewObject:
         jit.loadPtr(materializationToPointer.get(value.objectMaterialization()), GPRInfo::regT0);
         break;