Changeset 232000 in webkit for trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

Timestamp:

May 19, 2018, 3:00:21 PM (7 years ago)

Author:

[email protected]

Message:

DFG should inline InstanceOf ICs
​https://bugs.webkit.org/show_bug.cgi?id=185695

Reviewed by Yusuke Suzuki.

Source/JavaScriptCore:

This teaches the DFG how to inline InstanceOf ICs into a MatchStructure node. This can then
be folded to a CheckStructure + JSConstant.

In the process of testing this, I found a bug where LICM was not hoisting things that
depended on ExtraOSREntryLocal because that might return SpecEmpty. I fixed that by teaching
LICM how to materialize CheckNotEmpty on demand whenever HoistingFailed.

This is a ~5% speed-up on boyer.

~2x speed-up on the instanceof-always-hit-one, instanceof-always-hit-two, and
instanceof-sometimes-hit microbenchmarks.

• JavaScriptCore.xcodeproj/project.pbxproj:
• Sources.txt:
• bytecode/GetByIdStatus.cpp:

(JSC::GetByIdStatus::appendVariant):
(JSC::GetByIdStatus::filter):

• bytecode/GetByIdStatus.h:

(JSC::GetByIdStatus::operator bool const):
(JSC::GetByIdStatus::operator! const): Deleted.

• bytecode/GetByIdVariant.h:

(JSC::GetByIdVariant::operator bool const):
(JSC::GetByIdVariant::operator! const): Deleted.

• bytecode/ICStatusUtils.h: Added.

(JSC::appendICStatusVariant):
(JSC::filterICStatusVariants):

• bytecode/InstanceOfStatus.cpp: Added.

(JSC::InstanceOfStatus::appendVariant):
(JSC::InstanceOfStatus::computeFor):
(JSC::InstanceOfStatus::computeForStubInfo):
(JSC::InstanceOfStatus::commonPrototype const):
(JSC::InstanceOfStatus::filter):

• bytecode/InstanceOfStatus.h: Added.

(JSC::InstanceOfStatus::InstanceOfStatus):
(JSC::InstanceOfStatus::state const):
(JSC::InstanceOfStatus::isSet const):
(JSC::InstanceOfStatus::operator bool const):
(JSC::InstanceOfStatus::isSimple const):
(JSC::InstanceOfStatus::takesSlowPath const):
(JSC::InstanceOfStatus::numVariants const):
(JSC::InstanceOfStatus::variants const):
(JSC::InstanceOfStatus::at const):
(JSC::InstanceOfStatus::operator[] const):

• bytecode/InstanceOfVariant.cpp: Added.

(JSC::InstanceOfVariant::InstanceOfVariant):
(JSC::InstanceOfVariant::attemptToMerge):
(JSC::InstanceOfVariant::dump const):
(JSC::InstanceOfVariant::dumpInContext const):

• bytecode/InstanceOfVariant.h: Added.

(JSC::InstanceOfVariant::InstanceOfVariant):
(JSC::InstanceOfVariant::operator bool const):
(JSC::InstanceOfVariant::structureSet const):
(JSC::InstanceOfVariant::structureSet):
(JSC::InstanceOfVariant::conditionSet const):
(JSC::InstanceOfVariant::prototype const):
(JSC::InstanceOfVariant::isHit const):

• bytecode/StructureStubInfo.cpp:

(JSC::StructureStubInfo::StructureStubInfo):

• bytecode/StructureStubInfo.h:

(JSC::StructureStubInfo::considerCaching):

• dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::parseBlock):

• dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

• dfg/DFGConstantFoldingPhase.cpp:

(JSC::DFG::ConstantFoldingPhase::foldConstants):

• dfg/DFGDoesGC.cpp:

(JSC::DFG::doesGC):

• dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):

• dfg/DFGGraph.h:
• dfg/DFGLICMPhase.cpp:

(JSC::DFG::LICMPhase::attemptHoist):

• dfg/DFGNode.cpp:

(JSC::DFG::Node::remove):

