Changeset 254349 in webkit for trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp

Timestamp:

Jan 10, 2020, 10:49:51 AM (5 years ago)

Author:

[email protected]

Message:

ObjectAllocationSinkingPhase doesn't model pointers to allocations in control flow properly
​https://bugs.webkit.org/show_bug.cgi?id=204738
<rdar://problem/57553238>

Reviewed by Yusuke Suzuki.

JSTests:

• stress/allocation-sinking-must-model-allocation-pointers-properly-2.js: Added.

(assert):
(v9):

• stress/allocation-sinking-must-model-allocation-pointers-properly-3.js: Added.

(assert):
(v9):

• stress/allocation-sinking-must-model-allocation-pointers-properly-4.js: Added.

(bool):
(effects):
(escape):
(bar):

• stress/allocation-sinking-must-model-allocation-pointers-properly.js: Added.

(alwaysFalse):
(sometimesZero):
(assert):
(v9):

Source/JavaScriptCore:

Allocation sinking phase conducts a points to analysis. It uses this
information for programs like:

`
1: NewObject
2: NewObject
3: PutByOffset(@2, @1, "x")
4: GetByOffset(@2, "x")
`

It solves the points to problem knowing @4 points to @1.

It tracks this data in the LocalHeap data structure. This is used to track
the heap across blocks, and it includes a merge function to handle control
flow merges. However, this merge function would not always merge the pointer
sets together. It sometimes would merge them together, since it had a fast
path check inside merge, which would just copy the contents of the block to be
merged with itself if it were this block's first time merging. This fast path happened
to hide the bug in general case merge code. If we didn't take this fast path,
we would just never transfer pointer sets from predecessor to successor. This
could lead to all kinds of issues, including using the incorrect phantom node
in IR instead of its materialized version. It could also lead to the phase not
sinking objects it is capable of sinking.

This patch makes it so that we merge together the pointer sets. We always add
new pointers to the set. So in pointer A->B, if the set has yet to see A, we
add it. If the set already contains pointer A->B, and we encounter a new
pointer A->C, or if we encounter a merge without any A->* pointer, we mark
the A pointer as top, marking it A->TOP. We do this to ensure that we fixpoint.
We're guaranteed that m_pointers is monotonically increasing (module liveness
pruning, which is a constant). And once something is TOP, it never becomes
anything else. (Instead of marking a pointer top, we used to just remove it
from the set, but this has issues, as it could lead to us ping-ponging in
our fixpoint analysis, add, remove, add, remove, etc.)

So the merge rules are:
{A->B} merge {A->B} => {A->B}
{A->B} merge {A->C} => {A->TOP}
{A->B} merge {A->TOP} => {A->TOP}
{A->B} merge {} => {A->TOP}


Thanks to Samuel Groß of Google Project Zero for identifying this bug.

• dfg/DFGObjectAllocationSinkingPhase.cpp:

File:

• trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp (modified) (9 diffs)

trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2015-2019 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2020 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -403 +403 @@
     {
         auto iter = m_pointers.find(node);
-        ASSERT(iter == m_pointers.end() || m_allocations.contains(iter->value));
+        ASSERT(iter == m_pointers.end() || (!iter->value || m_allocations.contains(iter->value)));
         return iter == m_pointers.end() ? nullptr : iter->value;
     }
@@ -500 +500 @@
         }
 
