<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[128699] trunk/Source/JavaScriptCore</title>
</head>
<body>

<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/128699">128699</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2012-09-15 19:36:22 -0700 (Sat, 15 Sep 2012)</dd>
</dl>

<h3>Log Message</h3>
<pre>Structure check hoisting fails to consider the possibility of conflicting checks on the source of the first assignment to the hoisted variable
https://bugs.webkit.org/show_bug.cgi?id=96872

Reviewed by Oliver Hunt.

This does a few related things:
        
- It turns off the use of ForceOSRExit for sure-to-fail CheckStructures, because
  I noticed that this would sometimes happen for a ForwardCheckStructure. The
  problem is that ForceOSRExit exits backwards, not forwards. Since the code that
  led to those ForceOSRExit's being inserted was written out of paranoia rather
  than need, I removed it. Specifically, I removed the m_isValid = false code
  for CheckStructure/StructureTransitionWatchpoint in AbstractState.
        
- If a structure check causes a structure set to go empty, we don't want a
  PutStructure to revive the set. It should instead be smart enough to realize 
  that an empty set implies that the code can't execute. This was the only &quot;bug&quot;
  that the use of m_isValid = false was preventing.
        
- Finally, the main change: structure check hoisting looks at the source of the
  SetLocals on structure-check-hoistable variables and ensures that the source
  is not checked with a conflicting structure. This is O(n^2) but it does not
  show up at all in performance tests.
        
The first two parts of this change were auxiliary bugs that were revealed by
the structure check hoister doing bad things.

