/*
- * 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
* 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"
#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;
}
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:
+ }
+
+ template<typename WriteFunctor, typename ResolveFunctor>
+ void handleNode(
+ Node* node,
+ const WriteFunctor& heapWrite,
+ const ResolveFunctor& heapResolve)
+ {
+ m_heap.assertIsValid();
+ ASSERT(m_heap.takeEscapees().isEmpty());
+
+ Allocation* target = nullptr;
+ HashMap<PromotedLocationDescriptor, LazyNode> writes;
+ PromotedLocationDescriptor exactRead;
+
+ switch (node->op()) {
+ case NewObject:
+ target = &m_heap.newAllocation(node, Allocation::Kind::Object);
+ target->setStructures(node->structure());
+ writes.add(
+ StructurePLoc, LazyNode(m_graph.freeze(node->structure())));
+ break;
+
+ case MaterializeNewObject: {
+ target = &m_heap.newAllocation(node, Allocation::Kind::Object);
+ target->setStructures(node->structureSet());
+ writes.add(
+ StructurePLoc, LazyNode(m_graph.varArgChild(node, 0).node()));
+ for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
+ writes.add(
+ PromotedLocationDescriptor(
+ NamedPropertyPLoc,
+ node->objectMaterializationData().m_properties[i].m_identifierNumber),
+ LazyNode(m_graph.varArgChild(node, i + 1).node()));
+ }
+ break;
+ }
+
+ case NewFunction: {
+ if (node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid()) {
+ m_heap.escape(node->child1().node());
+ break;
+ }
+ target = &m_heap.newAllocation(node, Allocation::Kind::Function);
+ writes.add(FunctionExecutablePLoc, LazyNode(node->cellOperand()));
+ writes.add(FunctionActivationPLoc, LazyNode(node->child1().node()));
+ break;
+ }
+
+ case CreateActivation: {
+ if (node->castOperand<SymbolTable*>()->singletonScope()->isStillValid()) {
+ m_heap.escape(node->child1().node());
+ break;
+ }
+ target = &m_heap.newAllocation(node, Allocation::Kind::Activation);
+ writes.add(ActivationSymbolTablePLoc, LazyNode(node->cellOperand()));
+ writes.add(ActivationScopePLoc, LazyNode(node->child1().node()));
+ {
+ SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
+ ConcurrentJITLocker locker(symbolTable->m_lock);
+ LazyNode undefined(m_graph.freeze(jsUndefined()));
+ for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
+ writes.add(
+ PromotedLocationDescriptor(ClosureVarPLoc, iter->value.scopeOffset().offset()),
+ undefined);
+ }
+ }
+ 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 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.
+ // 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 not materialized and the
- // node is dead.
+ // 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.
+ // 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:
+ // 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:
//
- // var o = new Object();
- // if (rare) {
- // if (stuff)
- // call(o); // o escapes here.
- // return;
- // }
- // // o doesn't escape down here.
+ // 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.
//
- // 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);
-
+ // 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,
- [&] () { },
- [&] (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");
+ [&] (PromotedHeapLocation location, LazyNode value) {
+ if (!value.isNode())
return;
- }
-
- if (!materialized.add(escapee).isNewEntry) {
- if (verbose)
- dataLog(" It's already materialized.\n");
- return;
- }
-
- createMaterialize(escapee, node);
+
+ 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);
+ }
}
-
- // Second pass: find CFG edge materialization points.
+
+ if (m_sinkCandidates.isEmpty())
+ return hasUnescapedReads;
+
+ if (verbose)
+ dataLog("Candidates: ", listDump(m_sinkCandidates), "\n");
+
+ // Create the materialization nodes
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());
+ 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;
}
-
- // 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());
+
+ if (mustEscape)
+ escapingOnEdge.add(entry.key, entry.value);
}
+ placeMaterializations(WTF::move(escapingOnEdge), block->terminal());
}
}
+
+ return hasUnescapedReads || !m_sinkCandidates.isEmpty();
}
-
- void placeMaterializationPoints()
+
+ void placeMaterializations(HashMap<Node*, Allocation> escapees, Node* where)
{
- 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);
+ // 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 (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);
- }
+ 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));
}
}
-
- 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());
+
+ // 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);
+ }
}
-
- 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());
+ // 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);
}
-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
+ dependencies.remove(identifier);
+ reverseDependencies.remove(identifier);
+ forMaterialization.remove(identifier);
+ };
- 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);
+ // 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;
}
-
- 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));
- });
+
+ if (reverseDependencies.find(entry.key)->value.isEmpty()) {
+ materializeLast(WTF::move(entry.value));
+ continue;
}
}
-
- 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());
+
+ // 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));
}
-
- m_insertionSet.execute(block);
+ 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);
}
-
- // 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()
+
+ Node* createMaterialization(const Allocation& allocation, Node* where)
{
- // 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;
- }
+ // 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());
- 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;
- }
+ 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 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 Allocation::Kind::Function: {
+ FrozenValue* executable = allocation.identifier()->cellOperand();
- 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));
- }
- }
+ return m_graph.addNode(
+ allocation.identifier()->prediction(), NewFunction,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(executable));
+ break;
+ }
- node->convertToPhantomCreateActivation();
- }
- break;
- }
+ case Allocation::Kind::Activation: {
+ ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
+ FrozenValue* symbolTable = allocation.identifier()->cellOperand();
- 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;
- }
+ return m_graph.addNode(
+ allocation.identifier()->prediction(), Node::VarArg, MaterializeCreateActivation,
+ NodeOrigin(
+ allocation.identifier()->origin.semantic,
+ where->origin.forExit),
+ OpInfo(symbolTable), OpInfo(data), 0, 0);
+ }
- 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);
+ default:
+ DFG_CRASH(m_graph, allocation.identifier(), "Bad allocation kind");
}
}
-
- void promoteSunkenFields()
+
+ void promoteLocalHeap()
{
- // Collect the set of heap locations that we will be operating over.
+ // 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) {
- promoteHeapAccess(
+ handleNode(
node,
- [&] (PromotedHeapLocation location, Edge) {
+ [&] (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) {
- 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>());
+ 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();
+ m_pointerSSA.reset();
+ m_allocationSSA.reset();
// Collect the set of "variables" that we will be sinking.
m_locationToVariable.clear();
- m_indexToLocation.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_ssaCalculator.newVariable();
+ SSACalculator::Variable* variable = m_pointerSSA.newVariable();
m_locationToVariable.add(location, variable);
- ASSERT(m_indexToLocation.size() == variable->index());
- m_indexToLocation.append(location);
+ ASSERT(indexToLocation.size() == variable->index());
+ indexToLocation.append(location);
}
-
- // Create Defs from the existing hints.
+
+ // 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()) {
- for (Node* node : *block) {
- promoteHeapAccess(
+ 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, Edge value) {
- if (!m_sinkCandidates.contains(location.base()))
+ [&] (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_ssaCalculator.newDef(variable, block, value.node());
+ m_pointerSSA.newDef(variable, block, nodeValue);
},
- [&] (PromotedHeapLocation) { });
+ [] (PromotedHeapLocation) -> Node* {
+ return nullptr;
+ });
}
}
-
- // OMG run the SSA calculator to create Phis!
- m_ssaCalculator.computePhis(
+ 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* {
- PromotedHeapLocation location = m_indexToLocation[variable->index()];
- if (!m_combinedLiveness.liveAtHead[block].contains(location.base()))
+ 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 appropriate Upsilon nodes.
+ // value, and create the materialization nodes.
+ LocalOSRAvailabilityCalculator availabilityCalculator;
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_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();
-
- // 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());
+ 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()));
+ }
}
-
- if (verbose)
+
+ 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");
-
- // 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(
+ 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, Edge value) {
- if (m_sinkCandidates.contains(location.base()))
- m_localMapping.set(location, value.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) {
- if (m_sinkCandidates.contains(location.base())) {
- switch (node->op()) {
- case CheckStructure:
- node->convertToCheckStructureImmediate(resolve(block, location));
- break;
-
- default:
- node->replaceWith(resolve(block, location));
- break;
- }
- }
+ [&] (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_ssaCalculator.phisForBlock(successorBlock)) {
+ for (SSACalculator::Def* phiDef : m_pointerSSA.phisForBlock(successorBlock)) {
Node* phiNode = phiDef->value();
SSACalculator::Variable* variable = phiDef->variable();
- PromotedHeapLocation location = m_indexToLocation[variable->index()];
+ 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_ssaCalculator.nonLocalReachingDef(
+ SSACalculator::Def* def = m_pointerSSA.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>
- void handleNode(
- Node* node,
- const SinkCandidateFunctor& sinkCandidate,
- const EscapeFunctor& escape)
- {
- switch (node->op()) {
- case NewObject:
- case MaterializeNewObject:
- case MaterializeCreateActivation:
- sinkCandidate();
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- escape(edge.node());
- });
- break;
-
- case NewFunction:
- if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
- break;
-
- case CreateActivation:
- if (!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid())
- sinkCandidate();
- escape(node->child1().node());
- break;
- case Check:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- if (edge.willNotHaveCheck())
- return;
-
- if (alreadyChecked(edge.useKind(), SpecObject))
- return;
-
- escape(edge.node());
- });
- break;
+ Node* result = def->value();
- case MovHint:
- case PutHint:
- break;
+ ASSERT(!result->replacement());
- 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;
- }
+ m_localMapping.add(location, result);
+ return result;
+ }
- case GetClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- break;
- }
+ 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);
- case PutClosureVar: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- escape(node->child2().node());
- break;
- }
+ if (node->replacement())
+ node = node->replacement();
+ ASSERT(!node->replacement());
- case GetScope: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
- }
+ return node;
+ }
- case GetExecutable: {
- Node* target = node->child1().node();
- if (!target->isFunctionAllocation())
- escape(target);
- break;
- }
+ Node* getMaterialization(BasicBlock* block, Node* identifier)
+ {
+ ASSERT(m_heap.isAllocation(identifier));
+ if (!m_sinkCandidates.contains(identifier))
+ return identifier;
- case SkipScope: {
- Node* target = node->child1().node();
- if (!target->isActivationAllocation())
- escape(target);
- break;
- }
-
- case MultiPutByOffset:
- // FIXME: In the future we should be able to handle this. It's just a matter of
- // building the appropriate *Hint variant of this instruction, along with a
- // PhantomStructureSelect node - since this transforms the Structure in a conditional
- // way.
- // https://bugs.webkit.org/show_bug.cgi?id=136924
- escape(node->child1().node());
- escape(node->child2().node());
- break;
+ if (Node* materialization = m_escapeeToMaterialization.get(identifier))
+ return materialization;
- default:
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- escape(edge.node());
- });
- break;
- }
+ 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();
}
-
- Node* createMaterialize(Node* escapee, Node* where)
- {
- Node* result = nullptr;
-
- switch (escapee->op()) {
- case NewObject:
- case MaterializeNewObject: {
- ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
-
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeNewObject,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(data), OpInfo(), 0, 0);
- break;
- }
- case NewFunction:
- result = m_graph.addNode(
- escapee->prediction(), NewFunction,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(escapee->cellOperand()),
- escapee->child1());
- break;
+ 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;
- case CreateActivation:
- case MaterializeCreateActivation: {
- ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
- FrozenValue* symbolTable = escapee->cellOperand();
- result = m_graph.addNode(
- escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
- NodeOrigin(
- escapee->origin.semantic,
- where->origin.forExit),
- OpInfo(data), OpInfo(symbolTable), 0, 0);
- break;
+ m_insertionSet.insert(
+ nodeIndex, entry.key.createHint(m_graph, origin, materialization));
}
- default:
- DFG_CRASH(m_graph, escapee, "Bad escapee op");
- break;
+ 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());
}
-
- if (verbose)
- dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
-
- m_materializationToEscapee.add(result, escapee);
- m_materializationSiteToMaterializations.add(
- where, Vector<Node*>()).iterator->value.append(result);
-
- return result;
}
-
- void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
+
+ 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);
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;
}
}
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));
+ node->child1() = Edge(resolve(block, activation), KnownCellUse);
+ break;
+ }
- for (unsigned i = 0; i < locations.size(); ++i) {
- switch (locations[i].kind()) {
- case FunctionExecutablePLoc: {
- ASSERT(locations[i] == executable);
- break;
- }
+ default:
+ DFG_CRASH(m_graph, node, "Bad materialize op");
+ }
+ }
- case FunctionActivationPLoc: {
- ASSERT(locations[i] == activation);
- break;
- }
+ 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);
- default:
- DFG_CRASH(m_graph, node, "Bad location kind");
+ 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, node, "Bad materialize op");
+ 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<Node*, Node*> m_materializationToEscapee;
- HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
- HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
- Vector<PromotedHeapLocation> m_indexToLocation;
+ 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");
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
-
git://git.webkit.org / WebKit-https.git / commitdiff