summaryrefslogtreecommitdiff
path: root/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
diff options
context:
space:
mode:
authorLorry Tar Creator <lorry-tar-importer@lorry>2015-05-20 09:56:07 +0000
committerLorry Tar Creator <lorry-tar-importer@lorry>2015-05-20 09:56:07 +0000
commit41386e9cb918eed93b3f13648cbef387e371e451 (patch)
treea97f9d7bd1d9d091833286085f72da9d83fd0606 /Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
parente15dd966d523731101f70ccf768bba12435a0208 (diff)
downloadWebKitGtk-tarball-41386e9cb918eed93b3f13648cbef387e371e451.tar.gz
webkitgtk-2.4.9webkitgtk-2.4.9
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp')
-rw-r--r--Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp2136
1 files changed, 0 insertions, 2136 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp b/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
deleted file mode 100644
index fd88910e5..000000000
--- a/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
+++ /dev/null
@@ -1,2136 +0,0 @@
-/*
- * 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
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * 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.
- */
-
-#include "config.h"
-#include "DFGObjectAllocationSinkingPhase.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBlockMapInlines.h"
-#include "DFGCombinedLiveness.h"
-#include "DFGGraph.h"
-#include "DFGInsertionSet.h"
-#include "DFGLazyNode.h"
-#include "DFGLivenessAnalysisPhase.h"
-#include "DFGOSRAvailabilityAnalysisPhase.h"
-#include "DFGPhase.h"
-#include "DFGPromotedHeapLocation.h"
-#include "DFGSSACalculator.h"
-#include "DFGValidate.h"
-#include "JSCInlines.h"
-
-#include <list>
-
-namespace JSC { namespace DFG {
-
-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 elimination")
- , m_pointerSSA(graph)
- , m_allocationSSA(graph)
- , m_insertionSet(graph)
- {
- }
-
- bool run()
- {
- ASSERT(m_graph.m_form == SSA);
- ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
-
- if (!performSinking())
- return false;
-
- if (verbose) {
- dataLog("Graph after elimination:\n");
- m_graph.dump();
- }
-
- return true;
- }
-
-private:
- 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 elimination:\n");
- m_graph.dump();
- }
-
- performAnalysis();
-
- if (!determineSinkCandidates())
- return false;
-
- 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);
- return true;
- }
-
- void performAnalysis()
- {
- m_heapAtHead = BlockMap<LocalHeap>(m_graph);
- m_heapAtTail = BlockMap<LocalHeap>(m_graph);
-
- bool changed;
- do {
- if (verbose)
- dataLog("Doing iteration of escape analysis.\n");
- changed = false;
-
- for (BasicBlock* block : m_graph.blocksInPreOrder()) {
- m_heapAtHead[block].setReached();
- m_heap = m_heapAtHead[block];
-
- for (Node* node : *block) {
- handleNode(
- node,
- [] (PromotedHeapLocation, LazyNode) { },
- [&] (PromotedHeapLocation) -> Node* {
- return nullptr;
- });
- }
-
- if (m_heap == m_heapAtTail[block])
- continue;
-
- m_heapAtTail[block] = m_heap;
- changed = true;
-
- m_heap.assertIsValid();
-
- // We keep only pointers that are live, and only
- // allocations that are either live, pointed to by a
- // live pointer, or (recursively) stored in a field of
- // a live allocation.
- //
- // This means we can accidentaly leak non-dominating
- // nodes into the successor. However, due to the
- // non-dominance property, we are guaranteed that the
- // successor has at least one predecessor that is not
- // dominated either: this means any reference to a
- // non-dominating allocation in the successor will
- // trigger an escape and get pruned during the merge.
- m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
-
- for (BasicBlock* successorBlock : block->successors())
- m_heapAtHead[successorBlock].merge(m_heap);
- }
- } while (changed);
- }
-
- template<typename WriteFunctor, typename ResolveFunctor>
- void handleNode(
- Node* node,
- const WriteFunctor& heapWrite,
- const ResolveFunctor& heapResolve)
- {
- m_heap.assertIsValid();
- ASSERT(m_heap.takeEscapees().isEmpty());
-
- Allocation* target = nullptr;
- HashMap<PromotedLocationDescriptor, LazyNode> writes;
- PromotedLocationDescriptor exactRead;
-
- switch (node->op()) {
- case NewObject:
- target = &m_heap.newAllocation(node, Allocation::Kind::Object);
- target->setStructures(node->structure());
- writes.add(
- StructurePLoc, LazyNode(m_graph.freeze(node->structure())));
- break;
-
- case MaterializeNewObject: {
- target = &m_heap.newAllocation(node, Allocation::Kind::Object);
- target->setStructures(node->structureSet());
- writes.add(
- StructurePLoc, LazyNode(m_graph.varArgChild(node, 0).node()));
- for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
- writes.add(
- PromotedLocationDescriptor(
- NamedPropertyPLoc,
- node->objectMaterializationData().m_properties[i].m_identifierNumber),
- LazyNode(m_graph.varArgChild(node, i + 1).node()));
- }
- break;
- }
-
- case NewFunction: {
- if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid()) {
- m_heap.escape(node->child1().node());
- break;
- }
- target = &m_heap.newAllocation(node, Allocation::Kind::Function);
- writes.add(FunctionExecutablePLoc, LazyNode(node->cellOperand()));
- writes.add(FunctionActivationPLoc, LazyNode(node->child1().node()));
- break;
- }
-
- case CreateActivation: {
- if (node->castOperand<SymbolTable*>()->singletonScope()->isStillValid()) {
- m_heap.escape(node->child1().node());
- break;
- }
- target = &m_heap.newAllocation(node, Allocation::Kind::Activation);
- writes.add(ActivationSymbolTablePLoc, LazyNode(node->cellOperand()));
- writes.add(ActivationScopePLoc, LazyNode(node->child1().node()));
- {
- SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
- ConcurrentJITLocker locker(symbolTable->m_lock);
- LazyNode initialValue(m_graph.freeze(node->initializationValueForActivation()));
- for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
- writes.add(
- PromotedLocationDescriptor(ClosureVarPLoc, iter->value.scopeOffset().offset()),
- initialValue);
- }
- }
- break;
- }
-
- case MaterializeCreateActivation: {
- // We have sunk this once already - there is no way the
- // watchpoint is still valid.
- ASSERT(!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid());
- target = &m_heap.newAllocation(node, Allocation::Kind::Activation);
- writes.add(ActivationSymbolTablePLoc, LazyNode(m_graph.varArgChild(node, 0).node()));
- writes.add(ActivationScopePLoc, LazyNode(m_graph.varArgChild(node, 1).node()));
- for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
- writes.add(
- PromotedLocationDescriptor(
- ClosureVarPLoc,
- node->objectMaterializationData().m_properties[i].m_identifierNumber),
- LazyNode(m_graph.varArgChild(node, i + 2).node()));
- }
- break;
- }
-
- case PutStructure:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isObjectAllocation()) {
- writes.add(StructurePLoc, LazyNode(m_graph.freeze(JSValue(node->transition()->next))));
- target->setStructures(node->transition()->next);
- } else
- m_heap.escape(node->child1().node());
- break;
-
- case CheckStructure: {
- Allocation* allocation = m_heap.onlyLocalAllocation(node->child1().node());
- if (allocation && allocation->isObjectAllocation()) {
- allocation->filterStructures(node->structureSet());
- if (Node* value = heapResolve(PromotedHeapLocation(allocation->identifier(), StructurePLoc)))
- node->convertToCheckStructureImmediate(value);
- } else
- m_heap.escape(node->child1().node());
- break;
- }
-
- case GetByOffset:
- case GetGetterSetterByOffset:
- target = m_heap.onlyLocalAllocation(node->child2().node());
- if (target && target->isObjectAllocation()) {
- unsigned identifierNumber = node->storageAccessData().identifierNumber;
- exactRead = PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber);
- } else {
- m_heap.escape(node->child1().node());
- m_heap.escape(node->child2().node());
- }
- break;
-
- case MultiGetByOffset:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isObjectAllocation()) {
- unsigned identifierNumber = node->multiGetByOffsetData().identifierNumber;
- exactRead = PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber);
- } else
- m_heap.escape(node->child1().node());
- break;
-
- case PutByOffset:
- target = m_heap.onlyLocalAllocation(node->child2().node());
- if (target && target->isObjectAllocation()) {
- unsigned identifierNumber = node->storageAccessData().identifierNumber;
- writes.add(
- PromotedLocationDescriptor(NamedPropertyPLoc, identifierNumber),
- LazyNode(node->child3().node()));
- } else {
- m_heap.escape(node->child1().node());
- m_heap.escape(node->child2().node());
- m_heap.escape(node->child3().node());
- }
- break;
-
- case GetClosureVar:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isActivationAllocation()) {
- exactRead =
- PromotedLocationDescriptor(ClosureVarPLoc, node->scopeOffset().offset());
- } else
- m_heap.escape(node->child1().node());
- break;
-
- case PutClosureVar:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isActivationAllocation()) {
- writes.add(
- PromotedLocationDescriptor(ClosureVarPLoc, node->scopeOffset().offset()),
- LazyNode(node->child2().node()));
- } else {
- m_heap.escape(node->child1().node());
- m_heap.escape(node->child2().node());
- }
- break;
-
- case SkipScope:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isActivationAllocation())
- exactRead = ActivationScopePLoc;
- else
- m_heap.escape(node->child1().node());
- break;
-
- case GetExecutable:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isFunctionAllocation())
- exactRead = FunctionExecutablePLoc;
- else
- m_heap.escape(node->child1().node());
- break;
-
- case GetScope:
- target = m_heap.onlyLocalAllocation(node->child1().node());
- if (target && target->isFunctionAllocation())
- exactRead = FunctionActivationPLoc;
- else
- m_heap.escape(node->child1().node());
- break;
-
- case Check:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- if (edge.willNotHaveCheck())
- return;
-
- if (alreadyChecked(edge.useKind(), SpecObject))
- return;
-
- m_heap.escape(edge.node());
- });
- break;
-
- case MovHint:
- case PutHint:
- // Handled by OSR availability analysis
- break;
-
- default:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- m_heap.escape(edge.node());
- });
- break;
- }
-
- if (exactRead) {
- ASSERT(target);
- ASSERT(writes.isEmpty());
- if (Node* value = heapResolve(PromotedHeapLocation(target->identifier(), exactRead))) {
- ASSERT(!value->replacement());
- node->replaceWith(value);
- }
- Node* identifier = target->get(exactRead);
- if (identifier)
- m_heap.newPointer(node, identifier);
- }
-
- for (auto entry : writes) {
- ASSERT(target);
- if (entry.value.isNode())
- target->set(entry.key, m_heap.follow(entry.value.asNode()));
- else
- target->remove(entry.key);
- heapWrite(PromotedHeapLocation(target->identifier(), entry.key), entry.value);
- }
-
- m_heap.assertIsValid();
- }
-
- bool determineSinkCandidates()
- {
- m_sinkCandidates.clear();
- m_materializationToEscapee.clear();
- m_materializationSiteToMaterializations.clear();
- m_materializationSiteToRecoveries.clear();
-
- // Logically we wish to consider every allocation and sink
- // it. However, it is probably not profitable to sink an
- // allocation that will always escape. So, we only sink an
- // allocation if one of the following is true:
- //
- // 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();
- StructureSet* set = m_graph.addStructureSet(allocation.structures());
-
- return m_graph.addNode(
- allocation.identifier()->prediction(), Node::VarArg, MaterializeNewObject,
- NodeOrigin(
- allocation.identifier()->origin.semantic,
- where->origin.forExit),
- 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 Allocation::Kind::Activation: {
- ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
- FrozenValue* symbolTable = allocation.identifier()->cellOperand();
-
- return m_graph.addNode(
- allocation.identifier()->prediction(), Node::VarArg, MaterializeCreateActivation,
- NodeOrigin(
- allocation.identifier()->origin.semantic,
- where->origin.forExit),
- OpInfo(symbolTable), OpInfo(data), 0, 0);
- }
-
- default:
- DFG_CRASH(m_graph, allocation.identifier(), "Bad allocation kind");
- }
- }
-
- 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;
- }
-
- 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, allocation.identifier());
- ASSERT(locations.contains(structure));
-
- m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse));
-
- for (PromotedHeapLocation location : locations) {
- switch (location.kind()) {
- case StructurePLoc:
- ASSERT(location == structure);
- break;
-
- case NamedPropertyPLoc: {
- 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);
- break;
- }
-
- case MaterializeCreateActivation: {
- ObjectMaterializationData& data = node->objectMaterializationData();
-
- unsigned firstChild = m_graph.m_varArgChildren.size();
-
- Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
-
- 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 (PromotedHeapLocation location : locations) {
- switch (location.kind()) {
- case ActivationScopePLoc: {
- ASSERT(location == scope);
- break;
- }
-
- case ActivationSymbolTablePLoc: {
- ASSERT(location == symbolTable);
- break;
- }
-
- case ClosureVarPLoc: {
- 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);
- break;
- }
-
- case NewFunction: {
- Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
- ASSERT(locations.size() == 2);
-
- PromotedHeapLocation executable(FunctionExecutablePLoc, allocation.identifier());
- ASSERT_UNUSED(executable, locations.contains(executable));
-
- PromotedHeapLocation activation(FunctionActivationPLoc, allocation.identifier());
- ASSERT(locations.contains(activation));
-
- 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;
- }
- }
-
- 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;
-
- 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");
- return runPhase<ObjectAllocationSinkingPhase>(graph);
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
View Lorry Controller Status