Changeset 274539 in webkit

Timestamp:

Mar 16, 2021, 5:23:06 PM (5 years ago)

Author:

sbarati@apple.com

Message:

Object allocation sinking phase should prioritize materializations with no dependencies before materializations with no reverse dependencies
​https://bugs.webkit.org/show_bug.cgi?id=221069
<rdar://problem/73686589>

Reviewed by Yusuke Suzuki.

JSTests:

• stress/allocation-sinking-scope-materialization-order.js: Added.

(var3.var2.x):
(var3):

Source/JavaScriptCore:

Suppose we have two scope objects, A and B. Let's say A points to B, so B is
A's parent scope. A then depends on B. B has no dependencies here. When deciding
an order to materialize scope objects, we should always do it in reverse dependency
order. So above, we should materialize B, then A.

Inside object allocation sinking phase, when at an object materialization
site, we do track both dependencies and reverse dependencies. In the above
object graph, we'd attempt to materialize the objects in the right order,
always picking things with no dependencies first (and updating the list of
dependencies as we materialzed objects).

The code was using an std::list to track things to materialize, and it had
notions for materializing something first, and materializing something last.
However, there was a bug in how the code managed to insert things when
it first inserted last followed by inserting first. This patch simplifies
the code and makes it do the right thing.

• dfg/DFGObjectAllocationSinkingPhase.cpp:

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/allocation-sinking-scope-materialization-order.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp (modified) (3 diffs)

trunk/JSTests/ChangeLog

@@ +1 @@
+2021-03-16  Saam Barati  <sbarati@apple.com>
+
+        Object allocation sinking phase should prioritize materializations with no dependencies before materializations with no reverse dependencies
+        https://bugs.webkit.org/show_bug.cgi?id=221069
+        <rdar://problem/73686589>
+
+        Reviewed by Yusuke Suzuki.
+
+        * stress/allocation-sinking-scope-materialization-order.js: Added.
+        (var3.var2.x):
+        (var3):
+
 2021-03-16  Commit Queue  <commit-queue@webkit.org>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2021-03-16  Saam Barati  <sbarati@apple.com>
+
+        Object allocation sinking phase should prioritize materializations with no dependencies before materializations with no reverse dependencies
+        https://bugs.webkit.org/show_bug.cgi?id=221069
+        <rdar://problem/73686589>
+
+        Reviewed by Yusuke Suzuki.
+
+        Suppose we have two scope objects, A and B. Let's say A points to B, so B is
+        A's parent scope. A then depends on B. B has no dependencies here. When deciding
+        an order to materialize scope objects, we should always do it in reverse dependency
+        order. So above, we should materialize B, then A.
+        
+        Inside object allocation sinking phase, when at an object materialization
+        site, we do track both dependencies and reverse dependencies. In the above
+        object graph, we'd attempt to materialize the objects in the right order,
+        always picking things with no dependencies first (and updating the list of
+        dependencies as we materialzed objects).
+        
+        The code was using an std::list to track things to materialize, and it had
+        notions for materializing something first, and materializing something last.
+        However, there was a bug in how the code managed to insert things when
+        it first inserted last followed by inserting first. This patch simplifies
+        the code and makes it do the right thing.
+
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+
 2021-03-16  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp

@@ -1580 +1580 @@
         // materialized first - amongst the remaining unmaterialized
         // nodes
-        StdList<Allocation> toMaterialize;
-        auto firstPos = toMaterialize.begin();
+        Vector<Allocation> toMaterialize;
+        toMaterialize.resize(escapees.size());
+        size_t firstIndex = 0;
+        size_t lastIndex = toMaterialize.size();
         auto materializeFirst = [&] (Allocation&& allocation) {
+            RELEASE_ASSERT(firstIndex < lastIndex);
             materialize(allocation.identifier());
-            // We need to insert *after* the current position
-            if (firstPos != toMaterialize.end())
-                ++firstPos;
-            firstPos = toMaterialize.insert(firstPos, WTFMove(allocation));
+            toMaterialize[firstIndex] = WTFMove(allocation);
+            ++firstIndex;
         };
 
@@ -1593 +1594 @@
         // materialized last - amongst the remaining unmaterialized
         // nodes
-        auto lastPos = toMaterialize.end();
         auto materializeLast = [&] (Allocation&& allocation) {
             materialize(allocation.identifier());
-            lastPos = toMaterialize.insert(lastPos, WTFMove(allocation));
+            RELEASE_ASSERT(firstIndex < lastIndex);
+            RELEASE_ASSERT(lastIndex);
+            --lastIndex;
+            toMaterialize[lastIndex] = WTFMove(allocation);
         };
 
@@ -1654 +1657 @@
                 escapees.remove(identifier);
         }
+
+        RELEASE_ASSERT(firstIndex == lastIndex);
 
         materialized.clear();