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

Timestamp:

May 19, 2016, 2:25:29 PM (9 years ago)

Author:

[email protected]

Message:

DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
​https://bugs.webkit.org/show_bug.cgi?id=144527

Reviewed by Saam Barati.

Source/JavaScriptCore:

This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
the execution of one implies that the other one must also execute. It means that the two
blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
this has caused problems in the past. If we hoist something that may exit from a block that
was not control equivalent to the pre-header then it's possible that the node's speculation
will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
HoistingFailed exit kind.

Note that this deliberately still allows us to hoist things that may exit even if they are
not control equivalent to the pre-header. This is necessary because the profitability of
hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
shot.

This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
problems on that program even though LICM previously did the wrong thing).

• JavaScriptCore.xcodeproj/project.pbxproj:
• bytecode/ExitKind.cpp:

(JSC::exitKindToString):

• bytecode/ExitKind.h:
• dfg/DFGAtTailAbstractState.h:

(JSC::DFG::AtTailAbstractState::operator bool):
(JSC::DFG::AtTailAbstractState::initializeTo):

• dfg/DFGBackwardsCFG.h: Added.

(JSC::DFG::BackwardsCFG::BackwardsCFG):

• dfg/DFGBackwardsDominators.h: Added.

(JSC::DFG::BackwardsDominators::BackwardsDominators):

• dfg/DFGCommon.h:

(JSC::DFG::checkAndSet): Deleted.

• dfg/DFGControlEquivalenceAnalysis.h: Added.

