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.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@186795 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
index 7041799..0e7faf9 100644
--- a/Source/JavaScriptCore/ChangeLog
+++ b/Source/JavaScriptCore/ChangeLog
@@ -1,3 +1,82 @@
+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):
+
2015-07-13 Daniel Bates <dabates@apple.com>
Cleanup: Avoid extraneous increment and decrement of reference count of ScriptArguments in ConsoleClient
diff --git a/Source/JavaScriptCore/dfg/DFGGraph.h b/Source/JavaScriptCore/dfg/DFGGraph.h
index e19ad1f..b6f2c6b 100644
--- a/Source/JavaScriptCore/dfg/DFGGraph.h
+++ b/Source/JavaScriptCore/dfg/DFGGraph.h
@@ -325,7 +325,6 @@
StructureSet* addStructureSet(const StructureSet& structureSet)
{
- ASSERT(structureSet.size());
m_structureSet.append(structureSet);
return &m_structureSet.last();
}
diff --git a/Source/JavaScriptCore/dfg/DFGLazyNode.cpp b/Source/JavaScriptCore/dfg/DFGLazyNode.cpp
index 954ed98..c8d0940 100644
--- a/Source/JavaScriptCore/dfg/DFGLazyNode.cpp
+++ b/Source/JavaScriptCore/dfg/DFGLazyNode.cpp
@@ -38,8 +38,7 @@
if (isNode())
out.print("LazyNode:@", asNode()->index());
else
- out.print("LazyNode:FrozenValue:", Graph::opName(op()), ", ", pointerDump(asValue()));
- out.print(")");
+ out.print("LazyNode:FrozenValue(", Graph::opName(op()), ", ", pointerDump(asValue()), ")");
}
}
diff --git a/Source/JavaScriptCore/dfg/DFGNode.h b/Source/JavaScriptCore/dfg/DFGNode.h
index 9ca2cdc..50ba1dd 100644
--- a/Source/JavaScriptCore/dfg/DFGNode.h
+++ b/Source/JavaScriptCore/dfg/DFGNode.h
@@ -1293,13 +1293,7 @@
FrozenValue* cellOperand()
{
ASSERT(hasCellOperand());
- switch (op()) {
- case MaterializeCreateActivation:
- return reinterpret_cast<FrozenValue*>(m_opInfo2);
- default:
- return reinterpret_cast<FrozenValue*>(m_opInfo);
- }
- RELEASE_ASSERT_NOT_REACHED();
+ return reinterpret_cast<FrozenValue*>(m_opInfo);
}
template<typename T>
@@ -1359,6 +1353,7 @@
switch (op()) {
case CheckStructure:
case CheckStructureImmediate:
+ case MaterializeNewObject:
return true;
default:
return false;
@@ -1444,7 +1439,7 @@
ObjectMaterializationData& objectMaterializationData()
{
ASSERT(hasObjectMaterializationData());
- return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo);
+ return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo2);
}
bool isObjectAllocation()
diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
index ff5fd95..8c8419a 100644
--- a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
@@ -32,7 +32,6 @@
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
-#include "DFGPromoteHeapAccess.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
diff --git a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp b/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
index 422382f..fce6520 100644
--- a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -20,7 +20,7 @@
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
@@ -28,77 +28,687 @@
#if ENABLE(DFG_JIT)
-#include "DFGAbstractHeap.h"
#include "DFGBlockMapInlines.h"
-#include "DFGClobberize.h"
#include "DFGCombinedLiveness.h"
#include "DFGGraph.h"
-#include "DFGInsertOSRHintsForUpdate.h"
#include "DFGInsertionSet.h"
+#include "DFGLazyNode.h"
#include "DFGLivenessAnalysisPhase.h"
#include "DFGOSRAvailabilityAnalysisPhase.h"
#include "DFGPhase.h"
-#include "DFGPromoteHeapAccess.h"
+#include "DFGPromotedHeapLocation.h"
#include "DFGSSACalculator.h"
#include "DFGValidate.h"
#include "JSCInlines.h"
+#include <list>
+
namespace JSC { namespace DFG {
-static bool verbose = false;
+namespace {
+
+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;
+};
class ObjectAllocationSinkingPhase : public Phase {
public:
ObjectAllocationSinkingPhase(Graph& graph)
- : Phase(graph, "object allocation sinking")
- , m_ssaCalculator(graph)
+ : Phase(graph, "object allocation elimination")
+ , m_pointerSSA(graph)
+ , m_allocationSSA(graph)
, m_insertionSet(graph)
{
}
-
+
bool run()
{
+ ASSERT(m_graph.m_form == SSA);
ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
-
- 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
-
+
if (!performSinking())
return false;
-
- while (performSinking()) { }
-
+
if (verbose) {
- dataLog("Graph after sinking:\n");
+ dataLog("Graph after elimination:\n");
m_graph.dump();
}
-
+
return true;
}
@@ -106,759 +716,277 @@
bool performSinking()
{
m_graph.computeRefCounts();
+ m_graph.initializeNodeOwners();
performLivenessAnalysis(m_graph);
performOSRAvailabilityAnalysis(m_graph);
m_combinedLiveness = CombinedLiveness(m_graph);
-
+
CString graphBeforeSinking;
if (Options::verboseValidationFailure() && Options::validateGraphAtEachPhase()) {
StringPrintStream out;
m_graph.dump(out);
graphBeforeSinking = out.toCString();
}
-
+
if (verbose) {
- dataLog("Graph before sinking:\n");
+ dataLog("Graph before elimination:\n");
m_graph.dump();
}
-
- determineMaterializationPoints();
- if (m_sinkCandidates.isEmpty())
+
+ performAnalysis();
+
+ if (!determineSinkCandidates())
return false;
-
- // At this point we are committed to sinking the sinking candidates.
- placeMaterializationPoints();
- lowerNonReadingOperationsOnPhantomAllocations();
- promoteSunkenFields();
-
+
+ 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();
+
if (Options::validateGraphAtEachPhase())
validate(m_graph, DumpGraph, graphBeforeSinking);
-
- if (verbose)
- dataLog("Sinking iteration changed the graph.\n");
return true;
}
-
- void determineMaterializationPoints()
+
+ void performAnalysis()
{
- // 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);
-
+ m_heapAtHead = BlockMap<LocalHeap>(m_graph);
+ m_heapAtTail = BlockMap<LocalHeap>(m_graph);
+
bool changed;
do {
if (verbose)
- dataLog("Doing iteration of materialization point placement.\n");
+ dataLog("Doing iteration of escape analysis.\n");
changed = false;
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- HashMap<Node*, bool> materialized = materializedAtHead[block];
- if (verbose)
- dataLog(" Looking at block ", pointerDump(block), "\n");
+
+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+ m_heapAtHead[block].setReached();
+ m_heap = m_heapAtHead[block];
+
for (Node* node : *block) {
handleNode(
node,
- [&] () {
- 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;
- }
+ [] (PromotedHeapLocation, LazyNode) { },
+ [&] (PromotedHeapLocation) -> Node* {
+ return nullptr;
});
}
-
- if (verbose)
- dataLog(" Materialized at tail of ", pointerDump(block), ": ", mapDump(materialized), "\n");
-
- if (materialized == materializedAtTail[block])
+
+ if (m_heap == m_heapAtTail[block])
continue;
-
- materializedAtTail[block] = materialized;
+
+ m_heapAtTail[block] = m_heap;
changed = true;
-
- // 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);
- }
- 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;
- }
- }
+
+ 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);
-
- // Determine the sink candidates. Broadly, a sink candidate is a node that handleNode()
- // believes is sinkable, and one of the following is true:
- //
- // 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.
- //
- // 2) There exists a basic block at the tail of which the node is not materialized and the
- // node is dead.
- //
- // 3) The sum of execution counts of the materializations is less than the sum of
- // execution counts of the original node.
- //
- // We currently implement only rule #2.
- // FIXME: Implement the two other rules.
- // https://bugs.webkit.org/show_bug.cgi?id=137073 (rule #1)
- // https://bugs.webkit.org/show_bug.cgi?id=137074 (rule #3)
-
- 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.
- //
- // FIXME: This can create duplicate allocations when we really only needed to perform one.
- // For example:
- //
- // var o = new Object();
- // if (rare) {
- // if (stuff)
- // call(o); // o escapes here.
- // return;
- // }
- // // o doesn't escape down here.
- //
- // 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);
-
- handleNode(
- node,
- [&] () { },
- [&] (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");
- return;
- }
-
- if (!materialized.add(escapee).isNewEntry) {
- if (verbose)
- dataLog(" It's already materialized.\n");
- return;
- }
-
- createMaterialize(escapee, node);
- });
- }
- }
-
- // Second pass: find CFG edge materialization points.
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- 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)
- continue;
-
- // 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;
- }
- }
-
- 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());
- }
- }
- }
- }
-
- void placeMaterializationPoints()
- {
- 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);
- }
-
- 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);
- }
- }
- }
-
- 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());
-
- mapping.set(originalNode, phiDef->value());
- }
-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
-
- 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);
- }
-
- 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));
- });
- }
- }
-
- 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());
- }
- }
-
- m_insertionSet.execute(block);
- }
-
- // 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.
- }
-
- void lowerNonReadingOperationsOnPhantomAllocations()
- {
- // 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;
- }
-
- 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;
- }
-
- 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;
- }
-
- 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));
-
- {
- 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));
- }
- }
-
- node->convertToPhantomCreateActivation();
- }
- break;
- }
-
- 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);
- }
- }
-
- void promoteSunkenFields()
- {
- // Collect the set of heap locations that we will be operating over.
- HashSet<PromotedHeapLocation> locations;
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- for (Node* node : *block) {
- promoteHeapAccess(
- node,
- [&] (PromotedHeapLocation location, Edge) {
- if (m_sinkCandidates.contains(location.base()))
- locations.add(location);
- },
- [&] (PromotedHeapLocation location) {
- if (m_sinkCandidates.contains(location.base()))
- locations.add(location);
- });
- }
- }
-
- // Figure out which locations belong to which allocations.
- m_locationsForAllocation.clear();
- for (PromotedHeapLocation location : locations) {
- auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>());
- ASSERT(!result.iterator->value.contains(location));
- result.iterator->value.append(location);
- }
-
- // 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);
- }
-
- m_ssaCalculator.reset();
-
- // Collect the set of "variables" that we will be sinking.
- m_locationToVariable.clear();
- m_indexToLocation.clear();
- for (PromotedHeapLocation location : locations) {
- SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
- m_locationToVariable.add(location, variable);
- ASSERT(m_indexToLocation.size() == variable->index());
- m_indexToLocation.append(location);
- }
-
- // Create Defs from the existing hints.
- for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
- for (Node* node : *block) {
- promoteHeapAccess(
- node,
- [&] (PromotedHeapLocation location, Edge value) {
- if (!m_sinkCandidates.contains(location.base()))
- return;
- SSACalculator::Variable* variable = m_locationToVariable.get(location);
- m_ssaCalculator.newDef(variable, block, value.node());
- },
- [&] (PromotedHeapLocation) { });
- }
- }
-
- // OMG run the SSA calculator to create Phis!
- m_ssaCalculator.computePhis(
- [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
- PromotedHeapLocation location = m_indexToLocation[variable->index()];
- if (!m_combinedLiveness.liveAtHead[block].contains(location.base()))
- return nullptr;
-
- Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
- phiNode->mergeFlags(NodeResultJS);
- return phiNode;
- });
-
- // Place Phis in the right places, replace all uses of any load with the appropriate
- // value, and create the appropriate Upsilon nodes.
- m_graph.clearReplacements();
- for (BasicBlock* block : m_graph.blocksInPreOrder()) {
- // 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.
- m_localMapping.clear();
-
- // 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());
- }
-
- if (verbose)
- dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n");
-
- // 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(
- node,
- [&] (PromotedHeapLocation location, Edge value) {
- if (m_sinkCandidates.contains(location.base()))
- m_localMapping.set(location, value.node());
- },
- [&] (PromotedHeapLocation location) {
- if (m_sinkCandidates.contains(location.base())) {
- switch (node->op()) {
- case CheckStructure:
- node->convertToCheckStructureImmediate(resolve(block, location));
- break;
-
- default:
- node->replaceWith(resolve(block, location));
- break;
- }
- }
- });
- }
-
- // Gotta drop some Upsilons.
- NodeAndIndex terminal = block->findTerminal();
- size_t upsilonInsertionPoint = terminal.index;
- NodeOrigin upsilonOrigin = terminal.node->origin;
- for (BasicBlock* successorBlock : block->successors()) {
- for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
- Node* phiNode = phiDef->value();
- SSACalculator::Variable* variable = phiDef->variable();
- PromotedHeapLocation location = m_indexToLocation[variable->index()];
- Node* incoming = resolve(block, location);
-
- m_insertionSet.insertNode(
- upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
- OpInfo(phiNode), incoming->defaultEdge());
- }
- }
-
- m_insertionSet.execute(block);
- }
- }
-
- Node* resolve(BasicBlock* block, PromotedHeapLocation location)
- {
- if (Node* result = m_localMapping.get(location))
- return result;
-
- // This implies that there is no local mapping. Find a non-local mapping.
- SSACalculator::Def* def = m_ssaCalculator.nonLocalReachingDef(
- block, m_locationToVariable.get(location));
- ASSERT(def);
- ASSERT(def->value());
- m_localMapping.add(location, def->value());
- return def->value();
}
- template<typename SinkCandidateFunctor, typename EscapeFunctor>
+ template<typename WriteFunctor, typename ResolveFunctor>
void handleNode(
Node* node,
- const SinkCandidateFunctor& sinkCandidate,
- const EscapeFunctor& escape)
+ 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:
- case MaterializeNewObject:
- case MaterializeCreateActivation:
- sinkCandidate();
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- escape(edge.node());
- });
+ target = &m_heap.newAllocation(node, Allocation::Kind::Object);
+ target->setStructures(node->structure());
+ writes.add(
+ StructurePLoc, LazyNode(m_graph.freeze(node->structure())));
break;
- case NewFunction:
- if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
+ 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);
+ }
+ }
+ 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 CreateActivation:
- if (!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
+ 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:
@@ -867,189 +995,928 @@
[&] (Edge edge) {
if (edge.willNotHaveCheck())
return;
-
+
if (alreadyChecked(edge.useKind(), SpecObject))
return;
-
- escape(edge.node());
+
+ m_heap.escape(edge.node());
});
break;
case MovHint:
case PutHint:
- break;
-
- 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;
- }
-
- case GetClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- break;
- }
-
- case PutClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- escape(node->child2().node());
- break;
- }
-
- case GetScope: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
- }
-
- case GetExecutable: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
- }
-
- 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());
+ // Handled by OSR availability analysis
break;
default:
m_graph.doToChildren(
node,
[&] (Edge edge) {
- escape(edge.node());
+ 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();
}
-
- Node* createMaterialize(Node* escapee, Node* where)
+
+ bool determineSinkCandidates()
{
- Node* result = nullptr;
-
- switch (escapee->op()) {
- case NewObject:
- case MaterializeNewObject: {
+ 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:
+ //
+ // 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.
+ //
+ // 2) There exists a basic block at the tail of which the node
+ // is dead and not materialized.
+ //
+ // 3) The sum of execution counts of the materializations is
+ // less than the sum of execution counts of the original
+ // node.
+ //
+ // We currently implement only rule #2.
+ // FIXME: Implement the two other rules.
+ // https://bugs.webkit.org/show_bug.cgi?id=137073 (rule #1)
+ // https://bugs.webkit.org/show_bug.cgi?id=137074 (rule #3)
+ //
+ // 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:
+ //
+ // 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.
+ //
+ // 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) {
+ handleNode(
+ node,
+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!value.isNode())
+ return;
+
+ 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;
+ });
+ }
+
+ // 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);
+ }
+ }
+
+ // 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
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ 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())
+ continue;
+
+ bool mustEscape = false;
+ for (BasicBlock* successorBlock : block->successors()) {
+ if (!m_heapAtHead[successorBlock].isAllocation(entry.key)
+ || m_heapAtHead[successorBlock].getAllocation(entry.key).isEscapedAllocation())
+ mustEscape = true;
+ }
+
+ if (mustEscape)
+ escapingOnEdge.add(entry.key, entry.value);
+ }
+ placeMaterializations(WTF::move(escapingOnEdge), block->terminal());
+ }
+ }
+
+ return hasUnescapedReads || !m_sinkCandidates.isEmpty();
+ }
+
+ void placeMaterializations(HashMap<Node*, Allocation> escapees, Node* where)
+ {
+ // 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);
+ }
+ 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);
+ }
+ }
+ }
+
+ // 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);
+ }
+ dependencies.remove(identifier);
+ reverseDependencies.remove(identifier);
+ forMaterialization.remove(identifier);
+ };
+
+ // 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;
+ }
+
+ if (reverseDependencies.find(entry.key)->value.isEmpty()) {
+ materializeLast(WTF::move(entry.value));
+ continue;
+ }
+ }
+
+ // 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;
+ }
+ }
+ RELEASE_ASSERT(maxEvaluation > 0);
+
+ materializeFirst(WTF::move(*bestAllocation));
+ }
+ RELEASE_ASSERT(!materialized.isEmpty());
+
+ for (Node* identifier : materialized)
+ escapees.remove(identifier);
+ }
+
+ 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);
+ }
+ }
+
+ Node* createMaterialization(const Allocation& allocation, Node* where)
+ {
+ // 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();
-
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeNewObject,
+ StructureSet* set = m_graph.addStructureSet(allocation.structures());
+
+ return m_graph.addNode(
+ allocation.identifier()->prediction(), Node::VarArg, MaterializeNewObject,
NodeOrigin(
- escapee->origin.semantic,
+ allocation.identifier()->origin.semantic,
where->origin.forExit),
- OpInfo(data), OpInfo(), 0, 0);
+ OpInfo(set), OpInfo(data), 0, 0);
+ }
+
+ case Allocation::Kind::Function: {
+ FrozenValue* executable = allocation.identifier()->cellOperand();
+
+ return m_graph.addNode(
+ allocation.identifier()->prediction(), NewFunction,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(executable));
break;
}
- 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: {
+ case Allocation::Kind::Activation: {
ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
- FrozenValue* symbolTable = escapee->cellOperand();
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
+ FrozenValue* symbolTable = allocation.identifier()->cellOperand();
+
+ return m_graph.addNode(
+ allocation.identifier()->prediction(), Node::VarArg, MaterializeCreateActivation,
NodeOrigin(
- escapee->origin.semantic,
+ allocation.identifier()->origin.semantic,
where->origin.forExit),
- OpInfo(data), OpInfo(symbolTable), 0, 0);
- break;
+ OpInfo(symbolTable), OpInfo(data), 0, 0);
}
default:
- DFG_CRASH(m_graph, escapee, "Bad escapee op");
- break;
+ DFG_CRASH(m_graph, allocation.identifier(), "Bad allocation kind");
}
-
- 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);
-
+ }
+
+ void promoteLocalHeap()
+ {
+ // Collect the set of heap locations that we will be operating
+ // over.
+ HashSet<PromotedHeapLocation> locations;
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ m_heap = m_heapAtHead[block];
+
+ for (Node* node : *block) {
+ handleNode(
+ node,
+ [&] (PromotedHeapLocation location, LazyNode) {
+ // If the location is not on a sink candidate,
+ // we only sink it if it is read
+ if (m_sinkCandidates.contains(location.base()))
+ locations.add(location);
+ },
+ [&] (PromotedHeapLocation location) -> Node* {
+ locations.add(location);
+ return nullptr;
+ });
+ }
+ }
+
+ // Figure out which locations belong to which allocations.
+ m_locationsForAllocation.clear();
+ for (PromotedHeapLocation location : locations) {
+ auto result = m_locationsForAllocation.add(
+ location.base(),
+ Vector<PromotedHeapLocation>());
+ ASSERT(!result.iterator->value.contains(location));
+ result.iterator->value.append(location);
+ }
+
+ m_pointerSSA.reset();
+ m_allocationSSA.reset();
+
+ // Collect the set of "variables" that we will be sinking.
+ m_locationToVariable.clear();
+ 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);
+ }
+
+ for (PromotedHeapLocation location : locations) {
+ SSACalculator::Variable* variable = m_pointerSSA.newVariable();
+ m_locationToVariable.add(location, variable);
+ ASSERT(indexToLocation.size() == variable->index());
+ indexToLocation.append(location);
+ }
+
+ // 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));
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ 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(
+ node,
+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!locations.contains(location))
+ return;
+
+ 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);
+ }
+ }
+
+ SSACalculator::Variable* variable = m_locationToVariable.get(location);
+ m_pointerSSA.newDef(variable, block, nodeValue);
+ },
+ [] (PromotedHeapLocation) -> Node* {
+ return nullptr;
+ });
+ }
+ }
+ m_insertionSet.execute(m_graph.block(0));
+
+ // Run the SSA calculators to create Phis
+ m_pointerSSA.computePhis(
+ [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
+ PromotedHeapLocation location = indexToLocation[variable->index()];
+
+ // Don't create Phi nodes for fields of dead allocations
+ if (!m_heapAtHead[block].isAllocation(location.base()))
+ return nullptr;
+
+ // 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;
+
+ Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+ phiNode->mergeFlags(NodeResultJS);
+ return phiNode;
+ });
+
+ 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;
+ });
+
+ // Place Phis in the right places, replace all uses of any load with the appropriate
+ // value, and create the materialization nodes.
+ LocalOSRAvailabilityCalculator availabilityCalculator;
+ m_graph.clearReplacements();
+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+ 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).
+ m_localMapping.clear();
+ 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()));
+ }
+ }
+
+ 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) {
+ dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n");
+ 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(
+ node,
+ [&] (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));
+ },
+ [&] (PromotedHeapLocation location) -> Node* {
+ return resolve(block, location);
+ });
+
+ 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()));
+ });
+ }
+
+ // Gotta drop some Upsilons.
+ NodeAndIndex terminal = block->findTerminal();
+ size_t upsilonInsertionPoint = terminal.index;
+ NodeOrigin upsilonOrigin = terminal.node->origin;
+ for (BasicBlock* successorBlock : block->successors()) {
+ for (SSACalculator::Def* phiDef : m_pointerSSA.phisForBlock(successorBlock)) {
+ Node* phiNode = phiDef->value();
+ SSACalculator::Variable* variable = phiDef->variable();
+ PromotedHeapLocation location = indexToLocation[variable->index()];
+ Node* incoming = resolve(block, location);
+
+ m_insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
+ OpInfo(phiNode), incoming->defaultEdge());
+ }
+
+ 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());
+ }
+ }
+
+ m_insertionSet.execute(block);
+ }
+ }
+
+ Node* resolve(BasicBlock* block, PromotedHeapLocation location)
+ {
+ // 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);
+
+ if (Node* result = m_localMapping.get(location))
+ return result;
+
+ // This implies that there is no local mapping. Find a non-local mapping.
+ SSACalculator::Def* def = m_pointerSSA.nonLocalReachingDef(
+ block, m_locationToVariable.get(location));
+ ASSERT(def);
+ ASSERT(def->value());
+
+ Node* result = def->value();
+
+ ASSERT(!result->replacement());
+
+ m_localMapping.add(location, result);
return result;
}
-
- void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
+
+ Node* resolve(BasicBlock* block, Node* node)
{
+ // 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);
+
+ if (node->replacement())
+ node = node->replacement();
+ ASSERT(!node->replacement());
+
+ return node;
+ }
+
+ Node* getMaterialization(BasicBlock* block, Node* identifier)
+ {
+ ASSERT(m_heap.isAllocation(identifier));
+ if (!m_sinkCandidates.contains(identifier))
+ return identifier;
+
+ if (Node* materialization = m_escapeeToMaterialization.get(identifier))
+ return materialization;
+
+ 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();
+ }
+
+ 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;
+
+ m_insertionSet.insert(
+ nodeIndex, entry.key.createHint(m_graph, origin, materialization));
+ }
+
+ 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;
+
+ int operand = availability.m_locals.operandForIndex(i);
+ m_insertionSet.insertNode(
+ nodeIndex, SpecNone, MovHint, origin, OpInfo(operand),
+ materialization->defaultEdge());
+ }
+ }
+
+ void populateMaterialization(BasicBlock* block, Node* node, Node* escapee)
+ {
+ Allocation& allocation = m_heap.getAllocation(escapee);
switch (node->op()) {
case MaterializeNewObject: {
ObjectMaterializationData& data = node->objectMaterializationData();
unsigned firstChild = m_graph.m_varArgChildren.size();
-
+
Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
-
- PromotedHeapLocation structure(StructurePLoc, escapee);
+
+ PromotedHeapLocation structure(StructurePLoc, allocation.identifier());
ASSERT(locations.contains(structure));
-
+
m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse));
-
- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
- case StructurePLoc: {
- ASSERT(locations[i] == structure);
+
+ for (PromotedHeapLocation location : locations) {
+ switch (location.kind()) {
+ case StructurePLoc:
+ ASSERT(location == structure);
break;
- }
-
+
case NamedPropertyPLoc: {
- 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);
+ 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);
break;
}
-
+
default:
DFG_CRASH(m_graph, node, "Bad location kind");
}
}
-
+
node->children = AdjacencyList(
AdjacencyList::Variable,
firstChild, m_graph.m_varArgChildren.size() - firstChild);
@@ -1063,31 +1930,35 @@
Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
- PromotedHeapLocation scope(ActivationScopePLoc, escapee);
- PromotedHeapLocation symbolTable(ActivationSymbolTablePLoc, escapee);
- ASSERT(locations.contains(scope));
+ 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());
+ ASSERT(locations.contains(scope));
m_graph.m_varArgChildren.append(Edge(resolve(block, scope), KnownCellUse));
- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
+ for (PromotedHeapLocation location : locations) {
+ switch (location.kind()) {
case ActivationScopePLoc: {
- ASSERT(locations[i] == scope);
+ ASSERT(location == scope);
break;
}
case ActivationSymbolTablePLoc: {
- ASSERT(locations[i] == symbolTable);
+ ASSERT(location == symbolTable);
break;
}
case ClosureVarPLoc: {
- 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);
+ 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);
break;
}
@@ -1103,56 +1974,157 @@
}
case NewFunction: {
- if (!ASSERT_DISABLED) {
- Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
+ Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
+ ASSERT(locations.size() == 2);
- ASSERT(locations.size() == 2);
+ PromotedHeapLocation executable(FunctionExecutablePLoc, allocation.identifier());
+ ASSERT_UNUSED(executable, locations.contains(executable));
- PromotedHeapLocation executable(FunctionExecutablePLoc, escapee);
- ASSERT(locations.contains(executable));
+ PromotedHeapLocation activation(FunctionActivationPLoc, allocation.identifier());
+ ASSERT(locations.contains(activation));
- PromotedHeapLocation activation(FunctionActivationPLoc, escapee);
- ASSERT(locations.contains(activation));
-
- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
- case FunctionExecutablePLoc: {
- ASSERT(locations[i] == executable);
- break;
- }
-
- case FunctionActivationPLoc: {
- ASSERT(locations[i] == activation);
- break;
- }
-
- default:
- DFG_CRASH(m_graph, node, "Bad location kind");
- }
- }
- }
-
+ node->child1() = Edge(resolve(block, activation), KnownCellUse);
break;
}
default:
DFG_CRASH(m_graph, node, "Bad materialize op");
+ }
+ }
+
+ 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);
+
+ 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();
+ }
+ currentSet.add(structure);
+ }
+ data->variants.append(PutByIdVariant::replace(currentSet, currentOffset));
+ }
+
+ return m_graph.addNode(
+ SpecNone,
+ MultiPutByOffset,
+ NodeOrigin(
+ base->origin.semantic,
+ where->origin.forExit),
+ OpInfo(data),
+ Edge(base, KnownCellUse),
+ value->defaultEdge());
+ break;
+ }
+
+ case ClosureVarPLoc: {
+ return m_graph.addNode(
+ SpecNone,
+ PutClosureVar,
+ NodeOrigin(
+ base->origin.semantic,
+ where->origin.forExit),
+ OpInfo(location.info()),
+ Edge(base, KnownCellUse),
+ value->defaultEdge());
+ break;
+ }
+
+ default:
+ DFG_CRASH(m_graph, base, "Bad location kind");
break;
}
}
-
- CombinedLiveness m_combinedLiveness;
- SSACalculator m_ssaCalculator;
+
+ 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;
+ CombinedLiveness m_combinedLiveness;
+
HashMap<Node*, Node*> m_materializationToEscapee;
HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
+ HashMap<Node*, Vector<PromotedHeapLocation>> m_materializationSiteToRecoveries;
+
HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
- HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
- Vector<PromotedHeapLocation> m_indexToLocation;
- HashMap<PromotedHeapLocation, Node*> m_localMapping;
- InsertionSet m_insertionSet;
+
+ BlockMap<LocalHeap> m_heapAtHead;
+ BlockMap<LocalHeap> m_heapAtTail;
+ LocalHeap m_heap;
+
+ Node* m_bottom = nullptr;
};
-
+
+}
+
bool performObjectAllocationSinking(Graph& graph)
{
SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
@@ -1162,4 +2134,3 @@
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
-
diff --git a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h b/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h
index 1630f66..b400d4e 100644
--- a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h
+++ b/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -32,10 +32,10 @@
class Graph;
-// 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.
+// 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.
bool performObjectAllocationSinking(Graph&);
@@ -44,4 +44,3 @@
#endif // ENABLE(DFG_JIT)
#endif // DFGObjectAllocationSinkingPhase_h
-
diff --git a/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h b/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h
index bc15158..a21e4da 100644
--- a/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h
+++ b/Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h
@@ -57,8 +57,16 @@
, m_info(info)
{
}
-
+
+ PromotedLocationDescriptor(WTF::HashTableDeletedValueType)
+ : m_kind(InvalidPromotedLocationKind)
+ , m_info(1)
+ {
+ }
+
bool operator!() const { return m_kind == InvalidPromotedLocationKind; }
+
+ explicit operator bool() const { return !!*this; }
PromotedLocationKind kind() const { return m_kind; }
unsigned info() const { return m_info; }
@@ -86,6 +94,18 @@
{
return m_kind == InvalidPromotedLocationKind && m_info;
}
+
+ bool neededForMaterialization() const
+ {
+ switch (kind()) {
+ case NamedPropertyPLoc:
+ case ClosureVarPLoc:
+ return false;
+
+ default:
+ return true;
+ }
+ }
void dump(PrintStream& out) const;
@@ -94,6 +114,12 @@
unsigned m_info;
};
+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;
+};
+
class PromotedHeapLocation {
public:
PromotedHeapLocation(
@@ -176,6 +202,16 @@
static const bool emptyValueIsZero = false;
};
+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;
+};
+
} // namespace WTF
#endif // ENABLE(DFG_JIT)
diff --git a/Source/JavaScriptCore/dfg/DFGValidate.cpp b/Source/JavaScriptCore/dfg/DFGValidate.cpp
index 6578a96..0d5b468 100644
--- a/Source/JavaScriptCore/dfg/DFGValidate.cpp
+++ b/Source/JavaScriptCore/dfg/DFGValidate.cpp
@@ -528,12 +528,42 @@
case Phantom:
VALIDATE((node), !"bad node type for SSA");
break;
-
+
default:
// FIXME: Add more things here.
// https://bugs.webkit.org/show_bug.cgi?id=123471
break;
}
+ 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;
+ }
}
}
}
diff --git a/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp b/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
index 64b0abd..c9dde55 100644
--- a/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
+++ b/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
@@ -5287,12 +5287,7 @@
for (unsigned i = 0; i < data.m_properties.size(); ++i)
values.append(lowJSValue(m_graph.varArgChild(m_node, 1 + i)));
- StructureSet set;
- m_interpreter.phiChildren()->forAllTransitiveIncomingValues(
- m_graph.varArgChild(m_node, 0).node(),
- [&] (Node* incoming) {
- set.add(incoming->castConstant<Structure*>());
- });
+ const StructureSet& set = m_node->structureSet();
Vector<LBasicBlock, 1> blocks(set.size());
for (unsigned i = set.size(); i--;)
@@ -5391,10 +5386,11 @@
Vector<LValue, 8> values;
for (unsigned i = 0; i < data.m_properties.size(); ++i)
- values.append(lowJSValue(m_graph.varArgChild(m_node, 1 + i)));
+ values.append(lowJSValue(m_graph.varArgChild(m_node, 2 + i)));
- LValue scope = lowCell(m_graph.varArgChild(m_node, 0));
+ LValue scope = lowCell(m_graph.varArgChild(m_node, 1));
SymbolTable* table = m_node->castOperand<SymbolTable*>();
+ ASSERT(table == m_graph.varArgChild(m_node, 0)->castConstant<SymbolTable*>());
Structure* structure = m_graph.globalObjectFor(m_node->origin.semantic)->activationStructure();
LBasicBlock slowPath = FTL_NEW_BLOCK(m_out, ("MaterializeCreateActivation slow path"));
diff --git a/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp b/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp
index 27788e7..1650143 100644
--- a/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp
+++ b/Source/JavaScriptCore/ftl/FTLOSRExitCompiler.cpp
@@ -220,24 +220,24 @@
jit.or32(GPRInfo::regT2, MacroAssembler::AbsoluteAddress(arrayProfile->addressOfArrayModes()));
}
}
-
+
if (!!exit.m_valueProfile)
jit.store64(GPRInfo::regT0, exit.m_valueProfile.getSpecFailBucket(0));
}
-
- // 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.
+
+ // 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.
+
HashSet<ExitTimeObjectMaterialization*> toMaterialize;
for (ExitTimeObjectMaterialization* materialization : exit.m_materializations)
toMaterialize.add(materialization);
-
+
while (!toMaterialize.isEmpty()) {
unsigned previousToMaterializeSize = toMaterialize.size();
-
+
Vector<ExitTimeObjectMaterialization*> worklist;
worklist.appendRange(toMaterialize.begin(), toMaterialize.end());
for (ExitTimeObjectMaterialization* materialization : worklist) {
@@ -246,20 +246,28 @@
for (ExitPropertyValue value : materialization->properties()) {
if (!value.value().isObjectMaterialization())
continue;
+ if (!value.location().neededForMaterialization())
+ continue;
if (toMaterialize.contains(value.value().objectMaterialization())) {
- // Gotta skip this one, since one of its fields points to a materialization
- // that hasn't been materialized.
+ // Gotta skip this one, since it needs a
+ // materialization that hasn't been materialized.
allGood = false;
break;
}
}
if (!allGood)
continue;
-
- // 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.
+
+ // 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.
for (unsigned propertyIndex = materialization->properties().size(); propertyIndex--;) {
- const ExitValue& value = materialization->properties()[propertyIndex].value();
+ const ExitPropertyValue& property = materialization->properties()[propertyIndex];
+ const ExitValue& value = property.value();
+ if (!property.location().neededForMaterialization())
+ continue;
+
compileRecovery(
jit, value, record, jitCode->stackmaps, registerScratch,
materializationToPointer);
@@ -273,7 +281,7 @@
jit.move(CCallHelpers::TrustedImmPtr(bitwise_cast<void*>(operationMaterializeObjectInOSR)), GPRInfo::nonArgGPR0);
jit.call(GPRInfo::nonArgGPR0);
jit.storePtr(GPRInfo::returnValueGPR, materializationToPointer.get(materialization));
-
+
// Let everyone know that we're done.
toMaterialize.remove(materialization);
}
@@ -284,6 +292,27 @@
RELEASE_ASSERT(toMaterialize.size() < previousToMaterializeSize);
}
+ // 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);
+ }
+
// Save all state from wherever the exit data tells us it was, into the appropriate place in
// the scratch buffer. This also does the reboxing.
diff --git a/Source/JavaScriptCore/ftl/FTLOperations.cpp b/Source/JavaScriptCore/ftl/FTLOperations.cpp
index 4e5c8b3..4c38373 100644
--- a/Source/JavaScriptCore/ftl/FTLOperations.cpp
+++ b/Source/JavaScriptCore/ftl/FTLOperations.cpp
@@ -48,37 +48,30 @@
return JSFinalObject::create(exec, structure, butterfly);
}
-extern "C" JSCell* JIT_OPERATION operationMaterializeObjectInOSR(
- ExecState* exec, ExitTimeObjectMaterialization* materialization, EncodedJSValue* values)
+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: {
- // First figure out what the structure is.
- Structure* structure = nullptr;
- for (unsigned i = materialization->properties().size(); i--;) {
- const ExitPropertyValue& property = materialization->properties()[i];
- if (property.location() != PromotedLocationDescriptor(StructurePLoc))
- continue;
-
- structure = jsCast<Structure*>(JSValue::decode(values[i]));
- break;
- }
- RELEASE_ASSERT(structure);
-
- // Let's create that object!
- JSFinalObject* result = JSFinalObject::create(vm, structure);
-
- // 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.
+ 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];
@@ -86,11 +79,79 @@
continue;
if (codeBlock->identifier(property.location().info()).impl() != entry.key)
continue;
-
- result->putDirect(vm, entry.offset, JSValue::decode(values[i]));
+
+ 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;
+
+ }
+}
+
+extern "C" JSCell* JIT_OPERATION operationMaterializeObjectInOSR(
+ ExecState* exec, ExitTimeObjectMaterialization* materialization, EncodedJSValue* values)
+{
+ VM& vm = exec->vm();
+
+ // We cannot GC. We've got pointers in evil places.
+ DeferGCForAWhile deferGC(vm.heap);
+ switch (materialization->type()) {
+ case PhantomNewObject: {
+ // Figure out what the structure is
+ Structure* structure = nullptr;
+ for (unsigned i = materialization->properties().size(); i--;) {
+ const ExitPropertyValue& property = materialization->properties()[i];
+ if (property.location() != PromotedLocationDescriptor(StructurePLoc))
+ continue;
+
+ structure = jsCast<Structure*>(JSValue::decode(values[i]));
+ break;
+ }
+ RELEASE_ASSERT(structure);
+
+ JSFinalObject* result = JSFinalObject::create(vm, structure);
+
+ // 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));
+
return result;
}
@@ -113,7 +174,7 @@
}
case PhantomCreateActivation: {
- // Figure out where the scope is
+ // Figure out what the scope and symbol table are
JSScope* scope = nullptr;
SymbolTable* table = nullptr;
for (unsigned i = materialization->properties().size(); i--;) {
@@ -133,13 +194,17 @@
JSLexicalEnvironment* result = JSLexicalEnvironment::create(vm, structure, scope, table);
RELEASE_ASSERT(materialization->properties().size() - 2 == table->scopeSize());
- // Figure out what to populate the activation with
+
+ // The real values will be put subsequently by
+ // operationPopulateNewObjectInOSR. See the PhantomNewObject
+ // case for details.
for (unsigned i = materialization->properties().size(); i--;) {
const ExitPropertyValue& property = materialization->properties()[i];
if (property.location().kind() != ClosureVarPLoc)
continue;
- result->variableAt(ScopeOffset(property.location().info())).set(exec->vm(), result, JSValue::decode(values[i]));
+ result->variableAt(ScopeOffset(property.location().info())).set(
+ exec->vm(), result, jsNumber(29834));
}
if (validationEnabled()) {
diff --git a/Source/JavaScriptCore/ftl/FTLOperations.h b/Source/JavaScriptCore/ftl/FTLOperations.h
index d15f18e..a5568f9 100644
--- a/Source/JavaScriptCore/ftl/FTLOperations.h
+++ b/Source/JavaScriptCore/ftl/FTLOperations.h
@@ -40,6 +40,9 @@
JSCell* JIT_OPERATION operationMaterializeObjectInOSR(
ExecState*, ExitTimeObjectMaterialization*, EncodedJSValue*) WTF_INTERNAL;
+void JIT_OPERATION operationPopulateObjectInOSR(
+ ExecState*, ExitTimeObjectMaterialization*, EncodedJSValue*, EncodedJSValue*) WTF_INTERNAL;
+
} // extern "C"
} } // namespace JSC::DFG