-        mergePointerSets(m_pointers, other.m_pointers, toEscape);
+        {
+            // This works because we won't collect all pointers until all of our predecessors
+            // merge their pointer sets with ours. That allows us to see the full state of the
+            // world during our fixpoint analysis. Once we have the full set of pointers, we
+            // only mark pointers to TOP, so we will eventually converge.
+            for (auto entry : other.m_pointers) {
+                auto addResult = m_pointers.add(entry.key, entry.value);
+                if (addResult.iterator->value != entry.value) {
+                    if (addResult.iterator->value) {
+                        toEscape.addVoid(addResult.iterator->value);
+                        addResult.iterator->value = nullptr;
+                    }
+                    if (entry.value)
+                        toEscape.addVoid(entry.value);
+                }
+            }
+            // This allows us to rule out pointers for graphs like this:
+            // bb#0
+            // branch #1, #2
+            // #1:
+            // x = pointer A
+            // jump #3
+            // #2:
+            // y = pointer B
+            // jump #3
+            // #3:
+            // ...
+            //
+            // When we merge state at #3, we'll very likely prune away the x and y pointer,
+            // since they're not live. But if they do happen to make it to this merge function, when
+            // #3 merges with #2 and #1, it'll eventually rule out x and y as not existing
+            // in the other, and therefore not existing in #3, which is the desired behavior.
+            //
+            // This also is necessary for a graph like this:
+            // #0
+            // o = {}
+            // o2 = {}
+            // jump #1
+            // 
+            // #1
+            // o.f = o2
+            // effects()
+            // x = o.f
+            // escape(o)
+            // branch #2, #1
+            // 
+            // #2
+            // x cannot be o2 here, it has to be TOP
+            // ...
+            //
+            // On the first fixpoint iteration, we might think that x is o2 at the head
+            // of #2. However, when we fixpoint our analysis, we determine that o gets
+            // escaped. This means that when we fixpoint, x will eventually not be a pointer.
+            // When we merge again here, we'll notice and mark o2 as escaped.
+            for (auto& entry : m_pointers) {
+                if (!other.m_pointers.contains(entry.key)) {
+                    if (entry.value) {
+                        toEscape.addVoid(entry.value);
+                        entry.value = nullptr;
+                        ASSERT(!m_pointers.find(entry.key)->value);
+                    }
+                }
+            }
+        }
 
         for (Node* identifier : toEscape)
@@ -535 +598 @@
         // Pointers should point to an actual allocation
         for (const auto& entry : m_pointers) {
-            ASSERT_UNUSED(entry, entry.value);
-            ASSERT(m_allocations.contains(entry.value));
+            if (entry.value)
+                ASSERT(m_allocations.contains(entry.value));
         }
 
@@ -566 +629 @@
     }
 
-    const HashMap<Node*, Node*>& pointers() const
-    {
-        return m_pointers;
-    }
-
     void dump(PrintStream& out) const
     {
@@ -577 +635 @@
             out.print("    #", entry.key, ": ", entry.value, "\n");
         out.print("  Pointers:\n");
-        for (const auto& entry : m_pointers)
-            out.print("    ", entry.key, " => #", entry.value, "\n");
+        for (const auto& entry : m_pointers) {
+            out.print("    ", entry.key, " => #");
+            if (entry.value)
+                out.print(entry.value, "\n");
+            else
+                out.print("TOP\n");
+        }
     }
 
@@ -672 +735 @@
     {
         NodeSet reachable;
-        for (const auto& entry : m_pointers)
-            reachable.addVoid(entry.value);
+        for (const auto& entry : m_pointers) {
+            if (entry.value)
+                reachable.addVoid(entry.value);
+        }
 
         // Repeatedly mark as reachable allocations in fields of other
@@ -811 +876 @@
                 // a live allocation.
                 //
-                // This means we can accidentaly leak non-dominating
+                // This means we can accidentally leak non-dominating
                 // nodes into the successor. However, due to the
                 // non-dominance property, we are guaranteed that the
@@ -820 +885 @@
                 m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
 
-                for (BasicBlock* successorBlock : block->successors())
+                for (BasicBlock* successorBlock : block->successors()) {
+                    // FIXME: Maybe we should:
+                    // 1. Store the liveness pruned heap as part of m_heapAtTail
+                    // 2. Move this code above where we make block merge with
+                    // its predecessors before walking the block forward.
+                    // https://bugs.webkit.org/show_bug.cgi?id=206041
+                    LocalHeap heap = m_heapAtHead[successorBlock];
                     m_heapAtHead[successorBlock].merge(m_heap);
+                    if (heap != m_heapAtHead[successorBlock])
+                        changed = true;
+                }
             }
         } while (changed);