(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
(JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
(JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::ensureBackwardsCFG):
(JSC::DFG::Graph::ensureBackwardsDominators):
(JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
(JSC::DFG::Graph::methodOfGettingAValueProfileFor):

• dfg/DFGGraph.h:

(JSC::DFG::Graph::hasDebuggerEnabled):

• dfg/DFGInPlaceAbstractState.h:

(JSC::DFG::InPlaceAbstractState::operator bool):
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):

• dfg/DFGLICMPhase.cpp:

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

• dfg/DFGMayExit.cpp:

(JSC::DFG::mayExit):

• dfg/DFGMayExit.h:
• dfg/DFGNode.h:
• dfg/DFGNodeOrigin.cpp:

(JSC::DFG::NodeOrigin::dump):

• dfg/DFGNodeOrigin.h:

(JSC::DFG::NodeOrigin::takeValidExit):
(JSC::DFG::NodeOrigin::withWasHoisted):
(JSC::DFG::NodeOrigin::forInsertingAfter):

• dfg/DFGNullAbstractState.h: Added.

(JSC::DFG::NullAbstractState::NullAbstractState):
(JSC::DFG::NullAbstractState::operator bool):
(JSC::DFG::NullAbstractState::forNode):

• dfg/DFGOSRExit.cpp:

(JSC::DFG::OSRExit::OSRExit):

• dfg/DFGOSRExitBase.cpp:

(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):

• dfg/DFGOSRExitBase.h:

(JSC::DFG::OSRExitBase::OSRExitBase):

• dfg/DFGTypeCheckHoistingPhase.cpp:

(JSC::DFG::TypeCheckHoistingPhase::run):

• ftl/FTLOSRExit.cpp:

(JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
(JSC::FTL::OSRExit::OSRExit):

• ftl/FTLOSRExit.h:

Source/WTF:

This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
passing around a Graph template argument that follows the protocol shared by DFG::CFG,
B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
node that it uses as the root in the inverted graph. This currently may resort to some
heuristics in programs that have an infinite loop, but other than that, it'll work well in
the general case.

This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
backwards dominators, which then allows us to easily answer control flow equivalence
queries.

• CMakeLists.txt:
• WTF.xcodeproj/project.pbxproj:
• wtf/BackwardsGraph.h: Added.

(WTF::BackwardsGraph::Node::Node):
(WTF::BackwardsGraph::Node::root):
(WTF::BackwardsGraph::Node::operator==):
(WTF::BackwardsGraph::Node::operator!=):
(WTF::BackwardsGraph::Node::operator bool):
(WTF::BackwardsGraph::Node::isRoot):
(WTF::BackwardsGraph::Node::node):
(WTF::BackwardsGraph::Set::Set):
(WTF::BackwardsGraph::Set::add):
(WTF::BackwardsGraph::Set::remove):
(WTF::BackwardsGraph::Set::contains):
(WTF::BackwardsGraph::Set::dump):
(WTF::BackwardsGraph::Map::Map):
(WTF::BackwardsGraph::Map::clear):
(WTF::BackwardsGraph::Map::size):
(WTF::BackwardsGraph::Map::operator[]):
(WTF::BackwardsGraph::BackwardsGraph):
(WTF::BackwardsGraph::root):
(WTF::BackwardsGraph::newMap):
(WTF::BackwardsGraph::successors):
(WTF::BackwardsGraph::predecessors):
(WTF::BackwardsGraph::index):
(WTF::BackwardsGraph::node):
(WTF::BackwardsGraph::numNodes):
(WTF::BackwardsGraph::dump):

• wtf/Dominators.h:

(WTF::Dominators::Dominators):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):

• wtf/GraphNodeWorklist.h:

(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):

• wtf/StdLibExtras.h:

(WTF::callStatelessLambda):
(WTF::checkAndSet):

LayoutTests:

Add tests for LICM hoisting things that would only exit if hoisted.

• js/regress/licm-dragons-expected.txt: Added.
• js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
• js/regress/licm-dragons-out-of-bounds.html: Added.
• js/regress/licm-dragons-overflow-expected.txt: Added.
• js/regress/licm-dragons-overflow.html: Added.
• js/regress/licm-dragons.html: Added.
• js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.

(foo):

• js/regress/script-tests/licm-dragons-overflow.js: Added.

(foo):

• js/regress/script-tests/licm-dragons.js: Added.

(foo):

File:

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

trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -34 +34 @@
 #include "DFGClobberSet.h"
 #include "DFGClobberize.h"
+#include "DFGControlEquivalenceAnalysis.h"
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGMayExit.h"
 #include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
@@ -75 +77 @@
         m_graph.ensureDominators();
         m_graph.ensureNaturalLoops();
+        m_graph.ensureControlEquivalenceAnalysis();
 
         if (verbose) {
@@ -261 +264 @@
         // https://bugs.webkit.org/show_bug.cgi?id=144525
         
-        // FIXME: If a node has a type check - even something like a CheckStructure - then we should
-        // only hoist the node if we know that it will execute on every loop iteration or if we know
-        // that the type check will always succeed at the loop pre-header through some other means
-        // (like looking at prediction propagation results). Otherwise, we might make a mistake like
-        // this:
-        //
-        // var o = ...; // sometimes null and sometimes an object with structure S1.
-        // for (...) {
-        //     if (o)
-        //         ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
-        // }
-        //
-        // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
-        // will have a recompile. We'll then end up thinking that the get_by_id needs to be
-        // polymorphic, which is false.
-        //
-        // We can counter this by either having a control flow equivalence check, or by consulting
-        // prediction propagation to see if the check would always succeed. Prediction propagation
-        // would not be enough for things like:
-        //
-        // var p = ...; // some boolean predicate
-        // var o = {};
-        // if (p)
-        //     o.f = 42;
-        // for (...) {
-        //     if (p)
-        //         ... = o.f;
-        // }
-        //
-        // Prediction propagation can't tell us anything about the structure, and the CheckStructure
-        // will appear to be hoistable because the loop doesn't clobber structures. The cell check
-        // in the CheckStructure will be hoistable though, since prediction propagation can tell us
-        // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
-        // only effective guard.
-        //
-        // https://bugs.webkit.org/show_bug.cgi?id=144527
-        
         if (readsOverlap(m_graph, node, data.writes)) {
             if (verbose) {
@@ -312 +278 @@
                 dataLog(
                     "    Not hoisting ", node, " because it isn't safe to execute.\n");
+            }
+            return false;
+        }
+        
+        NodeOrigin originalOrigin = node->origin;
+
+        // NOTE: We could just use BackwardsDominators here directly, since we already know that the
+        // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
+        // dominance checks are O(1) and only a few integer compares.
+        bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
+            && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
+        
+        if (addsBlindSpeculation
+            && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
+            if (verbose) {
+                dataLog(
+                    "    Not hoisting ", node, " because it may exit and the pre-header (",
+                    *data.preHeader, ") is not control equivalent to the node's original block (",
+                    *fromBlock, ") and hoisting had previously failed.\n");
             }
             return false;
@@ -327 +312 @@
         data.preHeader->insertBeforeTerminal(node);
         node->owner = data.preHeader;
-        NodeOrigin originalOrigin = node->origin;
-        node->origin = data.preHeader->terminal()->origin.withSemantic(node->origin.semantic);
+        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+        node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+        node->origin.wasHoisted |= addsBlindSpeculation;
         
         // Modify the states at the end of the preHeader of the loop we hoisted to,