<!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>[186795] trunk</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/186795">186795</a></dd>
<dt>Author</dt> <dd>basile_clement@apple.com</dd>
<dt>Date</dt> <dd>2015-07-13 16:27:30 -0700 (Mon, 13 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Object cycles should not prevent allocation elimination/sinking
https://bugs.webkit.org/show_bug.cgi?id=143073
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
This patch introduces a new allocation sinking phase that is able to
sink cycles, in DFGAllocationCycleSinkingPhase.cpp. This phase
supersedes the old allocation sinking phase in
DFGObjectAllocationSinkingPhase.cpp, as that previous phase was never
able to sink allocation cycles while the new phase sometimes can; see
DFGAllocationCycleSinkingPhase.cpp for details.
For now, the new sinking phase is kept behind a
JSC_enableAllocationCycleSinking flag that reverts to the old sinking
phase when false (i.e., by default). This also removes the old
JSC_enableObjectAllocationSinking flag. run-javascriptcore-tests
defaults to using the new sinking phase.
* dfg/DFGGraph.h:
(JSC::DFG::Graph::addStructureSet): Allow empty structure sets
* dfg/DFGLazyNode.cpp:
(JSC::DFG::LazyNode::dump): Prettier dump
* dfg/DFGNode.h:
(JSC::DFG::Node::cellOperand): Move to opInfo for MaterializeCreateActivation
(JSC::DFG::Node::hasStructureSet): Add MaterializeNewObject
(JSC::DFG::Node::objectMaterializationData): Move to opInfo2
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp: Remove unused header
* dfg/DFGObjectAllocationSinkingPhase.cpp:
(JSC::DFG::ObjectAllocationSinkingPhase::ObjectAllocationSinkingPhase): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::run): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::performSinking): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::lowerNonReadingOperationsOnPhantomAllocations): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::promoteSunkenFields): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::resolve): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::handleNode): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::createMaterialize): Deleted.
(JSC::DFG::ObjectAllocationSinkingPhase::populateMaterialize): Deleted.
* dfg/DFGObjectAllocationSinkingPhase.h:
* dfg/DFGPromotedHeapLocation.h: Add a hash and a helper function to PromotedLocationDescriptor
(JSC::DFG::PromotedLocationDescriptor::PromotedLocationDescriptor):
(JSC::DFG::PromotedLocationDescriptor::operator bool):
(JSC::DFG::PromotedLocationDescriptor::neededForMaterialization):
(JSC::DFG::PromotedLocationDescriptorHash::hash):
(JSC::DFG::PromotedLocationDescriptorHash::equal):
* dfg/DFGValidate.cpp:
(JSC::DFG::Validate::validateSSA): Assert that most nodes never see a phantom allocation
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::compileMaterializeNewObject): Use the new structureSet() operand
(JSC::FTL::DFG::LowerDFGToLLVM::compileMaterializeCreateActivation): Node has a new child
* ftl/FTLOSRExitCompiler.cpp: Handle materialization cycles
(JSC::FTL::compileStub):
* ftl/FTLOperations.cpp: Handle materialization cycles
(JSC::FTL::operationPopulateObjectInOSR):
(JSC::FTL::operationMaterializeObjectInOSR):
* ftl/FTLOperations.h: Handle materialization cycles
* tests/stress/correctly-sink-object-even-though-it-dies.js: Added.
(clobber):
(foo):
* tests/stress/eliminate-object-read-over-call.js: Added.
(clobber):
(foo):
* tests/stress/materialize-object-on-edge.js: Added.
(call):
(foo):
* tests/stress/object-sinking-stress.js: Added.
(foo):
* tests/stress/sink-object-cycle.js: Added.
(clobber):
(foo):
* tests/stress/sink-object-past-put.js: Added.
(clobber):
(foo):
* tests/stress/sinkable-new-object-in-loop.js: Added.
(foo):
LayoutTests:
Add a few microbenchmarks that show performance improvement when
sinking or elimininating object cycles.
* js/regress/elidable-new-object-cycle-expected.txt: Added.
* js/regress/elidable-new-object-cycle.html: Added.
* js/regress/script-tests/elidable-new-object-cycle.js: Added.
(sumOfArithSeries):
(foo):
* js/regress/script-tests/sinkable-closure-cycle.js: Added.
(factorial.f):
(factorial):
* js/regress/script-tests/sinkable-new-object-cycle.js: Added.
(sumOfArithSeries):
(verify):
(foo):
* js/regress/sinkable-closure-cycle-expected.txt: Added.
* js/regress/sinkable-closure-cycle.html: Added.
* js/regress/sinkable-new-object-cycle-expected.txt: Added.
* js/regress/sinkable-new-object-cycle.html: Added.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLazyNodecpp">trunk/Source/JavaScriptCore/dfg/DFGLazyNode.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeh">trunk/Source/JavaScriptCore/dfg/DFGNode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSRAvailabilityAnalysisPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhaseh">trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPromotedHeapLocationh">trunk/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGValidatecpp">trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLOSRExitCompilercpp">trunk/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLOperationscpp">trunk/Source/JavaScriptCore/ftl/FTLOperations.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLOperationsh">trunk/Source/JavaScriptCore/ftl/FTLOperations.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/LayoutTests/ChangeLog 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -1,3 +1,30 @@
</span><ins>+2015-07-13 Basile Clement <basile_clement@apple.com>
+
+ Object cycles should not prevent allocation elimination/sinking
+ https://bugs.webkit.org/show_bug.cgi?id=143073
+
+ Reviewed by Filip Pizlo.
+
+ Add a few microbenchmarks that show performance improvement when
+ sinking or elimininating object cycles.
+
+ * js/regress/elidable-new-object-cycle-expected.txt: Added.
+ * js/regress/elidable-new-object-cycle.html: Added.
+ * js/regress/script-tests/elidable-new-object-cycle.js: Added.
+ (sumOfArithSeries):
+ (foo):
+ * js/regress/script-tests/sinkable-closure-cycle.js: Added.
+ (factorial.f):
+ (factorial):
+ * js/regress/script-tests/sinkable-new-object-cycle.js: Added.
+ (sumOfArithSeries):
+ (verify):
+ (foo):
+ * js/regress/sinkable-closure-cycle-expected.txt: Added.
+ * js/regress/sinkable-closure-cycle.html: Added.
+ * js/regress/sinkable-new-object-cycle-expected.txt: Added.
+ * js/regress/sinkable-new-object-cycle.html: Added.
+
</ins><span class="cx"> 2015-07-13 Brent Fulgham <bfulgham@apple.com>
</span><span class="cx">
</span><span class="cx"> [Win] Skip failing table-related AX tests
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -1,3 +1,82 @@
</span><ins>+2015-07-13 Basile Clement <basile_clement@apple.com>
+
+ Object cycles should not prevent allocation elimination/sinking
+ https://bugs.webkit.org/show_bug.cgi?id=143073
+
+ Reviewed by Filip Pizlo.
+
+ This patch introduces a new allocation sinking phase that is able to
+ sink cycles, in DFGAllocationCycleSinkingPhase.cpp. This phase
+ supersedes the old allocation sinking phase in
+ DFGObjectAllocationSinkingPhase.cpp, as that previous phase was never
+ able to sink allocation cycles while the new phase sometimes can; see
+ DFGAllocationCycleSinkingPhase.cpp for details.
+
+ For now, the new sinking phase is kept behind a
+ JSC_enableAllocationCycleSinking flag that reverts to the old sinking
+ phase when false (i.e., by default). This also removes the old
+ JSC_enableObjectAllocationSinking flag. run-javascriptcore-tests
+ defaults to using the new sinking phase.
+
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::addStructureSet): Allow empty structure sets
+ * dfg/DFGLazyNode.cpp:
+ (JSC::DFG::LazyNode::dump): Prettier dump
+ * dfg/DFGNode.h:
+ (JSC::DFG::Node::cellOperand): Move to opInfo for MaterializeCreateActivation
+ (JSC::DFG::Node::hasStructureSet): Add MaterializeNewObject
+ (JSC::DFG::Node::objectMaterializationData): Move to opInfo2
+ * dfg/DFGOSRAvailabilityAnalysisPhase.cpp: Remove unused header
+ * dfg/DFGObjectAllocationSinkingPhase.cpp:
+ (JSC::DFG::ObjectAllocationSinkingPhase::ObjectAllocationSinkingPhase): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::run): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::performSinking): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::lowerNonReadingOperationsOnPhantomAllocations): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::promoteSunkenFields): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::resolve): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::handleNode): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::createMaterialize): Deleted.
+ (JSC::DFG::ObjectAllocationSinkingPhase::populateMaterialize): Deleted.
+ * dfg/DFGObjectAllocationSinkingPhase.h:
+ * dfg/DFGPromotedHeapLocation.h: Add a hash and a helper function to PromotedLocationDescriptor
+ (JSC::DFG::PromotedLocationDescriptor::PromotedLocationDescriptor):
+ (JSC::DFG::PromotedLocationDescriptor::operator bool):
+ (JSC::DFG::PromotedLocationDescriptor::neededForMaterialization):
+ (JSC::DFG::PromotedLocationDescriptorHash::hash):
+ (JSC::DFG::PromotedLocationDescriptorHash::equal):
+ * dfg/DFGValidate.cpp:
+ (JSC::DFG::Validate::validateSSA): Assert that most nodes never see a phantom allocation
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::DFG::LowerDFGToLLVM::compileMaterializeNewObject): Use the new structureSet() operand
+ (JSC::FTL::DFG::LowerDFGToLLVM::compileMaterializeCreateActivation): Node has a new child
+ * ftl/FTLOSRExitCompiler.cpp: Handle materialization cycles
+ (JSC::FTL::compileStub):
+ * ftl/FTLOperations.cpp: Handle materialization cycles
+ (JSC::FTL::operationPopulateObjectInOSR):
+ (JSC::FTL::operationMaterializeObjectInOSR):
+ * ftl/FTLOperations.h: Handle materialization cycles
+ * tests/stress/correctly-sink-object-even-though-it-dies.js: Added.
+ (clobber):
+ (foo):
+ * tests/stress/eliminate-object-read-over-call.js: Added.
+ (clobber):
+ (foo):
+ * tests/stress/materialize-object-on-edge.js: Added.
+ (call):
+ (foo):
+ * tests/stress/object-sinking-stress.js: Added.
+ (foo):
+ * tests/stress/sink-object-cycle.js: Added.
+ (clobber):
+ (foo):
+ * tests/stress/sink-object-past-put.js: Added.
+ (clobber):
+ (foo):
+ * tests/stress/sinkable-new-object-in-loop.js: Added.
+ (foo):
+
</ins><span class="cx"> 2015-07-13 Daniel Bates <dabates@apple.com>
</span><span class="cx">
</span><span class="cx"> Cleanup: Avoid extraneous increment and decrement of reference count of ScriptArguments in ConsoleClient
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -325,7 +325,6 @@
</span><span class="cx">
</span><span class="cx"> StructureSet* addStructureSet(const StructureSet& structureSet)
</span><span class="cx"> {
</span><del>- ASSERT(structureSet.size());
</del><span class="cx"> m_structureSet.append(structureSet);
</span><span class="cx"> return &m_structureSet.last();
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLazyNodecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLazyNode.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLazyNode.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGLazyNode.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -38,8 +38,7 @@
</span><span class="cx"> if (isNode())
</span><span class="cx"> out.print("LazyNode:@", asNode()->index());
</span><span class="cx"> else
</span><del>- out.print("LazyNode:FrozenValue:", Graph::opName(op()), ", ", pointerDump(asValue()));
- out.print(")");
</del><ins>+ out.print("LazyNode:FrozenValue(", Graph::opName(op()), ", ", pointerDump(asValue()), ")");
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNode.h (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNode.h 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGNode.h 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -1293,13 +1293,7 @@
</span><span class="cx"> FrozenValue* cellOperand()
</span><span class="cx"> {
</span><span class="cx"> ASSERT(hasCellOperand());
</span><del>- switch (op()) {
- case MaterializeCreateActivation:
- return reinterpret_cast<FrozenValue*>(m_opInfo2);
- default:
- return reinterpret_cast<FrozenValue*>(m_opInfo);
- }
- RELEASE_ASSERT_NOT_REACHED();
</del><ins>+ return reinterpret_cast<FrozenValue*>(m_opInfo);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T>
</span><span class="lines">@@ -1359,6 +1353,7 @@
</span><span class="cx"> switch (op()) {
</span><span class="cx"> case CheckStructure:
</span><span class="cx"> case CheckStructureImmediate:
</span><ins>+ case MaterializeNewObject:
</ins><span class="cx"> return true;
</span><span class="cx"> default:
</span><span class="cx"> return false;
</span><span class="lines">@@ -1444,7 +1439,7 @@
</span><span class="cx"> ObjectMaterializationData& objectMaterializationData()
</span><span class="cx"> {
</span><span class="cx"> ASSERT(hasObjectMaterializationData());
</span><del>- return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo);
</del><ins>+ return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo2);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool isObjectAllocation()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSRAvailabilityAnalysisPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -32,7 +32,6 @@
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><span class="cx"> #include "DFGPhase.h"
</span><del>-#include "DFGPromoteHeapAccess.h"
</del><span class="cx"> #include "JSCInlines.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -20,7 +20,7 @@
</span><span class="cx"> * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
</span><span class="cx"> * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
</span><span class="cx"> * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
</span><del>- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
</del><ins>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
</ins><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #include "config.h"
</span><span class="lines">@@ -28,77 +28,687 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-#include "DFGAbstractHeap.h"
</del><span class="cx"> #include "DFGBlockMapInlines.h"
</span><del>-#include "DFGClobberize.h"
</del><span class="cx"> #include "DFGCombinedLiveness.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><del>-#include "DFGInsertOSRHintsForUpdate.h"
</del><span class="cx"> #include "DFGInsertionSet.h"
</span><ins>+#include "DFGLazyNode.h"
</ins><span class="cx"> #include "DFGLivenessAnalysisPhase.h"
</span><span class="cx"> #include "DFGOSRAvailabilityAnalysisPhase.h"
</span><span class="cx"> #include "DFGPhase.h"
</span><del>-#include "DFGPromoteHeapAccess.h"
</del><ins>+#include "DFGPromotedHeapLocation.h"
</ins><span class="cx"> #include "DFGSSACalculator.h"
</span><span class="cx"> #include "DFGValidate.h"
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="cx">
</span><ins>+#include <list>
+
</ins><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><del>-static bool verbose = false;
</del><ins>+namespace {
</ins><span class="cx">
</span><ins>+bool verbose = false;
+
+// In order to sink object cycles, we use a points-to analysis coupled
+// with an escape analysis. This analysis is actually similar to an
+// abstract interpreter focused on local allocations and ignoring
+// everything else.
+//
+// We represent the local heap using two mappings:
+//
+// - A set of the local allocations present in the function, where
+// each of those have a further mapping from
+// PromotedLocationDescriptor to local allocations they must point
+// to.
+//
+// - A "pointer" mapping from nodes to local allocations, if they must
+// be equal to said local allocation and are currently live. This
+// can be because the node is the actual node that created the
+// allocation, or any other node that must currently point to it -
+// we don't make a difference.
+//
+// The following graph is a motivation for why we separate allocations
+// from pointers:
+//
+// Block #0
+// 0: NewObject({})
+// 1: NewObject({})
+// -: PutByOffset(@0, @1, x)
+// -: PutStructure(@0, {x:0})
+// 2: GetByOffset(@0, x)
+// -: Jump(#1)
+//
+// Block #1
+// -: Return(@2)
+//
+// Here, we need to remember in block #1 that @2 points to a local
+// allocation with appropriate fields and structures information
+// (because we should be able to place a materialization on top of
+// block #1 here), even though @1 is dead. We *could* just keep @1
+// artificially alive here, but there is no real reason to do it:
+// after all, by the end of block #0, @1 and @2 should be completely
+// interchangeable, and there is no reason for us to artificially make
+// @1 more important.
+//
+// An important point to consider to understand this separation is
+// that we should think of the local heap as follow: we have a
+// bunch of nodes that are pointers to "allocations" that live
+// someplace on the heap, and those allocations can have pointers in
+// between themselves as well. We shouldn't care about whatever
+// names we give to the allocations ; what matters when
+// comparing/merging two heaps is the isomorphism/comparison between
+// the allocation graphs as seen by the nodes.
+//
+// For instance, in the following graph:
+//
+// Block #0
+// 0: NewObject({})
+// -: Branch(#1, #2)
+//
+// Block #1
+// 1: NewObject({})
+// -: PutByOffset(@0, @1, x)
+// -: PutStructure(@0, {x:0})
+// -: Jump(#3)
+//
+// Block #2
+// 2: NewObject({})
+// -: PutByOffset(@2, undefined, x)
+// -: PutStructure(@2, {x:0})
+// -: PutByOffset(@0, @2, x)
+// -: PutStructure(@0, {x:0})
+// -: Jump(#3)
+//
+// Block #3
+// -: Return(@0)
+//
+// we should think of the heaps at tail of blocks #1 and #2 as being
+// exactly the same, even though one has @0.x pointing to @1 and the
+// other has @0.x pointing to @2, because in essence this should not
+// be different from the graph where we hoisted @1 and @2 into a
+// single allocation in block #0. We currently will not handle this
+// case, because we merge allocations based on the node they are
+// coming from, but this is only a technicality for the sake of
+// simplicity that shouldn't hide the deeper idea outlined here.
+
+class Allocation {
+public:
+ // We use Escaped as a special allocation kind because when we
+ // decide to sink an allocation, we still need to keep track of it
+ // once it is escaped if it still has pointers to it in order to
+ // replace any use of those pointers by the corresponding
+ // materialization
+ enum class Kind { Escaped, Object, Activation, Function };
+
+ explicit Allocation(Node* identifier = nullptr, Kind kind = Kind::Escaped)
+ : m_identifier(identifier)
+ , m_kind(kind)
+ {
+ }
+
+
+ const HashMap<PromotedLocationDescriptor, Node*>& fields() const
+ {
+ return m_fields;
+ }
+
+ Node* get(PromotedLocationDescriptor descriptor)
+ {
+ return m_fields.get(descriptor);
+ }
+
+ Allocation& set(PromotedLocationDescriptor descriptor, Node* value)
+ {
+ // Pointing to anything else than an unescaped local
+ // allocation is represented by simply not having the
+ // field
+ if (value)
+ m_fields.set(descriptor, value);
+ else
+ m_fields.remove(descriptor);
+ return *this;
+ }
+
+ void remove(PromotedLocationDescriptor descriptor)
+ {
+ set(descriptor, nullptr);
+ }
+
+ bool hasStructures() const
+ {
+ switch (kind()) {
+ case Kind::Object:
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ Allocation& setStructures(const StructureSet& structures)
+ {
+ ASSERT(hasStructures() && !structures.isEmpty());
+ m_structures = structures;
+ return *this;
+ }
+
+ Allocation& mergeStructures(const StructureSet& structures)
+ {
+ ASSERT(hasStructures() || structures.isEmpty());
+ m_structures.merge(structures);
+ return *this;
+ }
+
+ Allocation& filterStructures(const StructureSet& structures)
+ {
+ ASSERT(hasStructures());
+ m_structures.filter(structures);
+ return *this;
+ }
+
+ const StructureSet& structures() const
+ {
+ return m_structures;
+ }
+
+ Node* identifier() const { return m_identifier; }
+
+ Kind kind() const { return m_kind; }
+
+ bool isEscapedAllocation() const
+ {
+ return kind() == Kind::Escaped;
+ }
+
+ bool isObjectAllocation() const
+ {
+ return m_kind == Kind::Object;
+ }
+
+ bool isActivationAllocation() const
+ {
+ return m_kind == Kind::Activation;
+ }
+
+ bool isFunctionAllocation() const
+ {
+ return m_kind == Kind::Function;
+ }
+
+ bool operator==(const Allocation& other) const
+ {
+ return m_identifier == other.m_identifier
+ && m_kind == other.m_kind
+ && m_fields == other.m_fields
+ && m_structures == other.m_structures;
+ }
+
+ bool operator!=(const Allocation& other) const
+ {
+ return !(*this == other);
+ }
+
+ void dump(PrintStream& out) const
+ {
+ dumpInContext(out, nullptr);
+ }
+
+ void dumpInContext(PrintStream& out, DumpContext* context) const
+ {
+ switch (m_kind) {
+ case Kind::Escaped:
+ out.print("Escaped");
+ break;
+
+ case Kind::Object:
+ out.print("Object");
+ break;
+
+ case Kind::Function:
+ out.print("Function");
+ break;
+
+ case Kind::Activation:
+ out.print("Activation");
+ break;
+ }
+ out.print("Allocation(");
+ if (!m_structures.isEmpty())
+ out.print(inContext(m_structures, context));
+ if (!m_fields.isEmpty()) {
+ if (!m_structures.isEmpty())
+ out.print(", ");
+ out.print(mapDump(m_fields, " => #", ", "));
+ }
+ out.print(")");
+ }
+
+private:
+ Node* m_identifier; // This is the actual node that created the allocation
+ Kind m_kind;
+ HashMap<PromotedLocationDescriptor, Node*> m_fields;
+ StructureSet m_structures;
+};
+
+class LocalHeap {
+public:
+ Allocation& newAllocation(Node* node, Allocation::Kind kind)
+ {
+ ASSERT(!m_pointers.contains(node) && !isAllocation(node));
+ m_pointers.add(node, node);
+ return m_allocations.set(node, Allocation(node, kind)).iterator->value;
+ }
+
+ bool isAllocation(Node* identifier) const
+ {
+ return m_allocations.contains(identifier);
+ }
+
+ // Note that this is fundamentally different from
+ // onlyLocalAllocation() below. getAllocation() takes as argument
+ // a node-as-identifier, that is, an allocation node. This
+ // allocation node doesn't have to be alive; it may only be
+ // pointed to by other nodes or allocation fields.
+ // For instance, in the following graph:
+ //
+ // Block #0
+ // 0: NewObject({})
+ // 1: NewObject({})
+ // -: PutByOffset(@0, @1, x)
+ // -: PutStructure(@0, {x:0})
+ // 2: GetByOffset(@0, x)
+ // -: Jump(#1)
+ //
+ // Block #1
+ // -: Return(@2)
+ //
+ // At head of block #1, the only reachable allocation is #@1,
+ // which can be reached through node @2. Thus, getAllocation(#@1)
+ // contains the appropriate metadata for this allocation, but
+ // onlyLocalAllocation(@1) is null, as @1 is no longer a pointer
+ // to #@1 (since it is dead). Conversely, onlyLocalAllocation(@2)
+ // is the same as getAllocation(#@1), while getAllocation(#@2)
+ // does not make sense since @2 is not an allocation node.
+ //
+ // This is meant to be used when the node is already known to be
+ // an identifier (i.e. an allocation) - probably because it was
+ // found as value of a field or pointer in the current heap, or
+ // was the result of a call to follow(). In any other cases (such
+ // as when doing anything while traversing the graph), the
+ // appropriate function to call is probably onlyLocalAllocation.
+ Allocation& getAllocation(Node* identifier)
+ {
+ auto iter = m_allocations.find(identifier);
+ ASSERT(iter != m_allocations.end());
+ return iter->value;
+ }
+
+ void newPointer(Node* node, Node* identifier)
+ {
+ ASSERT(!m_allocations.contains(node) && !m_pointers.contains(node));
+ ASSERT(isAllocation(identifier));
+ m_pointers.add(node, identifier);
+ }
+
+ // follow solves the points-to problem. Given a live node, which
+ // may be either an allocation itself or a heap read (e.g. a
+ // GetByOffset node), it returns the corresponding allocation
+ // node, if there is one. If the argument node is neither an
+ // allocation or a heap read, or may point to different nodes,
+ // nullptr will be returned. Note that a node that points to
+ // different nodes can never point to an unescaped local
+ // allocation.
+ Node* follow(Node* node) const
+ {
+ auto iter = m_pointers.find(node);
+ ASSERT(iter == m_pointers.end() || m_allocations.contains(iter->value));
+ return iter == m_pointers.end() ? nullptr : iter->value;
+ }
+
+ Node* follow(PromotedHeapLocation location) const
+ {
+ const Allocation& base = m_allocations.find(location.base())->value;
+ auto iter = base.fields().find(location.descriptor());
+
+ if (iter == base.fields().end())
+ return nullptr;
+
+ return iter->value;
+ }
+
+ // onlyLocalAllocation find the corresponding allocation metadata
+ // for any live node. onlyLocalAllocation(node) is essentially
+ // getAllocation(follow(node)), with appropriate null handling.
+ Allocation* onlyLocalAllocation(Node* node)
+ {
+ Node* identifier = follow(node);
+ if (!identifier)
+ return nullptr;
+
+ return &getAllocation(identifier);
+ }
+
+ Allocation* onlyLocalAllocation(PromotedHeapLocation location)
+ {
+ Node* identifier = follow(location);
+ if (!identifier)
+ return nullptr;
+
+ return &getAllocation(identifier);
+ }
+
+ // This allows us to store the escapees only when necessary. If
+ // set, the current escapees can be retrieved at any time using
+ // takeEscapees(), which will clear the cached set of escapees;
+ // otherwise the heap won't remember escaping allocations.
+ void setWantEscapees()
+ {
+ m_wantEscapees = true;
+ }
+
+ HashMap<Node*, Allocation> takeEscapees()
+ {
+ return WTF::move(m_escapees);
+ }
+
+ void escape(Node* node)
+ {
+ Node* identifier = follow(node);
+ if (!identifier)
+ return;
+
+ escapeAllocation(identifier);
+ }
+
+ void merge(const LocalHeap& other)
+ {
+ assertIsValid();
+ other.assertIsValid();
+ ASSERT(!m_wantEscapees);
+
+ if (!reached()) {
+ ASSERT(other.reached());
+ *this = other;
+ return;
+ }
+
+ HashSet<Node*> toEscape;
+
+ for (auto& allocationEntry : other.m_allocations)
+ m_allocations.add(allocationEntry.key, allocationEntry.value);
+ for (auto& allocationEntry : m_allocations) {
+ auto allocationIter = other.m_allocations.find(allocationEntry.key);
+
+ // If we have it and they don't, it died for them but we
+ // are keeping it alive from another field somewhere.
+ // There is nothing to do - we will be escaped
+ // automatically when we handle that other field.
+ // This will also happen for allocation that we have and
+ // they don't, and all of those will get pruned.
+ if (allocationIter == other.m_allocations.end())
+ continue;
+
+ if (allocationEntry.value.kind() != allocationIter->value.kind()) {
+ toEscape.add(allocationEntry.key);
+ for (const auto& fieldEntry : allocationIter->value.fields())
+ toEscape.add(fieldEntry.value);
+ } else {
+ mergePointerSets(
+ allocationEntry.value.fields(), allocationIter->value.fields(),
+ [&] (Node* identifier) {
+ toEscape.add(identifier);
+ },
+ [&] (PromotedLocationDescriptor field) {
+ allocationEntry.value.remove(field);
+ });
+ allocationEntry.value.mergeStructures(allocationIter->value.structures());
+ }
+ }
+
+ mergePointerSets(m_pointers, other.m_pointers,
+ [&] (Node* identifier) {
+ toEscape.add(identifier);
+ },
+ [&] (Node* field) {
+ m_pointers.remove(field);
+ });
+
+ for (Node* identifier : toEscape)
+ escapeAllocation(identifier);
+
+ if (!ASSERT_DISABLED) {
+ for (const auto& entry : m_allocations)
+ ASSERT_UNUSED(entry, entry.value.isEscapedAllocation() || other.m_allocations.contains(entry.key));
+ }
+
+ // If there is no remaining pointer to an allocation, we can
+ // remove it. This should only happen for escaped allocations,
+ // because we only merge liveness-pruned heaps in the first
+ // place.
+ prune();
+
+ assertIsValid();
+ }
+
+ void pruneByLiveness(const HashSet<Node*>& live)
+ {
+ Vector<Node*> toRemove;
+ for (const auto& entry : m_pointers) {
+ if (!live.contains(entry.key))
+ toRemove.append(entry.key);
+ }
+ for (Node* node : toRemove)
+ m_pointers.remove(node);
+
+ prune();
+ }
+
+ void assertIsValid() const
+ {
+ if (ASSERT_DISABLED)
+ return;
+
+ // Pointers should point to an actual allocation
+ for (const auto& entry : m_pointers) {
+ ASSERT_UNUSED(entry, entry.value);
+ ASSERT(m_allocations.contains(entry.value));
+ }
+
+ for (const auto& allocationEntry : m_allocations) {
+ // Fields should point to an actual allocation
+ for (const auto& fieldEntry : allocationEntry.value.fields()) {
+ ASSERT_UNUSED(fieldEntry, fieldEntry.value);
+ ASSERT(m_allocations.contains(fieldEntry.value));
+ }
+ }
+ }
+
+ bool operator==(const LocalHeap& other) const
+ {
+ assertIsValid();
+ other.assertIsValid();
+ return m_allocations == other.m_allocations
+ && m_pointers == other.m_pointers;
+ }
+
+ bool operator!=(const LocalHeap& other) const
+ {
+ return !(*this == other);
+ }
+
+ const HashMap<Node*, Allocation> allocations() const
+ {
+ return m_allocations;
+ }
+
+ const HashMap<Node*, Node*> pointers() const
+ {
+ return m_pointers;
+ }
+
+ void dump(PrintStream& out) const
+ {
+ out.print(" Allocations:\n");
+ for (const auto& entry : m_allocations)
+ out.print(" #", entry.key, ": ", entry.value, "\n");
+ out.print(" Pointers:\n");
+ for (const auto& entry : m_pointers)
+ out.print(" ", entry.key, " => #", entry.value, "\n");
+ }
+
+ bool reached() const
+ {
+ return m_reached;
+ }
+
+ void setReached()
+ {
+ m_reached = true;
+ }
+
+private:
+ // When we merge two heaps, we escape all fields of allocations,
+ // unless they point to the same thing in both heaps.
+ // The reason for this is that it allows us not to do extra work
+ // for diamond graphs where we would otherwise have to check
+ // whether we have a single definition or not, which would be
+ // cumbersome.
+ //
+ // Note that we should try to unify nodes even when they are not
+ // from the same allocation; for instance we should be able to
+ // completely eliminate all allocations from the following graph:
+ //
+ // Block #0
+ // 0: NewObject({})
+ // -: Branch(#1, #2)
+ //
+ // Block #1
+ // 1: NewObject({})
+ // -: PutByOffset(@1, "left", val)
+ // -: PutStructure(@1, {val:0})
+ // -: PutByOffset(@0, @1, x)
+ // -: PutStructure(@0, {x:0})
+ // -: Jump(#3)
+ //
+ // Block #2
+ // 2: NewObject({})
+ // -: PutByOffset(@2, "right", val)
+ // -: PutStructure(@2, {val:0})
+ // -: PutByOffset(@0, @2, x)
+ // -: PutStructure(@0, {x:0})
+ // -: Jump(#3)
+ //
+ // Block #3:
+ // 3: GetByOffset(@0, x)
+ // 4: GetByOffset(@3, val)
+ // -: Return(@4)
+ template<typename Key, typename EscapeFunctor, typename RemoveFunctor>
+ void mergePointerSets(
+ const HashMap<Key, Node*>& my, const HashMap<Key, Node*>& their,
+ const EscapeFunctor& escape, const RemoveFunctor& remove)
+ {
+ Vector<Key> toRemove;
+ for (const auto& entry : my) {
+ auto iter = their.find(entry.key);
+ if (iter == their.end()) {
+ toRemove.append(entry.key);
+ escape(entry.value);
+ } else if (iter->value != entry.value) {
+ toRemove.append(entry.key);
+ escape(entry.value);
+ escape(iter->value);
+ }
+ }
+ for (const auto& entry : their) {
+ if (my.contains(entry.key))
+ continue;
+ escape(entry.value);
+ }
+ for (Key key : toRemove)
+ remove(key);
+ }
+
+ void escapeAllocation(Node* identifier)
+ {
+ Allocation& allocation = getAllocation(identifier);
+ if (allocation.isEscapedAllocation())
+ return;
+
+ Allocation unescaped = WTF::move(allocation);
+ allocation = Allocation(unescaped.identifier(), Allocation::Kind::Escaped);
+
+ for (const auto& entry : unescaped.fields())
+ escapeAllocation(entry.value);
+
+ if (m_wantEscapees)
+ m_escapees.add(unescaped.identifier(), WTF::move(unescaped));
+ }
+
+ void prune()
+ {
+ HashSet<Node*> reachable;
+ for (const auto& entry : m_pointers)
+ reachable.add(entry.value);
+
+ // Repeatedly mark as reachable allocations in fields of other
+ // reachable allocations
+ {
+ Vector<Node*> worklist;
+ worklist.appendRange(reachable.begin(), reachable.end());
+
+ while (!worklist.isEmpty()) {
+ Node* identifier = worklist.takeLast();
+ Allocation& allocation = m_allocations.find(identifier)->value;
+ for (const auto& entry : allocation.fields()) {
+ if (reachable.add(entry.value).isNewEntry)
+ worklist.append(entry.value);
+ }
+ }
+ }
+
+ // Remove unreachable allocations
+ {
+ Vector<Node*> toRemove;
+ for (const auto& entry : m_allocations) {
+ if (!reachable.contains(entry.key))
+ toRemove.append(entry.key);
+ }
+ for (Node* identifier : toRemove)
+ m_allocations.remove(identifier);
+ }
+ }
+
+ bool m_reached = false;
+ HashMap<Node*, Node*> m_pointers;
+ HashMap<Node*, Allocation> m_allocations;
+
+ bool m_wantEscapees = false;
+ HashMap<Node*, Allocation> m_escapees;
+};
+
</ins><span class="cx"> class ObjectAllocationSinkingPhase : public Phase {
</span><span class="cx"> public:
</span><span class="cx"> ObjectAllocationSinkingPhase(Graph& graph)
</span><del>- : Phase(graph, "object allocation sinking")
- , m_ssaCalculator(graph)
</del><ins>+ : Phase(graph, "object allocation elimination")
+ , m_pointerSSA(graph)
+ , m_allocationSSA(graph)
</ins><span class="cx"> , m_insertionSet(graph)
</span><span class="cx"> {
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> bool run()
</span><span class="cx"> {
</span><ins>+ ASSERT(m_graph.m_form == SSA);
</ins><span class="cx"> ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
</span><del>-
- m_graph.m_dominators.computeIfNecessary(m_graph);
-
- // Logically we wish to consider every NewObject and sink it. However it's probably not
- // profitable to sink a NewObject that will always escape. So, first we do a very simple
- // forward flow analysis that determines the set of NewObject nodes that have any chance
- // of benefiting from object allocation sinking. Then we fixpoint the following rules:
- //
- // - For each NewObject, we turn the original NewObject into a PhantomNewObject and then
- // we insert MaterializeNewObject just before those escaping sites that come before any
- // other escaping sites - that is, there is no path between the allocation and those sites
- // that would see any other escape. Note that Upsilons constitute escaping sites. Then we
- // insert additional MaterializeNewObject nodes on Upsilons that feed into Phis that mix
- // materializations and the original PhantomNewObject. We then turn each PutByOffset over a
- // PhantomNewObject into a PutHint.
- //
- // - We perform the same optimization for MaterializeNewObject. This allows us to cover
- // cases where we had MaterializeNewObject flowing into a PutHint.
- //
- // We could also add this rule:
- //
- // - If all of the Upsilons of a Phi have a MaterializeNewObject that isn't used by anyone
- // else, then replace the Phi with the MaterializeNewObject.
- //
- // FIXME: Implement this. Note that this totally doable but it requires some gnarly
- // code, and to be effective the pruner needs to be aware of it. Currently any Upsilon
- // is considered to be an escape even by the pruner, so it's unlikely that we'll see
- // many cases of Phi over Materializations.
- // https://bugs.webkit.org/show_bug.cgi?id=136927
-
</del><ins>+
</ins><span class="cx"> if (!performSinking())
</span><span class="cx"> return false;
</span><del>-
- while (performSinking()) { }
-
</del><ins>+
</ins><span class="cx"> if (verbose) {
</span><del>- dataLog("Graph after sinking:\n");
</del><ins>+ dataLog("Graph after elimination:\n");
</ins><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -106,950 +716,1207 @@
</span><span class="cx"> bool performSinking()
</span><span class="cx"> {
</span><span class="cx"> m_graph.computeRefCounts();
</span><ins>+ m_graph.initializeNodeOwners();
</ins><span class="cx"> performLivenessAnalysis(m_graph);
</span><span class="cx"> performOSRAvailabilityAnalysis(m_graph);
</span><span class="cx"> m_combinedLiveness = CombinedLiveness(m_graph);
</span><del>-
</del><ins>+
</ins><span class="cx"> CString graphBeforeSinking;
</span><span class="cx"> if (Options::verboseValidationFailure() && Options::validateGraphAtEachPhase()) {
</span><span class="cx"> StringPrintStream out;
</span><span class="cx"> m_graph.dump(out);
</span><span class="cx"> graphBeforeSinking = out.toCString();
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> if (verbose) {
</span><del>- dataLog("Graph before sinking:\n");
</del><ins>+ dataLog("Graph before elimination:\n");
</ins><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><del>-
- determineMaterializationPoints();
- if (m_sinkCandidates.isEmpty())
</del><ins>+
+ performAnalysis();
+
+ if (!determineSinkCandidates())
</ins><span class="cx"> return false;
</span><del>-
- // At this point we are committed to sinking the sinking candidates.
- placeMaterializationPoints();
- lowerNonReadingOperationsOnPhantomAllocations();
- promoteSunkenFields();
-
</del><ins>+
+ if (verbose) {
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ dataLog("Heap at head of ", *block, ": \n", m_heapAtHead[block]);
+ dataLog("Heap at tail of ", *block, ": \n", m_heapAtTail[block]);
+ }
+ }
+
+ promoteLocalHeap();
+
</ins><span class="cx"> if (Options::validateGraphAtEachPhase())
</span><span class="cx"> validate(m_graph, DumpGraph, graphBeforeSinking);
</span><del>-
- if (verbose)
- dataLog("Sinking iteration changed the graph.\n");
</del><span class="cx"> return true;
</span><span class="cx"> }
</span><del>-
- void determineMaterializationPoints()
</del><ins>+
+ void performAnalysis()
</ins><span class="cx"> {
</span><del>- // The premise of this pass is that if there exists a point in the program where some
- // path from a phantom allocation site to that point causes materialization, then *all*
- // paths cause materialization. This should mean that there are never any redundant
- // materializations.
-
- m_sinkCandidates.clear();
- m_materializationToEscapee.clear();
- m_materializationSiteToMaterializations.clear();
-
- BlockMap<HashMap<Node*, bool>> materializedAtHead(m_graph);
- BlockMap<HashMap<Node*, bool>> materializedAtTail(m_graph);
-
</del><ins>+ m_heapAtHead = BlockMap<LocalHeap>(m_graph);
+ m_heapAtTail = BlockMap<LocalHeap>(m_graph);
+
</ins><span class="cx"> bool changed;
</span><span class="cx"> do {
</span><span class="cx"> if (verbose)
</span><del>- dataLog("Doing iteration of materialization point placement.\n");
</del><ins>+ dataLog("Doing iteration of escape analysis.\n");
</ins><span class="cx"> changed = false;
</span><del>- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- HashMap<Node*, bool> materialized = materializedAtHead[block];
- if (verbose)
- dataLog(" Looking at block ", pointerDump(block), "\n");
</del><ins>+
+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+ m_heapAtHead[block].setReached();
+ m_heap = m_heapAtHead[block];
+
</ins><span class="cx"> for (Node* node : *block) {
</span><span class="cx"> handleNode(
</span><span class="cx"> node,
</span><del>- [&] () {
- materialized.add(node, false);
- },
- [&] (Node* escapee) {
- auto iter = materialized.find(escapee);
- if (iter != materialized.end()) {
- if (verbose)
- dataLog(" ", escapee, " escapes at ", node, "\n");
- iter->value = true;
- }
</del><ins>+ [] (PromotedHeapLocation, LazyNode) { },
+ [&] (PromotedHeapLocation) -> Node* {
+ return nullptr;
</ins><span class="cx"> });
</span><span class="cx"> }
</span><del>-
- if (verbose)
- dataLog(" Materialized at tail of ", pointerDump(block), ": ", mapDump(materialized), "\n");
-
- if (materialized == materializedAtTail[block])
</del><ins>+
+ if (m_heap == m_heapAtTail[block])
</ins><span class="cx"> continue;
</span><del>-
- materializedAtTail[block] = materialized;
</del><ins>+
+ m_heapAtTail[block] = m_heap;
</ins><span class="cx"> changed = true;
</span><del>-
- // Only propagate things to our successors if they are alive in all successors.
- // So, we prune materialized-at-tail to only include things that are live.
- Vector<Node*> toRemove;
- for (auto pair : materialized) {
- if (!m_combinedLiveness.liveAtTail[block].contains(pair.key))
- toRemove.append(pair.key);
</del><ins>+
+ m_heap.assertIsValid();
+
+ // We keep only pointers that are live, and only
+ // allocations that are either live, pointed to by a
+ // live pointer, or (recursively) stored in a field of
+ // a live allocation.
+ //
+ // This means we can accidentaly leak non-dominating
+ // nodes into the successor. However, due to the
+ // non-dominance property, we are guaranteed that the
+ // successor has at least one predecessor that is not
+ // dominated either: this means any reference to a
+ // non-dominating allocation in the successor will
+ // trigger an escape and get pruned during the merge.
+ m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
+
+ for (BasicBlock* successorBlock : block->successors())
+ m_heapAtHead[successorBlock].merge(m_heap);
+ }
+ } while (changed);
+ }
+
+ template<typename WriteFunctor, typename ResolveFunctor>
+ void handleNode(
+ Node* node,
+ const WriteFunctor& heapWrite,
+ const ResolveFunctor& heapResolve)
+ {
+ m_heap.assertIsValid();
+ ASSERT(m_heap.takeEscapees().isEmpty());
+
+ Allocation* target = nullptr;
+ HashMap<PromotedLocationDescriptor, LazyNode> writes;
+ PromotedLocationDescriptor exactRead;
+
+ switch (node->op()) {
+ case NewObject:
+ target = &m_heap.newAllocation(node, Allocation::Kind::Object);
+ target->setStructures(node->structure());
+ writes.add(
+ StructurePLoc, LazyNode(m_graph.freeze(node->structure())));
+ break;
+
+ case MaterializeNewObject: {
+ target = &m_heap.newAllocation(node, Allocation::Kind::Object);
+ target->setStructures(node->structureSet());
+ writes.add(
+ StructurePLoc, LazyNode(m_graph.varArgChild(node, 0).node()));
+ for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
+ writes.add(
+ PromotedLocationDescriptor(
+ NamedPropertyPLoc,
+ node->objectMaterializationData().m_properties[i].m_identifierNumber),
+ LazyNode(m_graph.varArgChild(node, i + 1).node()));
+ }
+ break;
+ }
+
+ case NewFunction: {
+ if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid()) {
+ m_heap.escape(node->child1().node());
+ break;
+ }
+ target = &m_heap.newAllocation(node, Allocation::Kind::Function);
+ writes.add(FunctionExecutablePLoc, LazyNode(node->cellOperand()));
+ writes.add(FunctionActivationPLoc, LazyNode(node->child1().node()));
+ break;
+ }
+
+ case CreateActivation: {
+ if (node->castOperand<SymbolTable*>()->singletonScope()->isStillValid()) {
+ m_heap.escape(node->child1().node());
+ break;
+ }
+ target = &m_heap.newAllocation(node, Allocation::Kind::Activation);
+ writes.add(ActivationSymbolTablePLoc, LazyNode(node->cellOperand()));
+ writes.add(ActivationScopePLoc, LazyNode(node->child1().node()));
+ {
+ SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
+ ConcurrentJITLocker locker(symbolTable->m_lock);
+ LazyNode undefined(m_graph.freeze(jsUndefined()));
+ for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
+ writes.add(
+ PromotedLocationDescriptor(ClosureVarPLoc, iter->value.scopeOffset().offset()),
+ undefined);
</ins><span class="cx"> }
</span><del>- for (Node* key : toRemove)
- materialized.remove(key);
-
- for (BasicBlock* successorBlock : block->successors()) {
- for (auto pair : materialized) {
- materializedAtHead[successorBlock].add(
- pair.key, false).iterator->value |= pair.value;
- }
- }
</del><span class="cx"> }
</span><del>- } while (changed);
-
- // Determine the sink candidates. Broadly, a sink candidate is a node that handleNode()
- // believes is sinkable, and one of the following is true:
</del><ins>+ break;
+ }
+
+ case MaterializeCreateActivation: {
+ // We have sunk this once already - there is no way the
+ // watchpoint is still valid.
+ ASSERT(!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid());
+ target = &m_heap.newAllocation(node, Allocation::Kind::Activation);
+ writes.add(ActivationSymbolTablePLoc, LazyNode(m_graph.varArgChild(node, 0).node()));
+ writes.add(ActivationScopePLoc, LazyNode(m_graph.varArgChild(node, 1).node()));
+ for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
+ writes.add(
+ PromotedLocationDescriptor(
+ ClosureVarPLoc,
+ node->objectMaterializationData().m_properties[i].m_identifierNumber),
+ LazyNode(m_graph.varArgChild(node, i + 2).node()));
+ }
+ break;
+ }
+
+ case PutStructure:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isObjectAllocation()) {
+ writes.add(StructurePLoc, LazyNode(m_graph.freeze(JSValue(node->transition()->next))));
+ target->setStructures(node->transition()->next);
+ } else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case CheckStructure: {
+ Allocation* allocation = m_heap.onlyLocalAllocation(node->child1().node());
+ if (allocation && allocation->isObjectAllocation()) {
+ allocation->filterStructures(node->structureSet());
+ if (Node* value = heapResolve(PromotedHeapLocation(allocation->identifier(), StructurePLoc)))
+ node->convertToCheckStructureImmediate(value);
+ } else
+ m_heap.escape(node->child1().node());
+ break;
+ }
+
+ case GetByOffset:
+ case GetGetterSetterByOffset:
+ target = m_heap.onlyLocalAllocation(node->child2().node());
+ if (target && target->isObjectAllocation()) {
+ unsigned identifierNumber = node->storageAccessData().identifierNumber;
+ exactRead = PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber);
+ } else {
+ m_heap.escape(node->child1().node());
+ m_heap.escape(node->child2().node());
+ }
+ break;
+
+ case MultiGetByOffset:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isObjectAllocation()) {
+ unsigned identifierNumber = node->multiGetByOffsetData().identifierNumber;
+ exactRead = PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber);
+ } else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case PutByOffset:
+ target = m_heap.onlyLocalAllocation(node->child2().node());
+ if (target && target->isObjectAllocation()) {
+ unsigned identifierNumber = node->storageAccessData().identifierNumber;
+ writes.add(
+ PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber),
+ LazyNode(node->child3().node()));
+ } else {
+ m_heap.escape(node->child1().node());
+ m_heap.escape(node->child2().node());
+ m_heap.escape(node->child3().node());
+ }
+ break;
+
+ case GetClosureVar:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isActivationAllocation()) {
+ exactRead =
+ PromotedLocationDescriptor(ClosureVarPLoc, node->scopeOffset().offset());
+ } else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case PutClosureVar:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isActivationAllocation()) {
+ writes.add(
+ PromotedLocationDescriptor(ClosureVarPLoc, node->scopeOffset().offset()),
+ LazyNode(node->child2().node()));
+ } else {
+ m_heap.escape(node->child1().node());
+ m_heap.escape(node->child2().node());
+ }
+ break;
+
+ case SkipScope:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isActivationAllocation())
+ exactRead = ActivationScopePLoc;
+ else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case GetExecutable:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isFunctionAllocation())
+ exactRead = FunctionExecutablePLoc;
+ else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case GetScope:
+ target = m_heap.onlyLocalAllocation(node->child1().node());
+ if (target && target->isFunctionAllocation())
+ exactRead = FunctionActivationPLoc;
+ else
+ m_heap.escape(node->child1().node());
+ break;
+
+ case Check:
+ m_graph.doToChildren(
+ node,
+ [&] (Edge edge) {
+ if (edge.willNotHaveCheck())
+ return;
+
+ if (alreadyChecked(edge.useKind(), SpecObject))
+ return;
+
+ m_heap.escape(edge.node());
+ });
+ break;
+
+ case MovHint:
+ case PutHint:
+ // Handled by OSR availability analysis
+ break;
+
+ default:
+ m_graph.doToChildren(
+ node,
+ [&] (Edge edge) {
+ m_heap.escape(edge.node());
+ });
+ break;
+ }
+
+ if (exactRead) {
+ ASSERT(target);
+ ASSERT(writes.isEmpty());
+ if (Node* value = heapResolve(PromotedHeapLocation(target->identifier(), exactRead))) {
+ ASSERT(!value->replacement());
+ node->replaceWith(value);
+ }
+ Node* identifier = target->get(exactRead);
+ if (identifier)
+ m_heap.newPointer(node, identifier);
+ }
+
+ for (auto entry : writes) {
+ ASSERT(target);
+ if (entry.value.isNode())
+ target->set(entry.key, m_heap.follow(entry.value.asNode()));
+ else
+ target->remove(entry.key);
+ heapWrite(PromotedHeapLocation(target->identifier(), entry.key), entry.value);
+ }
+
+ m_heap.assertIsValid();
+ }
+
+ bool determineSinkCandidates()
+ {
+ m_sinkCandidates.clear();
+ m_materializationToEscapee.clear();
+ m_materializationSiteToMaterializations.clear();
+ m_materializationSiteToRecoveries.clear();
+
+ // Logically we wish to consider every allocation and sink
+ // it. However, it is probably not profitable to sink an
+ // allocation that will always escape. So, we only sink an
+ // allocation if one of the following is true:
</ins><span class="cx"> //
</span><del>- // 1) There exists a basic block with only backward outgoing edges (or no outgoing edges)
- // in which the node wasn't materialized. This is meant to catch effectively-infinite
- // loops in which we don't need to have allocated the object.
</del><ins>+ // 1) There exists a basic block with only backwards outgoing
+ // edges (or no outgoing edges) in which the node wasn't
+ // materialized. This is meant to catch
+ // effectively-infinite loops in which we don't need to
+ // have allocated the object.
</ins><span class="cx"> //
</span><del>- // 2) There exists a basic block at the tail of which the node is not materialized and the
- // node is dead.
</del><ins>+ // 2) There exists a basic block at the tail of which the node
+ // is dead and not materialized.
</ins><span class="cx"> //
</span><del>- // 3) The sum of execution counts of the materializations is less than the sum of
- // execution counts of the original node.
</del><ins>+ // 3) The sum of execution counts of the materializations is
+ // less than the sum of execution counts of the original
+ // node.
</ins><span class="cx"> //
</span><span class="cx"> // We currently implement only rule #2.
</span><span class="cx"> // FIXME: Implement the two other rules.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=137073 (rule #1)
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=137074 (rule #3)
</span><del>-
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- for (auto pair : materializedAtTail[block]) {
- if (pair.value)
- continue; // It was materialized.
-
- if (m_combinedLiveness.liveAtTail[block].contains(pair.key))
- continue; // It might still get materialized in all of the successors.
-
- // We know that it died in this block and it wasn't materialized. That means that
- // if we sink this allocation, then *this* will be a path along which we never
- // have to allocate. Profit!
- m_sinkCandidates.add(pair.key);
- }
- }
-
- if (m_sinkCandidates.isEmpty())
- return;
-
- // A materialization edge exists at any point where a node escapes but hasn't been
- // materialized yet. We do this in two parts. First we find all of the nodes that cause
- // escaping to happen, where the escapee had not yet been materialized. This catches
- // everything but loops. We then catch loops - as well as weirder control flow constructs -
- // in a subsequent pass that looks at places in the CFG where an edge exists from a block
- // that hasn't materialized to a block that has. We insert the materialization along such an
- // edge, and we rely on the fact that critical edges were already broken so that we actually
- // either insert the materialization at the head of the successor or the tail of the
- // predecessor.
</del><span class="cx"> //
</span><del>- // FIXME: This can create duplicate allocations when we really only needed to perform one.
- // For example:
</del><ins>+ // However, these rules allow for a sunk object to be put into
+ // a non-sunk one, which we don't support. We could solve this
+ // by supporting PutHints on local allocations, making these
+ // objects only partially correct, and we would need to adapt
+ // the OSR availability analysis and OSR exit to handle
+ // this. This would be totally doable, but would create a
+ // super rare, and thus bug-prone, code path.
+ // So, instead, we need to implement one of the following
+ // closure rules:
</ins><span class="cx"> //
</span><del>- // var o = new Object();
- // if (rare) {
- // if (stuff)
- // call(o); // o escapes here.
- // return;
- // }
- // // o doesn't escape down here.
</del><ins>+ // 1) If we put a sink candidate into a local allocation that
+ // is not a sink candidate, change our minds and don't
+ // actually sink the sink candidate.
</ins><span class="cx"> //
</span><del>- // In this example, we would place a materialization point at call(o) and then we would find
- // ourselves having to insert another one at the implicit else case of that if statement
- // ('cause we've broken critical edges). We would instead really like to just have one
- // materialization point right at the top of the then case of "if (rare)". To do this, we can
- // find the LCA of the various materializations in the dom tree.
- // https://bugs.webkit.org/show_bug.cgi?id=137124
-
- // First pass: find intra-block materialization points.
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- HashSet<Node*> materialized;
- for (auto pair : materializedAtHead[block]) {
- if (pair.value && m_sinkCandidates.contains(pair.key))
- materialized.add(pair.key);
- }
-
- if (verbose)
- dataLog("Placing materialization points in ", pointerDump(block), " with materialization set ", listDump(materialized), "\n");
-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
-
</del><ins>+ // 2) If we put a sink candidate into a local allocation, that
+ // allocation becomes a sink candidate as well.
+ //
+ // We currently choose to implement closure rule #2.
+ HashMap<Node*, Vector<Node*>> dependencies;
+ bool hasUnescapedReads = false;
+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+ m_heap = m_heapAtHead[block];
+
+ for (Node* node : *block) {
</ins><span class="cx"> handleNode(
</span><span class="cx"> node,
</span><del>- [&] () { },
- [&] (Node* escapee) {
- if (verbose)
- dataLog("Seeing ", escapee, " escape at ", node, "\n");
-
- if (!m_sinkCandidates.contains(escapee)) {
- if (verbose)
- dataLog(" It's not a sink candidate.\n");
</del><ins>+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!value.isNode())
</ins><span class="cx"> return;
</span><del>- }
-
- if (!materialized.add(escapee).isNewEntry) {
- if (verbose)
- dataLog(" It's already materialized.\n");
- return;
- }
-
- createMaterialize(escapee, node);
</del><ins>+
+ Allocation* allocation = m_heap.onlyLocalAllocation(value.asNode());
+ if (allocation && !allocation->isEscapedAllocation())
+ dependencies.add(allocation->identifier(), Vector<Node*>()).iterator->value.append(location.base());
+ },
+ [&] (PromotedHeapLocation) -> Node* {
+ hasUnescapedReads = true;
+ return nullptr;
</ins><span class="cx"> });
</span><span class="cx"> }
</span><ins>+
+ // The sink candidates are initially the unescaped
+ // allocations dying at tail of blocks
+ HashSet<Node*> allocations;
+ for (const auto& entry : m_heap.allocations()) {
+ if (!entry.value.isEscapedAllocation())
+ allocations.add(entry.key);
+ }
+
+ m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
+
+ for (Node* identifier : allocations) {
+ if (!m_heap.isAllocation(identifier))
+ m_sinkCandidates.add(identifier);
+ }
</ins><span class="cx"> }
</span><del>-
- // Second pass: find CFG edge materialization points.
</del><ins>+
+ // Ensure that the set of sink candidates is closed for put operations
+ Vector<Node*> worklist;
+ worklist.appendRange(m_sinkCandidates.begin(), m_sinkCandidates.end());
+
+ while (!worklist.isEmpty()) {
+ for (Node* identifier : dependencies.get(worklist.takeLast())) {
+ if (m_sinkCandidates.add(identifier).isNewEntry)
+ worklist.append(identifier);
+ }
+ }
+
+ if (m_sinkCandidates.isEmpty())
+ return hasUnescapedReads;
+
+ if (verbose)
+ dataLog("Candidates: ", listDump(m_sinkCandidates), "\n");
+
+ // Create the materialization nodes
</ins><span class="cx"> for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
</span><del>- for (BasicBlock* successorBlock : block->successors()) {
- for (auto pair : materializedAtHead[successorBlock]) {
- Node* allocation = pair.key;
-
- // We only care if it is materialized in the successor.
- if (!pair.value)
</del><ins>+ m_heap = m_heapAtHead[block];
+ m_heap.setWantEscapees();
+
+ for (Node* node : *block) {
+ handleNode(
+ node,
+ [] (PromotedHeapLocation, LazyNode) { },
+ [] (PromotedHeapLocation) -> Node* {
+ return nullptr;
+ });
+ auto escapees = m_heap.takeEscapees();
+ if (!escapees.isEmpty())
+ placeMaterializations(escapees, node);
+ }
+
+ m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
+
+ {
+ HashMap<Node*, Allocation> escapingOnEdge;
+ for (const auto& entry : m_heap.allocations()) {
+ if (entry.value.isEscapedAllocation())
</ins><span class="cx"> continue;
</span><del>-
- // We only care about sinking candidates.
- if (!m_sinkCandidates.contains(allocation))
- continue;
-
- // We only care if it isn't materialized in the predecessor.
- if (materializedAtTail[block].get(allocation))
- continue;
-
- // We need to decide if we put the materialization at the head of the successor,
- // or the tail of the predecessor. It needs to be placed so that the allocation
- // is never materialized before, and always materialized after.
-
- // Is it never materialized in any of successor's predecessors? I like to think
- // of "successors' predecessors" and "predecessor's successors" as the "shadow",
- // because of what it looks like when you draw it.
- bool neverMaterializedInShadow = true;
- for (BasicBlock* shadowBlock : successorBlock->predecessors) {
- if (materializedAtTail[shadowBlock].get(allocation)) {
- neverMaterializedInShadow = false;
- break;
- }
</del><ins>+
+ bool mustEscape = false;
+ for (BasicBlock* successorBlock : block->successors()) {
+ if (!m_heapAtHead[successorBlock].isAllocation(entry.key)
+ || m_heapAtHead[successorBlock].getAllocation(entry.key).isEscapedAllocation())
+ mustEscape = true;
</ins><span class="cx"> }
</span><del>-
- if (neverMaterializedInShadow) {
- createMaterialize(allocation, successorBlock->firstOriginNode());
- continue;
- }
-
- // Because we had broken critical edges, it must be the case that the
- // predecessor's successors all materialize the object. This is because the
- // previous case is guaranteed to catch the case where the successor only has
- // one predecessor. When critical edges are broken, this is also the only case
- // where the predecessor could have had multiple successors. Therefore we have
- // already handled the case where the predecessor has multiple successors.
- DFG_ASSERT(m_graph, block, block->numSuccessors() == 1);
-
- createMaterialize(allocation, block->terminal());
</del><ins>+
+ if (mustEscape)
+ escapingOnEdge.add(entry.key, entry.value);
</ins><span class="cx"> }
</span><ins>+ placeMaterializations(WTF::move(escapingOnEdge), block->terminal());
</ins><span class="cx"> }
</span><span class="cx"> }
</span><ins>+
+ return hasUnescapedReads || !m_sinkCandidates.isEmpty();
</ins><span class="cx"> }
</span><del>-
- void placeMaterializationPoints()
</del><ins>+
+ void placeMaterializations(HashMap<Node*, Allocation> escapees, Node* where)
</ins><span class="cx"> {
</span><del>- m_ssaCalculator.reset();
-
- // The "variables" are the object allocations that we are sinking. So, nodeToVariable maps
- // sink candidates (aka escapees) to the SSACalculator's notion of Variable, and indexToNode
- // maps in the opposite direction using the SSACalculator::Variable::index() as the key.
- HashMap<Node*, SSACalculator::Variable*> nodeToVariable;
- Vector<Node*> indexToNode;
-
- for (Node* node : m_sinkCandidates) {
- SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
- nodeToVariable.add(node, variable);
- ASSERT(indexToNode.size() == variable->index());
- indexToNode.append(node);
</del><ins>+ // We don't create materializations if the escapee is not a
+ // sink candidate
+ Vector<Node*> toRemove;
+ for (const auto& entry : escapees) {
+ if (!m_sinkCandidates.contains(entry.key))
+ toRemove.append(entry.key);
</ins><span class="cx"> }
</span><del>-
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- for (Node* node : *block) {
- if (SSACalculator::Variable* variable = nodeToVariable.get(node))
- m_ssaCalculator.newDef(variable, block, node);
-
- for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
- m_ssaCalculator.newDef(
- nodeToVariable.get(m_materializationToEscapee.get(materialize)),
- block, materialize);
</del><ins>+ for (Node* identifier : toRemove)
+ escapees.remove(identifier);
+
+ if (escapees.isEmpty())
+ return;
+
+ // First collect the hints that will be needed when the node
+ // we materialize is still stored into other unescaped sink candidates
+ Vector<PromotedHeapLocation> hints;
+ for (const auto& entry : m_heap.allocations()) {
+ if (escapees.contains(entry.key))
+ continue;
+
+ for (const auto& field : entry.value.fields()) {
+ ASSERT(m_sinkCandidates.contains(entry.key) || !escapees.contains(field.value));
+ if (escapees.contains(field.value) && !field.key.neededForMaterialization())
+ hints.append(PromotedHeapLocation(entry.key, field.key));
+ }
+ }
+
+ // Now we need to order the materialization. Any order is
+ // valid (as long as we materialize a node first if it is
+ // needed for the materialization of another node, e.g. a
+ // function's activation must be materialized before the
+ // function itself), but we want to try minimizing the number
+ // of times we have to place Puts to close cycles after a
+ // materialization. In other words, we are trying to find the
+ // minimum number of materializations to remove from the
+ // materialization graph to make it a DAG, known as the
+ // (vertex) feedback set problem. Unfortunately, this is a
+ // NP-hard problem, which we don't want to solve exactly.
+ //
+ // Instead, we use a simple greedy procedure, that procedes as
+ // follow:
+ // - While there is at least one node with no outgoing edge
+ // amongst the remaining materializations, materialize it
+ // first
+ //
+ // - Similarily, while there is at least one node with no
+ // incoming edge amongst the remaining materializations,
+ // materialize it last.
+ //
+ // - When both previous conditions are false, we have an
+ // actual cycle, and we need to pick a node to
+ // materialize. We try greedily to remove the "pressure" on
+ // the remaining nodes by choosing the node with maximum
+ // |incoming edges| * |outgoing edges| as a measure of how
+ // "central" to the graph it is. We materialize it first,
+ // so that all the recoveries will be Puts of things into
+ // it (rather than Puts of the materialization into other
+ // objects), which means we will have a single
+ // StoreBarrier.
+
+
+ // Compute dependencies between materializations
+ HashMap<Node*, HashSet<Node*>> dependencies;
+ HashMap<Node*, HashSet<Node*>> reverseDependencies;
+ HashMap<Node*, HashSet<Node*>> forMaterialization;
+ for (const auto& entry : escapees) {
+ auto& myDependencies = dependencies.add(entry.key, HashSet<Node*>()).iterator->value;
+ auto& myDependenciesForMaterialization = forMaterialization.add(entry.key, HashSet<Node*>()).iterator->value;
+ reverseDependencies.add(entry.key, HashSet<Node*>());
+ for (const auto& field : entry.value.fields()) {
+ if (escapees.contains(field.value) && field.value != entry.key) {
+ myDependencies.add(field.value);
+ reverseDependencies.add(field.value, HashSet<Node*>()).iterator->value.add(entry.key);
+ if (field.key.neededForMaterialization())
+ myDependenciesForMaterialization.add(field.value);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
- m_ssaCalculator.computePhis(
- [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
- Node* allocation = indexToNode[variable->index()];
- if (!m_combinedLiveness.liveAtHead[block].contains(allocation))
- return nullptr;
-
- Node* phiNode = m_graph.addNode(allocation->prediction(), Phi, NodeOrigin());
- phiNode->mergeFlags(NodeResultJS);
- return phiNode;
- });
-
- // Place Phis in the right places. Replace all uses of any allocation with the appropriate
- // materialization. Create the appropriate Upsilon nodes.
- LocalOSRAvailabilityCalculator availabilityCalculator;
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- HashMap<Node*, Node*> mapping;
-
- for (Node* candidate : m_combinedLiveness.liveAtHead[block]) {
- SSACalculator::Variable* variable = nodeToVariable.get(candidate);
- if (!variable)
- continue;
-
- SSACalculator::Def* def = m_ssaCalculator.reachingDefAtHead(block, variable);
- if (!def)
- continue;
-
- mapping.set(indexToNode[variable->index()], def->value());
- }
-
- availabilityCalculator.beginBlock(block);
- for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
- m_insertionSet.insert(0, phiDef->value());
-
- Node* originalNode = indexToNode[phiDef->variable()->index()];
- insertOSRHintsForUpdate(
- m_insertionSet, 0, NodeOrigin(), availabilityCalculator.m_availability,
- originalNode, phiDef->value());
</del><span class="cx">
</span><del>- mapping.set(originalNode, phiDef->value());
</del><ins>+ // Helper function to update the materialized set and the
+ // dependencies
+ HashSet<Node*> materialized;
+ auto materialize = [&] (Node* identifier) {
+ materialized.add(identifier);
+ for (Node* dep : dependencies.get(identifier))
+ reverseDependencies.find(dep)->value.remove(identifier);
+ for (Node* rdep : reverseDependencies.get(identifier)) {
+ dependencies.find(rdep)->value.remove(identifier);
+ forMaterialization.find(rdep)->value.remove(identifier);
</ins><span class="cx"> }
</span><del>-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
</del><ins>+ dependencies.remove(identifier);
+ reverseDependencies.remove(identifier);
+ forMaterialization.remove(identifier);
+ };
</ins><span class="cx">
</span><del>- for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
- Node* escapee = m_materializationToEscapee.get(materialize);
- m_insertionSet.insert(nodeIndex, materialize);
- insertOSRHintsForUpdate(
- m_insertionSet, nodeIndex, node->origin,
- availabilityCalculator.m_availability, escapee, materialize);
- mapping.set(escapee, materialize);
</del><ins>+ // Nodes without remaining unmaterialized fields will be
+ // materialized first - amongst the remaining unmaterialized
+ // nodes
+ std::list<Allocation> toMaterialize;
+ auto firstPos = toMaterialize.begin();
+ auto materializeFirst = [&] (Allocation&& allocation) {
+ materialize(allocation.identifier());
+ // We need to insert *after* the current position
+ if (firstPos != toMaterialize.end())
+ ++firstPos;
+ firstPos = toMaterialize.insert(firstPos, WTF::move(allocation));
+ };
+
+ // Nodes that no other unmaterialized node points to will be
+ // materialized last - amongst the remaining unmaterialized
+ // nodes
+ auto lastPos = toMaterialize.end();
+ auto materializeLast = [&] (Allocation&& allocation) {
+ materialize(allocation.identifier());
+ lastPos = toMaterialize.insert(lastPos, WTF::move(allocation));
+ };
+
+ // These are the promoted locations that contains some of the
+ // allocations we are currently escaping. If they are a location on
+ // some other allocation we are currently materializing, we will need
+ // to "recover" their value with a real put once the corresponding
+ // allocation is materialized; if they are a location on some other
+ // not-yet-materialized allocation, we will need a PutHint.
+ Vector<PromotedHeapLocation> toRecover;
+
+ // This loop does the actual cycle breaking
+ while (!escapees.isEmpty()) {
+ materialized.clear();
+
+ // Materialize nodes that won't require recoveries if we can
+ for (auto& entry : escapees) {
+ if (!forMaterialization.find(entry.key)->value.isEmpty())
+ continue;
+
+ if (dependencies.find(entry.key)->value.isEmpty()) {
+ materializeFirst(WTF::move(entry.value));
+ continue;
</ins><span class="cx"> }
</span><del>-
- availabilityCalculator.executeNode(node);
-
- m_graph.doToChildren(
- node,
- [&] (Edge& edge) {
- if (Node* materialize = mapping.get(edge.node()))
- edge.setNode(materialize);
- });
-
- // If you cause an escape, you shouldn't see the original escapee.
- if (validationEnabled()) {
- handleNode(
- node,
- [&] () { },
- [&] (Node* escapee) {
- DFG_ASSERT(m_graph, node, !m_sinkCandidates.contains(escapee));
- });
</del><ins>+
+ if (reverseDependencies.find(entry.key)->value.isEmpty()) {
+ materializeLast(WTF::move(entry.value));
+ continue;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>-
- NodeAndIndex terminal = block->findTerminal();
- size_t upsilonInsertionPoint = terminal.index;
- Node* upsilonWhere = terminal.node;
- NodeOrigin upsilonOrigin = upsilonWhere->origin;
- for (BasicBlock* successorBlock : block->successors()) {
- for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
- Node* phiNode = phiDef->value();
- SSACalculator::Variable* variable = phiDef->variable();
- Node* allocation = indexToNode[variable->index()];
-
- Node* incoming = mapping.get(allocation);
- DFG_ASSERT(m_graph, incoming, incoming != allocation);
-
- m_insertionSet.insertNode(
- upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
- OpInfo(phiNode), incoming->defaultEdge());
</del><ins>+
+ // We reach this only if there is an actual cycle that needs
+ // breaking. Because we do not want to solve a NP-hard problem
+ // here, we just heuristically pick a node and materialize it
+ // first.
+ if (materialized.isEmpty()) {
+ uint64_t maxEvaluation = 0;
+ Allocation* bestAllocation;
+ for (auto& entry : escapees) {
+ if (!forMaterialization.find(entry.key)->value.isEmpty())
+ continue;
+
+ uint64_t evaluation =
+ static_cast<uint64_t>(dependencies.get(entry.key).size()) * reverseDependencies.get(entry.key).size();
+ if (evaluation > maxEvaluation) {
+ maxEvaluation = evaluation;
+ bestAllocation = &entry.value;
+ }
</ins><span class="cx"> }
</span><ins>+ RELEASE_ASSERT(maxEvaluation > 0);
+
+ materializeFirst(WTF::move(*bestAllocation));
</ins><span class="cx"> }
</span><del>-
- m_insertionSet.execute(block);
</del><ins>+ RELEASE_ASSERT(!materialized.isEmpty());
+
+ for (Node* identifier : materialized)
+ escapees.remove(identifier);
</ins><span class="cx"> }
</span><del>-
- // At this point we have dummy materialization nodes along with edges to them. This means
- // that the part of the control flow graph that prefers to see actual object allocations
- // is completely fixed up, except for the materializations themselves.
</del><ins>+
+ materialized.clear();
+
+ HashSet<Node*> escaped;
+ for (const Allocation& allocation : toMaterialize)
+ escaped.add(allocation.identifier());
+ for (const Allocation& allocation : toMaterialize) {
+ for (const auto& field : allocation.fields()) {
+ if (escaped.contains(field.value) && !materialized.contains(field.value))
+ toRecover.append(PromotedHeapLocation(allocation.identifier(), field.key));
+ }
+ materialized.add(allocation.identifier());
+ }
+
+ Vector<Node*>& materializations = m_materializationSiteToMaterializations.add(
+ where, Vector<Node*>()).iterator->value;
+
+ for (const Allocation& allocation : toMaterialize) {
+ Node* materialization = createMaterialization(allocation, where);
+ materializations.append(materialization);
+ m_materializationToEscapee.add(materialization, allocation.identifier());
+ }
+
+ if (!toRecover.isEmpty()) {
+ m_materializationSiteToRecoveries.add(
+ where, Vector<PromotedHeapLocation>()).iterator->value.appendVector(toRecover);
+ }
+
+ // The hints need to be after the "real" recoveries so that we
+ // don't hint not-yet-complete objects
+ if (!hints.isEmpty()) {
+ m_materializationSiteToRecoveries.add(
+ where, Vector<PromotedHeapLocation>()).iterator->value.appendVector(hints);
+ }
</ins><span class="cx"> }
</span><del>-
- void lowerNonReadingOperationsOnPhantomAllocations()
</del><ins>+
+ Node* createMaterialization(const Allocation& allocation, Node* where)
</ins><span class="cx"> {
</span><del>- // Lower everything but reading operations on phantom allocations. We absolutely have to
- // lower all writes so as to reveal them to the SSA calculator. We cannot lower reads
- // because the whole point is that those go away completely.
-
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
- switch (node->op()) {
- case PutByOffset: {
- Node* target = node->child2().node();
- if (m_sinkCandidates.contains(target)) {
- ASSERT(target->isPhantomObjectAllocation());
- node->convertToPutByOffsetHint();
- }
- break;
- }
</del><ins>+ // FIXME: This is the only place where we actually use the
+ // fact that an allocation's identifier is indeed the node
+ // that created the allocation.
+ switch (allocation.kind()) {
+ case Allocation::Kind::Object: {
+ ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
+ StructureSet* set = m_graph.addStructureSet(allocation.structures());
</ins><span class="cx">
</span><del>- case PutClosureVar: {
- Node* target = node->child1().node();
- if (m_sinkCandidates.contains(target)) {
- ASSERT(target->isPhantomActivationAllocation());
- node->convertToPutClosureVarHint();
- }
- break;
- }
-
- case PutStructure: {
- Node* target = node->child1().node();
- if (m_sinkCandidates.contains(target)) {
- ASSERT(target->isPhantomObjectAllocation());
- Node* structure = m_insertionSet.insertConstant(
- nodeIndex, node->origin, JSValue(node->transition()->next));
- node->convertToPutStructureHint(structure);
- }
- break;
- }
-
- case NewObject: {
- if (m_sinkCandidates.contains(node)) {
- Node* structure = m_insertionSet.insertConstant(
- nodeIndex + 1, node->origin, JSValue(node->structure()));
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(StructurePLoc, node).createHint(
- m_graph, node->origin, structure));
- node->convertToPhantomNewObject();
- }
- break;
- }
-
- case MaterializeNewObject: {
- if (m_sinkCandidates.contains(node)) {
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(StructurePLoc, node).createHint(
- m_graph, node->origin, m_graph.varArgChild(node, 0).node()));
- for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
- unsigned identifierNumber =
- node->objectMaterializationData().m_properties[i].m_identifierNumber;
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(
- NamedPropertyPLoc, node, identifierNumber).createHint(
- m_graph, node->origin,
- m_graph.varArgChild(node, i + 1).node()));
- }
- node->convertToPhantomNewObject();
- }
- break;
- }
</del><ins>+ return m_graph.addNode(
+ allocation.identifier()->prediction(), Node::VarArg, MaterializeNewObject,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(set), OpInfo(data), 0, 0);
+ }
</ins><span class="cx">
</span><del>- case NewFunction: {
- if (m_sinkCandidates.contains(node)) {
- Node* executable = m_insertionSet.insertConstant(
- nodeIndex + 1, node->origin, node->cellOperand());
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(FunctionExecutablePLoc, node).createHint(
- m_graph, node->origin, executable));
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(FunctionActivationPLoc, node).createHint(
- m_graph, node->origin, node->child1().node()));
- node->convertToPhantomNewFunction();
- }
- break;
- }
</del><ins>+ case Allocation::Kind::Function: {
+ FrozenValue* executable = allocation.identifier()->cellOperand();
</ins><span class="cx">
</span><del>- case CreateActivation: {
- if (m_sinkCandidates.contains(node)) {
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(ActivationScopePLoc, node).createHint(
- m_graph, node->origin, node->child1().node()));
- Node* symbolTableNode = m_insertionSet.insertConstant(
- nodeIndex + 1, node->origin, node->cellOperand());
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
- m_graph, node->origin, symbolTableNode));
</del><ins>+ return m_graph.addNode(
+ allocation.identifier()->prediction(), NewFunction,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(executable));
+ break;
+ }
</ins><span class="cx">
</span><del>- {
- SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
- Node* undefined = m_insertionSet.insertConstant(
- nodeIndex + 1, node->origin, jsUndefined());
- ConcurrentJITLocker locker(symbolTable->m_lock);
- for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(
- ClosureVarPLoc, node, iter->value.scopeOffset().offset()).createHint(
- m_graph, node->origin, undefined));
- }
- }
</del><ins>+ case Allocation::Kind::Activation: {
+ ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
+ FrozenValue* symbolTable = allocation.identifier()->cellOperand();
</ins><span class="cx">
</span><del>- node->convertToPhantomCreateActivation();
- }
- break;
- }
</del><ins>+ return m_graph.addNode(
+ allocation.identifier()->prediction(), Node::VarArg, MaterializeCreateActivation,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(symbolTable), OpInfo(data), 0, 0);
+ }
</ins><span class="cx">
</span><del>- case MaterializeCreateActivation: {
- if (m_sinkCandidates.contains(node)) {
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(ActivationScopePLoc, node).createHint(
- m_graph, node->origin, m_graph.varArgChild(node, 0).node()));
- Node* symbolTableNode = m_insertionSet.insertConstant(
- nodeIndex + 1, node->origin, node->cellOperand());
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
- m_graph, node->origin, symbolTableNode));
- ObjectMaterializationData& data = node->objectMaterializationData();
- for (unsigned i = 0; i < data.m_properties.size(); ++i) {
- unsigned identifierNumber = data.m_properties[i].m_identifierNumber;
- m_insertionSet.insert(
- nodeIndex + 1,
- PromotedHeapLocation(
- ClosureVarPLoc, node, identifierNumber).createHint(
- m_graph, node->origin,
- m_graph.varArgChild(node, i + 1).node()));
- }
- node->convertToPhantomCreateActivation();
- }
- break;
- }
-
- case StoreBarrier: {
- DFG_CRASH(m_graph, node, "Unexpected store barrier during sinking.");
- break;
- }
-
- default:
- break;
- }
-
- m_graph.doToChildren(
- node,
- [&] (Edge& edge) {
- if (m_sinkCandidates.contains(edge.node()))
- edge.setUseKind(KnownCellUse);
- });
- }
- m_insertionSet.execute(block);
</del><ins>+ default:
+ DFG_CRASH(m_graph, allocation.identifier(), "Bad allocation kind");
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>-
- void promoteSunkenFields()
</del><ins>+
+ void promoteLocalHeap()
</ins><span class="cx"> {
</span><del>- // Collect the set of heap locations that we will be operating over.
</del><ins>+ // Collect the set of heap locations that we will be operating
+ // over.
</ins><span class="cx"> HashSet<PromotedHeapLocation> locations;
</span><span class="cx"> for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
</span><ins>+ m_heap = m_heapAtHead[block];
+
</ins><span class="cx"> for (Node* node : *block) {
</span><del>- promoteHeapAccess(
</del><ins>+ handleNode(
</ins><span class="cx"> node,
</span><del>- [&] (PromotedHeapLocation location, Edge) {
</del><ins>+ [&] (PromotedHeapLocation location, LazyNode) {
+ // If the location is not on a sink candidate,
+ // we only sink it if it is read
</ins><span class="cx"> if (m_sinkCandidates.contains(location.base()))
</span><span class="cx"> locations.add(location);
</span><span class="cx"> },
</span><del>- [&] (PromotedHeapLocation location) {
- if (m_sinkCandidates.contains(location.base()))
- locations.add(location);
</del><ins>+ [&] (PromotedHeapLocation location) -> Node* {
+ locations.add(location);
+ return nullptr;
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> // Figure out which locations belong to which allocations.
</span><span class="cx"> m_locationsForAllocation.clear();
</span><span class="cx"> for (PromotedHeapLocation location : locations) {
</span><del>- auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>());
</del><ins>+ auto result = m_locationsForAllocation.add(
+ location.base(),
+ Vector<PromotedHeapLocation>());
</ins><span class="cx"> ASSERT(!result.iterator->value.contains(location));
</span><span class="cx"> result.iterator->value.append(location);
</span><span class="cx"> }
</span><del>-
- // For each sunken thingy, make sure we create Bottom values for all of its fields.
- // Note that this has the hilarious slight inefficiency of creating redundant hints for
- // things that were previously materializations. This should only impact compile times and
- // not code quality, and it's necessary for soundness without some data structure hackage.
- // For example, a MaterializeNewObject that we choose to sink may have new fields added to
- // it conditionally. That would necessitate Bottoms.
- Node* bottom = nullptr;
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- if (block == m_graph.block(0))
- bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsUndefined());
-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
- for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) {
- m_insertionSet.insert(
- nodeIndex + 1, location.createHint(m_graph, node->origin, bottom));
- }
- }
- m_insertionSet.execute(block);
- }
</del><span class="cx">
</span><del>- m_ssaCalculator.reset();
</del><ins>+ m_pointerSSA.reset();
+ m_allocationSSA.reset();
</ins><span class="cx">
</span><span class="cx"> // Collect the set of "variables" that we will be sinking.
</span><span class="cx"> m_locationToVariable.clear();
</span><del>- m_indexToLocation.clear();
</del><ins>+ m_nodeToVariable.clear();
+ Vector<Node*> indexToNode;
+ Vector<PromotedHeapLocation> indexToLocation;
+
+ for (Node* index : m_sinkCandidates) {
+ SSACalculator::Variable* variable = m_allocationSSA.newVariable();
+ m_nodeToVariable.add(index, variable);
+ ASSERT(indexToNode.size() == variable->index());
+ indexToNode.append(index);
+ }
+
</ins><span class="cx"> for (PromotedHeapLocation location : locations) {
</span><del>- SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
</del><ins>+ SSACalculator::Variable* variable = m_pointerSSA.newVariable();
</ins><span class="cx"> m_locationToVariable.add(location, variable);
</span><del>- ASSERT(m_indexToLocation.size() == variable->index());
- m_indexToLocation.append(location);
</del><ins>+ ASSERT(indexToLocation.size() == variable->index());
+ indexToLocation.append(location);
</ins><span class="cx"> }
</span><del>-
- // Create Defs from the existing hints.
</del><ins>+
+ // We insert all required constants at top of block 0 so that
+ // they are inserted only once and we don't clutter the graph
+ // with useless constants everywhere
+ HashMap<FrozenValue*, Node*> lazyMapping;
+ if (!m_bottom)
+ m_bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsNumber(1927));
</ins><span class="cx"> for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
</span><del>- for (Node* node : *block) {
- promoteHeapAccess(
</del><ins>+ m_heap = m_heapAtHead[block];
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+
+ // Some named properties can be added conditionally,
+ // and that would necessitate bottoms
+ for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) {
+ if (location.kind() != NamedPropertyPLoc)
+ continue;
+
+ SSACalculator::Variable* variable = m_locationToVariable.get(location);
+ m_pointerSSA.newDef(variable, block, m_bottom);
+ }
+
+ for (Node* materialization : m_materializationSiteToMaterializations.get(node)) {
+ Node* escapee = m_materializationToEscapee.get(materialization);
+ m_allocationSSA.newDef(m_nodeToVariable.get(escapee), block, materialization);
+ }
+
+ if (m_sinkCandidates.contains(node))
+ m_allocationSSA.newDef(m_nodeToVariable.get(node), block, node);
+
+ handleNode(
</ins><span class="cx"> node,
</span><del>- [&] (PromotedHeapLocation location, Edge value) {
- if (!m_sinkCandidates.contains(location.base()))
</del><ins>+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!locations.contains(location))
</ins><span class="cx"> return;
</span><ins>+
+ Node* nodeValue;
+ if (value.isNode())
+ nodeValue = value.asNode();
+ else {
+ auto iter = lazyMapping.find(value.asValue());
+ if (iter != lazyMapping.end())
+ nodeValue = iter->value;
+ else {
+ nodeValue = value.ensureIsNode(
+ m_insertionSet, m_graph.block(0), 0);
+ lazyMapping.add(value.asValue(), nodeValue);
+ }
+ }
+
</ins><span class="cx"> SSACalculator::Variable* variable = m_locationToVariable.get(location);
</span><del>- m_ssaCalculator.newDef(variable, block, value.node());
</del><ins>+ m_pointerSSA.newDef(variable, block, nodeValue);
</ins><span class="cx"> },
</span><del>- [&] (PromotedHeapLocation) { });
</del><ins>+ [] (PromotedHeapLocation) -> Node* {
+ return nullptr;
+ });
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>-
- // OMG run the SSA calculator to create Phis!
- m_ssaCalculator.computePhis(
</del><ins>+ m_insertionSet.execute(m_graph.block(0));
+
+ // Run the SSA calculators to create Phis
+ m_pointerSSA.computePhis(
</ins><span class="cx"> [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
</span><del>- PromotedHeapLocation location = m_indexToLocation[variable->index()];
- if (!m_combinedLiveness.liveAtHead[block].contains(location.base()))
</del><ins>+ PromotedHeapLocation location = indexToLocation[variable->index()];
+
+ // Don't create Phi nodes for fields of dead allocations
+ if (!m_heapAtHead[block].isAllocation(location.base()))
</ins><span class="cx"> return nullptr;
</span><del>-
</del><ins>+
+ // Don't create Phi nodes once we are escaped
+ if (m_heapAtHead[block].getAllocation(location.base()).isEscapedAllocation())
+ return nullptr;
+
+ // If we point to a single allocation, we will
+ // directly use its materialization
+ if (m_heapAtHead[block].follow(location))
+ return nullptr;
+
</ins><span class="cx"> Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
</span><span class="cx"> phiNode->mergeFlags(NodeResultJS);
</span><span class="cx"> return phiNode;
</span><span class="cx"> });
</span><del>-
</del><ins>+
+ m_allocationSSA.computePhis(
+ [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
+ Node* identifier = indexToNode[variable->index()];
+
+ // Don't create Phi nodes for dead allocations
+ if (!m_heapAtHead[block].isAllocation(identifier))
+ return nullptr;
+
+ // Don't create Phi nodes until we are escaped
+ if (!m_heapAtHead[block].getAllocation(identifier).isEscapedAllocation())
+ return nullptr;
+
+ Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+ phiNode->mergeFlags(NodeResultJS);
+ return phiNode;
+ });
+
</ins><span class="cx"> // Place Phis in the right places, replace all uses of any load with the appropriate
</span><del>- // value, and create the appropriate Upsilon nodes.
</del><ins>+ // value, and create the materialization nodes.
+ LocalOSRAvailabilityCalculator availabilityCalculator;
</ins><span class="cx"> m_graph.clearReplacements();
</span><span class="cx"> for (BasicBlock* block : m_graph.blocksInPreOrder()) {
</span><del>- // This mapping table is intended to be lazy. If something is omitted from the table,
- // it means that there haven't been any local stores to that promoted heap location.
</del><ins>+ m_heap = m_heapAtHead[block];
+ availabilityCalculator.beginBlock(block);
+
+ // These mapping tables are intended to be lazy. If
+ // something is omitted from the table, it means that
+ // there haven't been any local stores to the promoted
+ // heap location (or any local materialization).
</ins><span class="cx"> m_localMapping.clear();
</span><del>-
- // Insert the Phi functions that we had previously created.
- for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
- PromotedHeapLocation location = m_indexToLocation[phiDef->variable()->index()];
-
- m_insertionSet.insert(
- 0, phiDef->value());
- m_insertionSet.insert(
- 0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
- m_localMapping.add(location, phiDef->value());
</del><ins>+ m_escapeeToMaterialization.clear();
+
+ // Insert the Phi functions that we had previously
+ // created.
+ for (SSACalculator::Def* phiDef : m_pointerSSA.phisForBlock(block)) {
+ SSACalculator::Variable* variable = phiDef->variable();
+ m_insertionSet.insert(0, phiDef->value());
+
+ PromotedHeapLocation location = indexToLocation[variable->index()];
+ m_localMapping.set(location, phiDef->value());
+
+ if (m_sinkCandidates.contains(location.base())) {
+ m_insertionSet.insert(
+ 0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
+ }
</ins><span class="cx"> }
</span><del>-
- if (verbose)
</del><ins>+
+ for (SSACalculator::Def* phiDef : m_allocationSSA.phisForBlock(block)) {
+ SSACalculator::Variable* variable = phiDef->variable();
+ m_insertionSet.insert(0, phiDef->value());
+
+ Node* identifier = indexToNode[variable->index()];
+ m_escapeeToMaterialization.add(identifier, phiDef->value());
+ insertOSRHintsForUpdate(0, NodeOrigin(), availabilityCalculator.m_availability, identifier, phiDef->value());
+ }
+
+ if (verbose) {
</ins><span class="cx"> dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n");
</span><del>-
- // Process the block and replace all uses of loads with the promoted value.
- for (Node* node : *block) {
- m_graph.performSubstitution(node);
-
- if (Node* escapee = m_materializationToEscapee.get(node))
- populateMaterialize(block, node, escapee);
-
- promoteHeapAccess(
</del><ins>+ dataLog("Local materializations at ", pointerDump(block), ": ", mapDump(m_escapeeToMaterialization), "\n");
+ }
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) {
+ if (location.kind() != NamedPropertyPLoc)
+ continue;
+
+ m_localMapping.set(location, m_bottom);
+
+ if (m_sinkCandidates.contains(node)) {
+ m_insertionSet.insert(
+ nodeIndex + 1,
+ location.createHint(m_graph, node->origin, m_bottom));
+ }
+ }
+
+ for (Node* materialization : m_materializationSiteToMaterializations.get(node)) {
+ Node* escapee = m_materializationToEscapee.get(materialization);
+ populateMaterialization(block, materialization, escapee);
+ m_escapeeToMaterialization.set(escapee, materialization);
+ m_insertionSet.insert(nodeIndex, materialization);
+ if (verbose)
+ dataLog("Materializing ", escapee, " => ", materialization, " at ", node, "\n");
+ }
+
+ for (PromotedHeapLocation location : m_materializationSiteToRecoveries.get(node))
+ m_insertionSet.insert(nodeIndex, createRecovery(block, location, node));
+
+ // We need to put the OSR hints after the recoveries,
+ // because we only want the hints once the object is
+ // complete
+ for (Node* materialization : m_materializationSiteToMaterializations.get(node)) {
+ Node* escapee = m_materializationToEscapee.get(materialization);
+ insertOSRHintsForUpdate(
+ nodeIndex, node->origin,
+ availabilityCalculator.m_availability, escapee, materialization);
+ }
+
+ if (m_sinkCandidates.contains(node))
+ m_escapeeToMaterialization.set(node, node);
+
+ availabilityCalculator.executeNode(node);
+
+ bool doLower = false;
+ handleNode(
</ins><span class="cx"> node,
</span><del>- [&] (PromotedHeapLocation location, Edge value) {
- if (m_sinkCandidates.contains(location.base()))
- m_localMapping.set(location, value.node());
</del><ins>+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!locations.contains(location))
+ return;
+
+ Node* nodeValue;
+ if (value.isNode())
+ nodeValue = value.asNode();
+ else
+ nodeValue = lazyMapping.get(value.asValue());
+
+ nodeValue = resolve(block, nodeValue);
+
+ m_localMapping.set(location, nodeValue);
+
+ if (!m_sinkCandidates.contains(location.base()))
+ return;
+
+ doLower = true;
+
+ m_insertionSet.insert(nodeIndex + 1,
+ location.createHint(m_graph, node->origin, nodeValue));
</ins><span class="cx"> },
</span><del>- [&] (PromotedHeapLocation location) {
- if (m_sinkCandidates.contains(location.base())) {
- switch (node->op()) {
- case CheckStructure:
- node->convertToCheckStructureImmediate(resolve(block, location));
- break;
</del><ins>+ [&] (PromotedHeapLocation location) -> Node* {
+ return resolve(block, location);
+ });
</ins><span class="cx">
</span><del>- default:
- node->replaceWith(resolve(block, location));
- break;
- }
- }
</del><ins>+ if (m_sinkCandidates.contains(node) || doLower) {
+ switch (node->op()) {
+ case NewObject:
+ case MaterializeNewObject:
+ node->convertToPhantomNewObject();
+ break;
+
+ case NewFunction:
+ node->convertToPhantomNewFunction();
+ break;
+
+ case CreateActivation:
+ case MaterializeCreateActivation:
+ node->convertToPhantomCreateActivation();
+ break;
+
+ default:
+ node->remove();
+ break;
+ }
+ }
+
+ m_graph.doToChildren(
+ node,
+ [&] (Edge& edge) {
+ edge.setNode(resolve(block, edge.node()));
</ins><span class="cx"> });
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> // Gotta drop some Upsilons.
</span><span class="cx"> NodeAndIndex terminal = block->findTerminal();
</span><span class="cx"> size_t upsilonInsertionPoint = terminal.index;
</span><span class="cx"> NodeOrigin upsilonOrigin = terminal.node->origin;
</span><span class="cx"> for (BasicBlock* successorBlock : block->successors()) {
</span><del>- for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
</del><ins>+ for (SSACalculator::Def* phiDef : m_pointerSSA.phisForBlock(successorBlock)) {
</ins><span class="cx"> Node* phiNode = phiDef->value();
</span><span class="cx"> SSACalculator::Variable* variable = phiDef->variable();
</span><del>- PromotedHeapLocation location = m_indexToLocation[variable->index()];
</del><ins>+ PromotedHeapLocation location = indexToLocation[variable->index()];
</ins><span class="cx"> Node* incoming = resolve(block, location);
</span><del>-
</del><ins>+
</ins><span class="cx"> m_insertionSet.insertNode(
</span><span class="cx"> upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
</span><span class="cx"> OpInfo(phiNode), incoming->defaultEdge());
</span><span class="cx"> }
</span><ins>+
+ for (SSACalculator::Def* phiDef : m_allocationSSA.phisForBlock(successorBlock)) {
+ Node* phiNode = phiDef->value();
+ SSACalculator::Variable* variable = phiDef->variable();
+ Node* incoming = getMaterialization(block, indexToNode[variable->index()]);
+
+ m_insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
+ OpInfo(phiNode), incoming->defaultEdge());
+ }
</ins><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> m_insertionSet.execute(block);
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> Node* resolve(BasicBlock* block, PromotedHeapLocation location)
</span><span class="cx"> {
</span><ins>+ // If we are currently pointing to a single local allocation,
+ // simply return the associated materialization.
+ if (Node* identifier = m_heap.follow(location))
+ return getMaterialization(block, identifier);
+
</ins><span class="cx"> if (Node* result = m_localMapping.get(location))
</span><span class="cx"> return result;
</span><del>-
</del><ins>+
</ins><span class="cx"> // This implies that there is no local mapping. Find a non-local mapping.
</span><del>- SSACalculator::Def* def = m_ssaCalculator.nonLocalReachingDef(
</del><ins>+ SSACalculator::Def* def = m_pointerSSA.nonLocalReachingDef(
</ins><span class="cx"> block, m_locationToVariable.get(location));
</span><span class="cx"> ASSERT(def);
</span><span class="cx"> ASSERT(def->value());
</span><del>- m_localMapping.add(location, def->value());
- return def->value();
</del><ins>+
+ Node* result = def->value();
+
+ ASSERT(!result->replacement());
+
+ m_localMapping.add(location, result);
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- template<typename SinkCandidateFunctor, typename EscapeFunctor>
- void handleNode(
- Node* node,
- const SinkCandidateFunctor& sinkCandidate,
- const EscapeFunctor& escape)
</del><ins>+ Node* resolve(BasicBlock* block, Node* node)
</ins><span class="cx"> {
</span><del>- switch (node->op()) {
- case NewObject:
- case MaterializeNewObject:
- case MaterializeCreateActivation:
- sinkCandidate();
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- escape(edge.node());
- });
- break;
</del><ins>+ // If we are currently pointing to a single local allocation,
+ // simply return the associated materialization.
+ if (Node* identifier = m_heap.follow(node))
+ return getMaterialization(block, identifier);
</ins><span class="cx">
</span><del>- case NewFunction:
- if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
- break;
</del><ins>+ if (node->replacement())
+ node = node->replacement();
+ ASSERT(!node->replacement());
</ins><span class="cx">
</span><del>- case CreateActivation:
- if (!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
- break;
</del><ins>+ return node;
+ }
</ins><span class="cx">
</span><del>- case Check:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- if (edge.willNotHaveCheck())
- return;
-
- if (alreadyChecked(edge.useKind(), SpecObject))
- return;
-
- escape(edge.node());
- });
- break;
</del><ins>+ Node* getMaterialization(BasicBlock* block, Node* identifier)
+ {
+ ASSERT(m_heap.isAllocation(identifier));
+ if (!m_sinkCandidates.contains(identifier))
+ return identifier;
</ins><span class="cx">
</span><del>- case MovHint:
- case PutHint:
- break;
</del><ins>+ if (Node* materialization = m_escapeeToMaterialization.get(identifier))
+ return materialization;
</ins><span class="cx">
</span><del>- case PutStructure:
- case CheckStructure:
- case GetByOffset:
- case MultiGetByOffset:
- case GetGetterSetterByOffset: {
- Node* target = node->child1().node();
- if (!target->isObjectAllocation())
- escape(target);
- break;
- }
-
- case PutByOffset: {
- Node* target = node->child2().node();
- if (!target->isObjectAllocation()) {
- escape(target);
- escape(node->child1().node());
- }
- escape(node->child3().node());
- break;
- }
</del><ins>+ SSACalculator::Def* def = m_allocationSSA.nonLocalReachingDef(
+ block, m_nodeToVariable.get(identifier));
+ ASSERT(def && def->value());
+ m_escapeeToMaterialization.add(identifier, def->value());
+ ASSERT(!def->value()->replacement());
+ return def->value();
+ }
</ins><span class="cx">
</span><del>- case GetClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- break;
- }
</del><ins>+ void insertOSRHintsForUpdate(unsigned nodeIndex, NodeOrigin origin, AvailabilityMap& availability, Node* escapee, Node* materialization)
+ {
+ // We need to follow() the value in the heap.
+ // Consider the following graph:
+ //
+ // Block #0
+ // 0: NewObject({})
+ // 1: NewObject({})
+ // -: PutByOffset(@0, @1, x:0)
+ // -: PutStructure(@0, {x:0})
+ // 2: GetByOffset(@0, x:0)
+ // -: MovHint(@2, loc1)
+ // -: Branch(#1, #2)
+ //
+ // Block #1
+ // 3: Call(f, @1)
+ // 4: Return(@0)
+ //
+ // Block #2
+ // -: Return(undefined)
+ //
+ // We need to materialize @1 at @3, and when doing so we need
+ // to insert a MovHint for the materialization into loc1 as
+ // well.
+ // In order to do this, we say that we need to insert an
+ // update hint for any availability whose node resolve()s to
+ // the materialization.
+ for (auto entry : availability.m_heap) {
+ if (!entry.value.hasNode())
+ continue;
+ if (m_heap.follow(entry.value.node()) != escapee)
+ continue;
</ins><span class="cx">
</span><del>- case PutClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- escape(node->child2().node());
- break;
</del><ins>+ m_insertionSet.insert(
+ nodeIndex, entry.key.createHint(m_graph, origin, materialization));
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- case GetScope: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
- }
</del><ins>+ for (unsigned i = availability.m_locals.size(); i--;) {
+ if (!availability.m_locals[i].hasNode())
+ continue;
+ if (m_heap.follow(availability.m_locals[i].node()) != escapee)
+ continue;
</ins><span class="cx">
</span><del>- case GetExecutable: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
</del><ins>+ int operand = availability.m_locals.operandForIndex(i);
+ m_insertionSet.insertNode(
+ nodeIndex, SpecNone, MovHint, origin, OpInfo(operand),
+ materialization->defaultEdge());
</ins><span class="cx"> }
</span><del>-
- case SkipScope: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- break;
- }
-
- case MultiPutByOffset:
- // FIXME: In the future we should be able to handle this. It's just a matter of
- // building the appropriate *Hint variant of this instruction, along with a
- // PhantomStructureSelect node - since this transforms the Structure in a conditional
- // way.
- // https://bugs.webkit.org/show_bug.cgi?id=136924
- escape(node->child1().node());
- escape(node->child2().node());
- break;
-
- default:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- escape(edge.node());
- });
- break;
- }
</del><span class="cx"> }
</span><del>-
- Node* createMaterialize(Node* escapee, Node* where)
- {
- Node* result = nullptr;
-
- switch (escapee->op()) {
- case NewObject:
- case MaterializeNewObject: {
- ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
-
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeNewObject,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(data), OpInfo(), 0, 0);
- break;
- }
</del><span class="cx">
</span><del>- case NewFunction:
- result = m_graph.addNode(
- escapee->prediction(), NewFunction,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(escapee->cellOperand()),
- escapee->child1());
- break;
-
- case CreateActivation:
- case MaterializeCreateActivation: {
- ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
- FrozenValue* symbolTable = escapee->cellOperand();
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(data), OpInfo(symbolTable), 0, 0);
- break;
- }
-
- default:
- DFG_CRASH(m_graph, escapee, "Bad escapee op");
- break;
- }
-
- if (verbose)
- dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
-
- m_materializationToEscapee.add(result, escapee);
- m_materializationSiteToMaterializations.add(
- where, Vector<Node*>()).iterator->value.append(result);
-
- return result;
- }
-
- void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
</del><ins>+ void populateMaterialization(BasicBlock* block, Node* node, Node* escapee)
</ins><span class="cx"> {
</span><ins>+ Allocation& allocation = m_heap.getAllocation(escapee);
</ins><span class="cx"> switch (node->op()) {
</span><span class="cx"> case MaterializeNewObject: {
</span><span class="cx"> ObjectMaterializationData& data = node->objectMaterializationData();
</span><span class="cx"> unsigned firstChild = m_graph.m_varArgChildren.size();
</span><del>-
</del><ins>+
</ins><span class="cx"> Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
</span><del>-
- PromotedHeapLocation structure(StructurePLoc, escapee);
</del><ins>+
+ PromotedHeapLocation structure(StructurePLoc, allocation.identifier());
</ins><span class="cx"> ASSERT(locations.contains(structure));
</span><del>-
</del><ins>+
</ins><span class="cx"> m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse));
</span><del>-
- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
- case StructurePLoc: {
- ASSERT(locations[i] == structure);
</del><ins>+
+ for (PromotedHeapLocation location : locations) {
+ switch (location.kind()) {
+ case StructurePLoc:
+ ASSERT(location == structure);
</ins><span class="cx"> break;
</span><del>- }
-
</del><ins>+
</ins><span class="cx"> case NamedPropertyPLoc: {
</span><del>- Node* value = resolve(block, locations[i]);
- if (value->op() == BottomValue) {
- // We can skip Bottoms entirely.
- break;
- }
-
- data.m_properties.append(PhantomPropertyValue(locations[i].info()));
- m_graph.m_varArgChildren.append(value);
</del><ins>+ ASSERT(location.base() == allocation.identifier());
+ data.m_properties.append(PhantomPropertyValue(location.info()));
+ Node* value = resolve(block, location);
+ if (m_sinkCandidates.contains(value))
+ m_graph.m_varArgChildren.append(m_bottom);
+ else
+ m_graph.m_varArgChildren.append(value);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> default:
</span><span class="cx"> DFG_CRASH(m_graph, node, "Bad location kind");
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> node->children = AdjacencyList(
</span><span class="cx"> AdjacencyList::Variable,
</span><span class="cx"> firstChild, m_graph.m_varArgChildren.size() - firstChild);
</span><span class="lines">@@ -1063,31 +1930,35 @@
</span><span class="cx">
</span><span class="cx"> Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
</span><span class="cx">
</span><del>- PromotedHeapLocation scope(ActivationScopePLoc, escapee);
- PromotedHeapLocation symbolTable(ActivationSymbolTablePLoc, escapee);
</del><ins>+ PromotedHeapLocation symbolTable(ActivationSymbolTablePLoc, allocation.identifier());
+ ASSERT(locations.contains(symbolTable));
+ ASSERT(node->cellOperand() == resolve(block, symbolTable)->constant());
+ m_graph.m_varArgChildren.append(Edge(resolve(block, symbolTable), KnownCellUse));
+
+ PromotedHeapLocation scope(ActivationScopePLoc, allocation.identifier());
</ins><span class="cx"> ASSERT(locations.contains(scope));
</span><del>-
</del><span class="cx"> m_graph.m_varArgChildren.append(Edge(resolve(block, scope), KnownCellUse));
</span><span class="cx">
</span><del>- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
</del><ins>+ for (PromotedHeapLocation location : locations) {
+ switch (location.kind()) {
</ins><span class="cx"> case ActivationScopePLoc: {
</span><del>- ASSERT(locations[i] == scope);
</del><ins>+ ASSERT(location == scope);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case ActivationSymbolTablePLoc: {
</span><del>- ASSERT(locations[i] == symbolTable);
</del><ins>+ ASSERT(location == symbolTable);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case ClosureVarPLoc: {
</span><del>- Node* value = resolve(block, locations[i]);
- if (value->op() == BottomValue)
- break;
-
- data.m_properties.append(PhantomPropertyValue(locations[i].info()));
- m_graph.m_varArgChildren.append(value);
</del><ins>+ ASSERT(location.base() == allocation.identifier());
+ data.m_properties.append(PhantomPropertyValue(location.info()));
+ Node* value = resolve(block, location);
+ if (m_sinkCandidates.contains(value))
+ m_graph.m_varArgChildren.append(m_bottom);
+ else
+ m_graph.m_varArgChildren.append(value);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -1103,56 +1974,157 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case NewFunction: {
</span><del>- if (!ASSERT_DISABLED) {
- Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
</del><ins>+ Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
+ ASSERT(locations.size() == 2);
</ins><span class="cx">
</span><del>- ASSERT(locations.size() == 2);
</del><ins>+ PromotedHeapLocation executable(FunctionExecutablePLoc, allocation.identifier());
+ ASSERT_UNUSED(executable, locations.contains(executable));
</ins><span class="cx">
</span><del>- PromotedHeapLocation executable(FunctionExecutablePLoc, escapee);
- ASSERT(locations.contains(executable));
</del><ins>+ PromotedHeapLocation activation(FunctionActivationPLoc, allocation.identifier());
+ ASSERT(locations.contains(activation));
</ins><span class="cx">
</span><del>- PromotedHeapLocation activation(FunctionActivationPLoc, escapee);
- ASSERT(locations.contains(activation));
</del><ins>+ node->child1() = Edge(resolve(block, activation), KnownCellUse);
+ break;
+ }
</ins><span class="cx">
</span><del>- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
- case FunctionExecutablePLoc: {
- ASSERT(locations[i] == executable);
- break;
- }
</del><ins>+ default:
+ DFG_CRASH(m_graph, node, "Bad materialize op");
+ }
+ }
</ins><span class="cx">
</span><del>- case FunctionActivationPLoc: {
- ASSERT(locations[i] == activation);
- break;
- }
</del><ins>+ Node* createRecovery(BasicBlock* block, PromotedHeapLocation location, Node* where)
+ {
+ if (verbose)
+ dataLog("Recovering ", location, " at ", where, "\n");
+ ASSERT(location.base()->isPhantomAllocation());
+ Node* base = getMaterialization(block, location.base());
+ Node* value = resolve(block, location);
</ins><span class="cx">
</span><del>- default:
- DFG_CRASH(m_graph, node, "Bad location kind");
</del><ins>+ if (verbose)
+ dataLog("Base is ", base, " and value is ", value, "\n");
+
+ if (base->isPhantomAllocation()) {
+ return PromotedHeapLocation(base, location.descriptor()).createHint(
+ m_graph,
+ NodeOrigin(
+ base->origin.semantic,
+ where->origin.forExit),
+ value);
+ }
+
+ switch (location.kind()) {
+ case NamedPropertyPLoc: {
+ Allocation& allocation = m_heap.getAllocation(location.base());
+
+ Vector<Structure*> structures;
+ structures.appendRange(allocation.structures().begin(), allocation.structures().end());
+ unsigned identifierNumber = location.info();
+ UniquedStringImpl* uid = m_graph.identifiers()[identifierNumber];
+
+ std::sort(
+ structures.begin(),
+ structures.end(),
+ [uid] (Structure *a, Structure* b) -> bool {
+ return a->getConcurrently(uid) < b->getConcurrently(uid);
+ });
+
+ PropertyOffset firstOffset = structures[0]->getConcurrently(uid);
+
+ if (firstOffset == structures.last()->getConcurrently(uid)) {
+ Node* storage = base;
+ // FIXME: When we decide to sink objects with a
+ // property storage, we should handle non-inline offsets.
+ RELEASE_ASSERT(isInlineOffset(firstOffset));
+
+ StorageAccessData* data = m_graph.m_storageAccessData.add();
+ data->offset = firstOffset;
+ data->identifierNumber = identifierNumber;
+
+ return m_graph.addNode(
+ SpecNone,
+ PutByOffset,
+ where->origin,
+ OpInfo(data),
+ Edge(storage, KnownCellUse),
+ Edge(base, KnownCellUse),
+ value->defaultEdge());
+ }
+
+ MultiPutByOffsetData* data = m_graph.m_multiPutByOffsetData.add();
+ data->identifierNumber = identifierNumber;
+
+ {
+ PropertyOffset currentOffset = firstOffset;
+ StructureSet currentSet;
+ for (Structure* structure : structures) {
+ PropertyOffset offset = structure->getConcurrently(uid);
+ if (offset != currentOffset) {
+ data->variants.append(
+ PutByIdVariant::replace(currentSet, currentOffset));
+ currentOffset = offset;
+ currentSet.clear();
</ins><span class="cx"> }
</span><ins>+ currentSet.add(structure);
</ins><span class="cx"> }
</span><ins>+ data->variants.append(PutByIdVariant::replace(currentSet, currentOffset));
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+ return m_graph.addNode(
+ SpecNone,
+ MultiPutByOffset,
+ NodeOrigin(
+ base->origin.semantic,
+ where->origin.forExit),
+ OpInfo(data),
+ Edge(base, KnownCellUse),
+ value->defaultEdge());
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ case ClosureVarPLoc: {
+ return m_graph.addNode(
+ SpecNone,
+ PutClosureVar,
+ NodeOrigin(
+ base->origin.semantic,
+ where->origin.forExit),
+ OpInfo(location.info()),
+ Edge(base, KnownCellUse),
+ value->defaultEdge());
+ break;
+ }
+
</ins><span class="cx"> default:
</span><del>- DFG_CRASH(m_graph, node, "Bad materialize op");
</del><ins>+ DFG_CRASH(m_graph, base, "Bad location kind");
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ SSACalculator m_pointerSSA;
+ SSACalculator m_allocationSSA;
+ HashSet<Node*> m_sinkCandidates;
+ HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
+ HashMap<Node*, SSACalculator::Variable*> m_nodeToVariable;
+ HashMap<PromotedHeapLocation, Node*> m_localMapping;
+ HashMap<Node*, Node*> m_escapeeToMaterialization;
+ InsertionSet m_insertionSet;
</ins><span class="cx"> CombinedLiveness m_combinedLiveness;
</span><del>- SSACalculator m_ssaCalculator;
- HashSet<Node*> m_sinkCandidates;
</del><ins>+
</ins><span class="cx"> HashMap<Node*, Node*> m_materializationToEscapee;
</span><span class="cx"> HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
</span><ins>+ HashMap<Node*, Vector<PromotedHeapLocation>> m_materializationSiteToRecoveries;
+
</ins><span class="cx"> HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
</span><del>- HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
- Vector<PromotedHeapLocation> m_indexToLocation;
- HashMap<PromotedHeapLocation, Node*> m_localMapping;
- InsertionSet m_insertionSet;
</del><ins>+
+ BlockMap<LocalHeap> m_heapAtHead;
+ BlockMap<LocalHeap> m_heapAtTail;
+ LocalHeap m_heap;
+
+ Node* m_bottom = nullptr;
</ins><span class="cx"> };
</span><del>-
</del><ins>+
+}
+
</ins><span class="cx"> bool performObjectAllocationSinking(Graph& graph)
</span><span class="cx"> {
</span><span class="cx"> SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
</span><span class="lines">@@ -1162,4 +2134,3 @@
</span><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span><del>-
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhaseh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -32,10 +32,10 @@
</span><span class="cx">
</span><span class="cx"> class Graph;
</span><span class="cx">
</span><del>-// Sinks object allocations down to their uses. This will sink the allocations over OSR exits, by
-// replacing all stores to those objects with store hints so that OSR exit can materialize the
-// object. This may sink allocations past returns, creating control flow paths along which the
-// objects are not allocated at all. Replaces all uses of the objects' fields with SSA data flow.
</del><ins>+// Eliminates allocations allocations that are never used except
+// locally. This will insert phantom allocations and store hints so
+// that OSR exit can materialize the objects. Replaces all uses of the
+// objects' fields with SSA data flow. This phase is able to handle cyclic allocation graphs.
</ins><span class="cx">
</span><span class="cx"> bool performObjectAllocationSinking(Graph&);
</span><span class="cx">
</span><span class="lines">@@ -44,4 +44,3 @@
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span><span class="cx">
</span><span class="cx"> #endif // DFGObjectAllocationSinkingPhase_h
</span><del>-
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPromotedHeapLocationh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -57,8 +57,16 @@
</span><span class="cx"> , m_info(info)
</span><span class="cx"> {
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ PromotedLocationDescriptor(WTF::HashTableDeletedValueType)
+ : m_kind(InvalidPromotedLocationKind)
+ , m_info(1)
+ {
+ }
+
</ins><span class="cx"> bool operator!() const { return m_kind == InvalidPromotedLocationKind; }
</span><ins>+
+ explicit operator bool() const { return !!*this; }
</ins><span class="cx">
</span><span class="cx"> PromotedLocationKind kind() const { return m_kind; }
</span><span class="cx"> unsigned info() const { return m_info; }
</span><span class="lines">@@ -86,6 +94,18 @@
</span><span class="cx"> {
</span><span class="cx"> return m_kind == InvalidPromotedLocationKind && m_info;
</span><span class="cx"> }
</span><ins>+
+ bool neededForMaterialization() const
+ {
+ switch (kind()) {
+ case NamedPropertyPLoc:
+ case ClosureVarPLoc:
+ return false;
+
+ default:
+ return true;
+ }
+ }
</ins><span class="cx">
</span><span class="cx"> void dump(PrintStream& out) const;
</span><span class="cx">
</span><span class="lines">@@ -94,6 +114,12 @@
</span><span class="cx"> unsigned m_info;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+struct PromotedLocationDescriptorHash {
+ static unsigned hash(const PromotedLocationDescriptor& key) { return key.hash(); }
+ static bool equal(const PromotedLocationDescriptor& a, const PromotedLocationDescriptor& b) { return a == b; }
+ static const bool safeToCompareToEmptyOrDeleted = true;
+};
+
</ins><span class="cx"> class PromotedHeapLocation {
</span><span class="cx"> public:
</span><span class="cx"> PromotedHeapLocation(
</span><span class="lines">@@ -176,6 +202,16 @@
</span><span class="cx"> static const bool emptyValueIsZero = false;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+template<typename T> struct DefaultHash;
+template<> struct DefaultHash<JSC::DFG::PromotedLocationDescriptor> {
+ typedef JSC::DFG::PromotedLocationDescriptorHash Hash;
+};
+
+template<typename T> struct HashTraits;
+template<> struct HashTraits<JSC::DFG::PromotedLocationDescriptor> : SimpleClassHashTraits<JSC::DFG::PromotedLocationDescriptor> {
+ static const bool emptyValueIsZero = false;
+};
+
</ins><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGValidatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -528,12 +528,42 @@
</span><span class="cx"> case Phantom:
</span><span class="cx"> VALIDATE((node), !"bad node type for SSA");
</span><span class="cx"> break;
</span><del>-
</del><ins>+
</ins><span class="cx"> default:
</span><span class="cx"> // FIXME: Add more things here.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=123471
</span><span class="cx"> break;
</span><span class="cx"> }
</span><ins>+ switch (node->op()) {
+ case PhantomNewObject:
+ case PhantomNewFunction:
+ case PhantomCreateActivation:
+ case PhantomDirectArguments:
+ case PhantomClonedArguments:
+ case MovHint:
+ case Upsilon:
+ case ForwardVarargs:
+ case CallForwardVarargs:
+ case ConstructForwardVarargs:
+ case GetMyArgumentByVal:
+ break;
+
+ case Check:
+ // FIXME: This is probably not correct.
+ break;
+
+ case PutHint:
+ VALIDATE((node), node->child1()->isPhantomAllocation());
+ break;
+
+ default:
+ m_graph.doToChildren(
+ node,
+ [&] (const Edge& edge) {
+ VALIDATE((node), !edge->isPhantomAllocation());
+ });
+ break;
+ }
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -5287,12 +5287,7 @@
</span><span class="cx"> for (unsigned i = 0; i < data.m_properties.size(); ++i)
</span><span class="cx"> values.append(lowJSValue(m_graph.varArgChild(m_node, 1 + i)));
</span><span class="cx">
</span><del>- StructureSet set;
- m_interpreter.phiChildren()->forAllTransitiveIncomingValues(
- m_graph.varArgChild(m_node, 0).node(),
- [&] (Node* incoming) {
- set.add(incoming->castConstant<Structure*>());
- });
</del><ins>+ const StructureSet& set = m_node->structureSet();
</ins><span class="cx">
</span><span class="cx"> Vector<LBasicBlock, 1> blocks(set.size());
</span><span class="cx"> for (unsigned i = set.size(); i--;)
</span><span class="lines">@@ -5391,10 +5386,11 @@
</span><span class="cx">
</span><span class="cx"> Vector<LValue, 8> values;
</span><span class="cx"> for (unsigned i = 0; i < data.m_properties.size(); ++i)
</span><del>- values.append(lowJSValue(m_graph.varArgChild(m_node, 1 + i)));
</del><ins>+ values.append(lowJSValue(m_graph.varArgChild(m_node, 2 + i)));
</ins><span class="cx">
</span><del>- LValue scope = lowCell(m_graph.varArgChild(m_node, 0));
</del><ins>+ LValue scope = lowCell(m_graph.varArgChild(m_node, 1));
</ins><span class="cx"> SymbolTable* table = m_node->castOperand<SymbolTable*>();
</span><ins>+ ASSERT(table == m_graph.varArgChild(m_node, 0)->castConstant<SymbolTable*>());
</ins><span class="cx"> Structure* structure = m_graph.globalObjectFor(m_node->origin.semantic)->activationStructure();
</span><span class="cx">
</span><span class="cx"> LBasicBlock slowPath = FTL_NEW_BLOCK(m_out, ("MaterializeCreateActivation slow path"));
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLOSRExitCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -220,24 +220,24 @@
</span><span class="cx"> jit.or32(GPRInfo::regT2, MacroAssembler::AbsoluteAddress(arrayProfile->addressOfArrayModes()));
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> if (!!exit.m_valueProfile)
</span><span class="cx"> jit.store64(GPRInfo::regT0, exit.m_valueProfile.getSpecFailBucket(0));
</span><span class="cx"> }
</span><del>-
- // Materialize all objects. Don't materialize an object until all of the objects it needs
- // have been materialized. Curiously, this is the only place that we have an algorithm that prevents
- // OSR exit from handling cyclic object materializations. Of course, object allocation sinking
- // currently wouldn't recognize a cycle as being sinkable - but if it did then the only thing that
- // would ahve to change is this fixpoint. Instead we would allocate the objects first and populate
- // them with data later.
</del><ins>+
+ // Materialize all objects. Don't materialize an object until all
+ // of the objects it needs have been materialized. We break cycles
+ // by populating objects late - we only consider an object as
+ // needing another object if the later is needed for the
+ // allocation of the former.
+
</ins><span class="cx"> HashSet<ExitTimeObjectMaterialization*> toMaterialize;
</span><span class="cx"> for (ExitTimeObjectMaterialization* materialization : exit.m_materializations)
</span><span class="cx"> toMaterialize.add(materialization);
</span><del>-
</del><ins>+
</ins><span class="cx"> while (!toMaterialize.isEmpty()) {
</span><span class="cx"> unsigned previousToMaterializeSize = toMaterialize.size();
</span><del>-
</del><ins>+
</ins><span class="cx"> Vector<ExitTimeObjectMaterialization*> worklist;
</span><span class="cx"> worklist.appendRange(toMaterialize.begin(), toMaterialize.end());
</span><span class="cx"> for (ExitTimeObjectMaterialization* materialization : worklist) {
</span><span class="lines">@@ -246,20 +246,28 @@
</span><span class="cx"> for (ExitPropertyValue value : materialization->properties()) {
</span><span class="cx"> if (!value.value().isObjectMaterialization())
</span><span class="cx"> continue;
</span><ins>+ if (!value.location().neededForMaterialization())
+ continue;
</ins><span class="cx"> if (toMaterialize.contains(value.value().objectMaterialization())) {
</span><del>- // Gotta skip this one, since one of its fields points to a materialization
- // that hasn't been materialized.
</del><ins>+ // Gotta skip this one, since it needs a
+ // materialization that hasn't been materialized.
</ins><span class="cx"> allGood = false;
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> if (!allGood)
</span><span class="cx"> continue;
</span><del>-
- // All systems go for materializing the object. First we recover the values of all of
- // its fields and then we call a function to actually allocate the beast.
</del><ins>+
+ // All systems go for materializing the object. First we
+ // recover the values of all of its fields and then we
+ // call a function to actually allocate the beast.
+ // We only recover the fields that are needed for the allocation.
</ins><span class="cx"> for (unsigned propertyIndex = materialization->properties().size(); propertyIndex--;) {
</span><del>- const ExitValue& value = materialization->properties()[propertyIndex].value();
</del><ins>+ const ExitPropertyValue& property = materialization->properties()[propertyIndex];
+ const ExitValue& value = property.value();
+ if (!property.location().neededForMaterialization())
+ continue;
+
</ins><span class="cx"> compileRecovery(
</span><span class="cx"> jit, value, record, jitCode->stackmaps, registerScratch,
</span><span class="cx"> materializationToPointer);
</span><span class="lines">@@ -273,7 +281,7 @@
</span><span class="cx"> jit.move(CCallHelpers::TrustedImmPtr(bitwise_cast<void*>(operationMaterializeObjectInOSR)), GPRInfo::nonArgGPR0);
</span><span class="cx"> jit.call(GPRInfo::nonArgGPR0);
</span><span class="cx"> jit.storePtr(GPRInfo::returnValueGPR, materializationToPointer.get(materialization));
</span><del>-
</del><ins>+
</ins><span class="cx"> // Let everyone know that we're done.
</span><span class="cx"> toMaterialize.remove(materialization);
</span><span class="cx"> }
</span><span class="lines">@@ -284,6 +292,27 @@
</span><span class="cx"> RELEASE_ASSERT(toMaterialize.size() < previousToMaterializeSize);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Now that all the objects have been allocated, we populate them
+ // with the correct values. This time we can recover all the
+ // fields, including those that are only needed for the allocation.
+ for (ExitTimeObjectMaterialization* materialization : exit.m_materializations) {
+ for (unsigned propertyIndex = materialization->properties().size(); propertyIndex--;) {
+ const ExitValue& value = materialization->properties()[propertyIndex].value();
+ compileRecovery(
+ jit, value, record, jitCode->stackmaps, registerScratch,
+ materializationToPointer);
+ jit.storePtr(GPRInfo::regT0, materializationArguments + propertyIndex);
+ }
+
+ // This call assumes that we don't pass arguments on the stack
+ jit.setupArgumentsWithExecState(
+ CCallHelpers::TrustedImmPtr(materialization),
+ CCallHelpers::TrustedImmPtr(materializationToPointer.get(materialization)),
+ CCallHelpers::TrustedImmPtr(materializationArguments));
+ jit.move(CCallHelpers::TrustedImmPtr(bitwise_cast<void*>(operationPopulateObjectInOSR)), GPRInfo::nonArgGPR0);
+ jit.call(GPRInfo::nonArgGPR0);
+ }
+
</ins><span class="cx"> // Save all state from wherever the exit data tells us it was, into the appropriate place in
</span><span class="cx"> // the scratch buffer. This also does the reboxing.
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLOperationscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLOperations.cpp (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLOperations.cpp 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/ftl/FTLOperations.cpp 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -48,49 +48,110 @@
</span><span class="cx"> return JSFinalObject::create(exec, structure, butterfly);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+extern "C" void JIT_OPERATION operationPopulateObjectInOSR(
+ ExecState* exec, ExitTimeObjectMaterialization* materialization,
+ EncodedJSValue* encodedValue, EncodedJSValue* values)
+{
+ VM& vm = exec->vm();
+ CodeBlock* codeBlock = exec->codeBlock();
+
+ // We cannot GC. We've got pointers in evil places.
+ // FIXME: We are not doing anything that can GC here, and this is
+ // probably unnecessary.
+ DeferGCForAWhile deferGC(vm.heap);
+
+ switch (materialization->type()) {
+ case PhantomNewObject: {
+ JSFinalObject* object = jsCast<JSFinalObject*>(JSValue::decode(*encodedValue));
+ Structure* structure = object->structure();
+
+ // Figure out what the heck to populate the object with. Use
+ // getPropertiesConcurrently() because that happens to be
+ // lower-level and more convenient. It doesn't change the
+ // materialization of the property table. We want to have
+ // minimal visible effects on the system. Also, don't mind
+ // that this is O(n^2). It doesn't matter. We only get here
+ // from OSR exit.
+ for (PropertyMapEntry entry : structure->getPropertiesConcurrently()) {
+ for (unsigned i = materialization->properties().size(); i--;) {
+ const ExitPropertyValue& property = materialization->properties()[i];
+ if (property.location().kind() != NamedPropertyPLoc)
+ continue;
+ if (codeBlock->identifier(property.location().info()).impl() != entry.key)
+ continue;
+
+ object->putDirect(vm, entry.offset, JSValue::decode(values[i]));
+ }
+ }
+ break;
+ }
+
+ case PhantomNewFunction:
+ case PhantomDirectArguments:
+ case PhantomClonedArguments:
+ // Those are completely handled by operationMaterializeObjectInOSR
+ break;
+
+ case PhantomCreateActivation: {
+ JSLexicalEnvironment* activation = jsCast<JSLexicalEnvironment*>(JSValue::decode(*encodedValue));
+
+ // Figure out what to populate the activation with
+ for (unsigned i = materialization->properties().size(); i--;) {
+ const ExitPropertyValue& property = materialization->properties()[i];
+ if (property.location().kind() != ClosureVarPLoc)
+ continue;
+
+ activation->variableAt(ScopeOffset(property.location().info())).set(exec->vm(), activation, JSValue::decode(values[i]));
+ }
+
+ break;
+ }
+
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+
+ }
+}
+
</ins><span class="cx"> extern "C" JSCell* JIT_OPERATION operationMaterializeObjectInOSR(
</span><span class="cx"> ExecState* exec, ExitTimeObjectMaterialization* materialization, EncodedJSValue* values)
</span><span class="cx"> {
</span><span class="cx"> VM& vm = exec->vm();
</span><del>- CodeBlock* codeBlock = exec->codeBlock();
</del><span class="cx">
</span><span class="cx"> // We cannot GC. We've got pointers in evil places.
</span><span class="cx"> DeferGCForAWhile deferGC(vm.heap);
</span><span class="cx">
</span><span class="cx"> switch (materialization->type()) {
</span><span class="cx"> case PhantomNewObject: {
</span><del>- // First figure out what the structure is.
</del><ins>+ // Figure out what the structure is
</ins><span class="cx"> Structure* structure = nullptr;
</span><span class="cx"> for (unsigned i = materialization->properties().size(); i--;) {
</span><span class="cx"> const ExitPropertyValue& property = materialization->properties()[i];
</span><span class="cx"> if (property.location() != PromotedLocationDescriptor(StructurePLoc))
</span><span class="cx"> continue;
</span><del>-
</del><ins>+
</ins><span class="cx"> structure = jsCast<Structure*>(JSValue::decode(values[i]));
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> RELEASE_ASSERT(structure);
</span><del>-
- // Let's create that object!
</del><ins>+
</ins><span class="cx"> JSFinalObject* result = JSFinalObject::create(vm, structure);
</span><del>-
- // Now figure out what the heck to populate the object with. Use getPropertiesConcurrently()
- // because that happens to be lower-level and more convenient. It doesn't change the
- // materialization of the property table. We want to have minimal visible effects on the
- // system. Also, don't mind that this is O(n^2). It doesn't matter. We only get here from OSR
- // exit.
- for (PropertyMapEntry entry : structure->getPropertiesConcurrently()) {
- for (unsigned i = materialization->properties().size(); i--;) {
- const ExitPropertyValue& property = materialization->properties()[i];
- if (property.location().kind() != NamedPropertyPLoc)
- continue;
- if (codeBlock->identifier(property.location().info()).impl() != entry.key)
- continue;
-
- result->putDirect(vm, entry.offset, JSValue::decode(values[i]));
- }
- }
-
</del><ins>+
+ // The real values will be put subsequently by
+ // operationPopulateNewObjectInOSR. We can't fill them in
+ // now, because they may not be available yet (typically
+ // because we have a cyclic dependency graph).
+
+ // We put a dummy value here in order to avoid super-subtle
+ // GC-and-OSR-exit crashes in case we have a bug and some
+ // field is, for any reason, not filled later.
+ // We use a random-ish number instead of a sensible value like
+ // undefined to make possible bugs easier to track.
+ for (PropertyMapEntry entry : structure->getPropertiesConcurrently())
+ result->putDirect(vm, entry.offset, jsNumber(19723));
+
</ins><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -113,7 +174,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case PhantomCreateActivation: {
</span><del>- // Figure out where the scope is
</del><ins>+ // Figure out what the scope and symbol table are
</ins><span class="cx"> JSScope* scope = nullptr;
</span><span class="cx"> SymbolTable* table = nullptr;
</span><span class="cx"> for (unsigned i = materialization->properties().size(); i--;) {
</span><span class="lines">@@ -133,13 +194,17 @@
</span><span class="cx"> JSLexicalEnvironment* result = JSLexicalEnvironment::create(vm, structure, scope, table);
</span><span class="cx">
</span><span class="cx"> RELEASE_ASSERT(materialization->properties().size() - 2 == table->scopeSize());
</span><del>- // Figure out what to populate the activation with
</del><ins>+
+ // The real values will be put subsequently by
+ // operationPopulateNewObjectInOSR. See the PhantomNewObject
+ // case for details.
</ins><span class="cx"> for (unsigned i = materialization->properties().size(); i--;) {
</span><span class="cx"> const ExitPropertyValue& property = materialization->properties()[i];
</span><span class="cx"> if (property.location().kind() != ClosureVarPLoc)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- result->variableAt(ScopeOffset(property.location().info())).set(exec->vm(), result, JSValue::decode(values[i]));
</del><ins>+ result->variableAt(ScopeOffset(property.location().info())).set(
+ exec->vm(), result, jsNumber(29834));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (validationEnabled()) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLOperationsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLOperations.h (186794 => 186795)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLOperations.h 2015-07-13 23:11:05 UTC (rev 186794)
+++ trunk/Source/JavaScriptCore/ftl/FTLOperations.h 2015-07-13 23:27:30 UTC (rev 186795)
</span><span class="lines">@@ -40,6 +40,9 @@
</span><span class="cx"> JSCell* JIT_OPERATION operationMaterializeObjectInOSR(
</span><span class="cx"> ExecState*, ExitTimeObjectMaterialization*, EncodedJSValue*) WTF_INTERNAL;
</span><span class="cx">
</span><ins>+void JIT_OPERATION operationPopulateObjectInOSR(
+ ExecState*, ExitTimeObjectMaterialization*, EncodedJSValue*, EncodedJSValue*) WTF_INTERNAL;
+
</ins><span class="cx"> } // extern "C"
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre>
</div>
</div>
</body>
</html>