* dfg/DFGAbstractState.cpp:
(JSC::DFG::AbstractState::initialize):
(JSC::DFG::AbstractState::execute):
* dfg/DFGStructureCheckHoistingPhase.cpp:
(JSC::DFG::StructureCheckHoistingPhase::run):</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAbstractStatecpp">trunk/Source/JavaScriptCore/dfg/DFGAbstractState.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGStructureCheckHoistingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGStructureCheckHoistingPhase.cpp</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (128698 => 128699)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog        2012-09-15 23:31:05 UTC (rev 128698)
+++ trunk/Source/JavaScriptCore/ChangeLog        2012-09-16 02:36:22 UTC (rev 128699)
</span><span class="lines">@@ -1,3 +1,38 @@
</span><ins>+2012-09-15  Filip Pizlo  &lt;fpizlo@apple.com&gt;
+
+        Structure check hoisting fails to consider the possibility of conflicting checks on the source of the first assignment to the hoisted variable
+        https://bugs.webkit.org/show_bug.cgi?id=96872
+
+        Reviewed by Oliver Hunt.
+
+        This does a few related things:
+        
+        - It turns off the use of ForceOSRExit for sure-to-fail CheckStructures, because
+          I noticed that this would sometimes happen for a ForwardCheckStructure. The
+          problem is that ForceOSRExit exits backwards, not forwards. Since the code that
+          led to those ForceOSRExit's being inserted was written out of paranoia rather
+          than need, I removed it. Specifically, I removed the m_isValid = false code
+          for CheckStructure/StructureTransitionWatchpoint in AbstractState.
+        
+        - If a structure check causes a structure set to go empty, we don't want a
+          PutStructure to revive the set. It should instead be smart enough to realize 
+          that an empty set implies that the code can't execute. This was the only &quot;bug&quot;
+          that the use of m_isValid = false was preventing.
+        
+        - Finally, the main change: structure check hoisting looks at the source of the
+          SetLocals on structure-check-hoistable variables and ensures that the source
+          is not checked with a conflicting structure. This is O(n^2) but it does not
+          show up at all in performance tests.
+        
+        The first two parts of this change were auxiliary bugs that were revealed by
+        the structure check hoister doing bad things.
+
+        * dfg/DFGAbstractState.cpp:
+        (JSC::DFG::AbstractState::initialize):
+        (JSC::DFG::AbstractState::execute):
+        * dfg/DFGStructureCheckHoistingPhase.cpp:
+        (JSC::DFG::StructureCheckHoistingPhase::run):
+
</ins><span class="cx"> 2012-09-14  Filip Pizlo  &lt;fpizlo@apple.com&gt;
</span><span class="cx"> 
</span><span class="cx">         All of the things in SparseArrayValueMap should be out-of-line
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAbstractStatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAbstractState.cpp (128698 => 128699)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAbstractState.cpp        2012-09-15 23:31:05 UTC (rev 128698)
+++ trunk/Source/JavaScriptCore/dfg/DFGAbstractState.cpp        2012-09-16 02:36:22 UTC (rev 128699)
</span><span class="lines">@@ -147,7 +147,13 @@
</span><span class="cx">         for (size_t i = 0; i &lt; graph.m_mustHandleValues.size(); ++i) {
</span><span class="cx">             AbstractValue value;
</span><span class="cx">             value.setMostSpecific(graph.m_mustHandleValues[i]);
</span><del>-            block-&gt;valuesAtHead.operand(graph.m_mustHandleValues.operandForIndex(i)).merge(value);
</del><ins>+            int operand = graph.m_mustHandleValues.operandForIndex(i);
+            block-&gt;valuesAtHead.operand(operand).merge(value);
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+            dataLog(&quot;    Initializing Block #%u, operand r%d, to &quot;, blockIndex, operand);
+            block-&gt;valuesAtHead.operand(operand).dump(WTF::dataFile());
+            dataLog(&quot;\n&quot;);
+#endif
</ins><span class="cx">         }
</span><span class="cx">         block-&gt;cfaShouldRevisit = true;
</span><span class="cx">     }
</span><span class="lines">@@ -1293,20 +1299,6 @@
</span><span class="cx">             !value.m_currentKnownStructure.isSubsetOf(set)
</span><span class="cx">             || !isCellSpeculation(value.m_type));
</span><span class="cx">         value.filter(set);
</span><del>-        // This is likely to be unnecessary, but it's conservative, and that's a good thing.
-        // This is trying to avoid situations where the CFA proves that this structure check
-        // must fail due to a future structure proof. We have two options at that point. We
-        // can either compile all subsequent code as we would otherwise, or we can ensure
-        // that the subsequent code is never reachable. The former is correct because the
-        // Proof Is Infallible (TM) -- hence even if we don't force the subsequent code to
-        // be unreachable, it must be unreachable nonetheless. But imagine what would happen
-        // if the proof was borked. In the former case, we'd get really bizarre bugs where
-        // we assumed that the structure of this object was known even though it wasn't. In
-        // the latter case, we'd have a slight performance pathology because this would be
-        // turned into an OSR exit unnecessarily. Which would you rather have?
-        if (value.m_currentKnownStructure.isClear()
-            || value.m_futurePossibleStructure.isClear())
-            m_isValid = false;
</del><span class="cx">         m_haveStructures = true;
</span><span class="cx">         break;
</span><span class="cx">     }
</span><span class="lines">@@ -1325,10 +1317,6 @@
</span><span class="cx">         
</span><span class="cx">         ASSERT(value.isClear() || isCellSpeculation(value.m_type)); // Value could be clear if we've proven must-exit due to a speculation statically known to be bad.
</span><span class="cx">         value.filter(node.structure());
</span><del>-        // See comment in CheckStructure for why this is here.
-        if (value.m_currentKnownStructure.isClear()
-            || value.m_futurePossibleStructure.isClear())
-            m_isValid = false;
</del><span class="cx">         m_haveStructures = true;
</span><span class="cx">         node.setCanExit(true);
</span><span class="cx">         break;
</span><span class="lines">@@ -1337,9 +1325,11 @@
</span><span class="cx">     case PutStructure:
</span><span class="cx">     case PhantomPutStructure:
</span><span class="cx">         node.setCanExit(false);
</span><del>-        clobberStructures(indexInBlock);
-        forNode(node.child1()).set(node.structureTransitionData().newStructure);
-        m_haveStructures = true;
</del><ins>+        if (!forNode(node.child1()).m_currentKnownStructure.isClear()) {
+            clobberStructures(indexInBlock);
+            forNode(node.child1()).set(node.structureTransitionData().newStructure);
+            m_haveStructures = true;
+        }
</ins><span class="cx">         break;
</span><span class="cx">     case GetButterfly:
</span><span class="cx">     case AllocatePropertyStorage:
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGStructureCheckHoistingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGStructureCheckHoistingPhase.cpp (128698 => 128699)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGStructureCheckHoistingPhase.cpp        2012-09-15 23:31:05 UTC (rev 128698)
+++ trunk/Source/JavaScriptCore/dfg/DFGStructureCheckHoistingPhase.cpp        2012-09-16 02:36:22 UTC (rev 128699)
</span><span class="lines">@@ -67,7 +67,8 @@
</span><span class="cx">                 if (!node.shouldGenerate())
</span><span class="cx">                     continue;
</span><span class="cx">                 switch (node.op()) {
</span><del>-                case CheckStructure: {
</del><ins>+                case CheckStructure:
+                case StructureTransitionWatchpoint: {
</ins><span class="cx">                     Node&amp; child = m_graph[node.child1()];
</span><span class="cx">                     if (child.op() != GetLocal)
</span><span class="cx">                         break;
</span><span class="lines">@@ -91,7 +92,6 @@
</span><span class="cx">                 case GetByOffset:
</span><span class="cx">                 case PutByOffset:
</span><span class="cx">                 case PutStructure:
</span><del>-                case StructureTransitionWatchpoint:
</del><span class="cx">                 case AllocatePropertyStorage:
</span><span class="cx">                 case ReallocatePropertyStorage:
</span><span class="cx">                 case GetButterfly:
</span><span class="lines">@@ -105,6 +105,40 @@
</span><span class="cx">                     // Don't count these uses.
</span><span class="cx">                     break;
</span><span class="cx">                     
</span><ins>+                case SetLocal: {
+                    // Find all uses of the source of the SetLocal. If any of them are a
+                    // kind of CheckStructure, then we should notice them to ensure that
+                    // we're not hoisting a check that would contravene checks that are
+                    // already being performed.
+                    VariableAccessData* variable = node.variableAccessData();
+                    if (variable-&gt;isCaptured() || variable-&gt;structureCheckHoistingFailed())
+                        break;
+                    if (!isCellSpeculation(variable-&gt;prediction()))
+                        break;
+                    NodeIndex source = node.child1().index();
+                    for (unsigned subIndexInBlock = 0; subIndexInBlock &lt; block-&gt;size(); ++subIndexInBlock) {
+                        NodeIndex subNodeIndex = block-&gt;at(subIndexInBlock);
+                        Node&amp; subNode = m_graph[subNodeIndex];
+                        if (!subNode.shouldGenerate())
+                            continue;
+                        switch (subNode.op()) {
+                        case CheckStructure:
+                        case StructureTransitionWatchpoint: {
+                            if (subNode.child1().index() != source)
+                                break;
+                            
+                            noticeStructureCheck(variable, subNode.structureSet());
+                            break;
+                        }
+                        default:
+                            break;
+                        }
+                    }
+                    
+                    m_graph.vote(node, VoteOther);
+                    break;
+                }
+                    
</ins><span class="cx">                 default:
</span><span class="cx">                     m_graph.vote(node, VoteOther);
</span><span class="cx">                     break;
</span></span></pre>
</div>
</div>

</body>
</html>