• dfg/DFGNode.h:

(JSC::DFG::Node::hasMatchStructureData):
(JSC::DFG::Node::matchStructureData):

• dfg/DFGNodeType.h:
• dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

• dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compileMatchStructure):

• dfg/DFGSpeculativeJIT.h:
• dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

• ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

• ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileMatchStructure):

Source/WTF:

I found myself needing a way to represent bottom/false/true/top, so I created it.

• WTF.xcodeproj/project.pbxproj:
• wtf/BooleanLattice.h: Added.

(WTF::lubBooleanLattice):
(WTF::printInternal):

• wtf/CMakeLists.txt:

File:

• trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (modified) (6 diffs)

trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2018 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -265 +265 @@
         
         m_state.initializeTo(data.preHeader);
-        if (!safeToExecute(m_state, m_graph, node)) {
-            if (verbose) {
-                dataLog(
-                    "    Not hoisting ", node, " because it isn't safe to execute.\n");
-            }
-            return false;
-        }
-        
+
         NodeOrigin originalOrigin = node->origin;
+        bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
 
         // NOTE: We could just use BackwardsDominators here directly, since we already know that the
@@ -281 +275 @@
             && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
         
-        if (addsBlindSpeculation
-            && m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed)) {
+        if (addsBlindSpeculation && !canSpeculateBlindly) {
             if (verbose) {
                 dataLog(
@@ -292 +285 @@
         }
         
+        // For abstract interpretation, these are in the reverse order that they appear in this
+        // vector.
+        Vector<Node*, 2> hoistedNodesReverse;
+        hoistedNodesReverse.append(node);
+
+        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+        
+        auto insertHoistedNode = [&] (Node* node) {
+            data.preHeader->insertBeforeTerminal(node);
+            node->owner = data.preHeader;
+            node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+            node->origin.wasHoisted |= addsBlindSpeculation;
+        };
+        
+        if (!safeToExecute(m_state, m_graph, node)) {
+            // See if we can rescue the situation by inserting blind speculations.
+            bool ignoreEmptyChildren = true;
+            if (canSpeculateBlindly
+                && safeToExecute(m_state, m_graph, node, ignoreEmptyChildren)) {
+                if (verbose) {
+                    dataLog(
+                        "    Rescuing hoisting by inserting empty checks.\n");
+                }
+                m_graph.doToChildren(
+                    node,
+                    [&] (Edge& edge) {
+                        if (!(m_state.forNode(edge).m_type & SpecEmpty))
+                            return;
+                        
+                        Node* check = m_graph.addNode(CheckNotEmpty, originalOrigin, Edge(edge.node(), UntypedUse));
+                        insertHoistedNode(check);
+                        hoistedNodesReverse.append(check);
+                    });
+            } else {
+                if (verbose) {
+                    dataLog(
+                        "    Not hoisting ", node, " because it isn't safe to execute.\n");
+                }
+                return false;
+            }
+        }
+        
         if (verbose) {
             dataLog(
@@ -298 +333 @@
         }
 
-        data.preHeader->insertBeforeTerminal(node);
-        node->owner = data.preHeader;
-        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
-        node->origin = terminalOrigin.withSemantic(node->origin.semantic);
-        node->origin.wasHoisted |= addsBlindSpeculation;
+        insertHoistedNode(node);
         
         // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
         m_state.trustEdgeProofs();
         m_state.initializeTo(data.preHeader);
-        m_interpreter.execute(node);
+        for (unsigned i = hoistedNodesReverse.size(); i--;)
+            m_interpreter.execute(hoistedNodesReverse[i]);
         // However, when walking various inner loops below, the proof status of
         // an edge may be trivially true, even if it's not true in the preheader
@@ -341 +373 @@
                 continue;
             m_state.initializeTo(subPreHeader);
-            m_interpreter.execute(node);
+            for (unsigned i = hoistedNodesReverse.size(); i--;)
+                m_interpreter.execute(hoistedNodesReverse[i]);
         }