Diff
Modified: branches/safari-608-branch/JSTests/ChangeLog (254774 => 254775)
--- branches/safari-608-branch/JSTests/ChangeLog 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/JSTests/ChangeLog 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,106 +1,3 @@
-2020-01-13 Alan Coon <[email protected]>
-
- Cherry-pick r254349. rdar://problem/58529693
-
- 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/_javascript_Core:
-
- 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:
-
- git-svn-id: https://svn.webkit.org/repository/webkit/trunk@254349 268f45cc-cd09-0410-ab3c-d52691b4dbfc
-
- 2020-01-10 Saam Barati <[email protected]>
-
- 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.
-
- * 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):
-
2019-10-20 Babak Shafiei <[email protected]>
Cherry-pick r249538. rdar://problem/56426429
Deleted: branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-2.js (254774 => 254775)
--- branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-2.js 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-2.js 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,34 +0,0 @@
-function assert(b) {
- if (!b)
- throw new Error;
-}
-
-function v9() {
- const v14 = {};
- const v15 = {a: 42};
- v14.phantom = v15;
-
- const v17 = [1];
- v17.toString = [];
- if (!v17) {
- return 42;
- }
-
- for (const v18 of "asdf") {
- v14.b = 43;
- }
-
- const v19 = v14.phantom;
-
- let r;
- for (let i = 0; i < 2; i++) {
- r = v19;
- }
-
- return r;
-}
-noInline(v9);
-
-for (let v27 = 0; v27 < 100000; v27++) {
- assert(v9().a === 42);
-}
Deleted: branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-3.js (254774 => 254775)
--- branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-3.js 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-3.js 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,34 +0,0 @@
-function assert(b) {
- if (!b)
- throw new Error;
-}
-
-function v9() {
- const v14 = {};
- const v15 = {a: 42};
- v14.phantom = v15;
-
- const v17 = [1];
- v17.toString = [];
- if (!v17) {
- return 42;
- }
-
- for (const v18 of "asdf") {
- v14.b = 43;
- }
-
- const v19 = v14.phantom;
-
- let r;
- for (let i = 0; i < 2; i++) {
- r = v19 == v19;
- }
-
- return r;
-}
-noInline(v9);
-
-for (let v27 = 0; v27 < 100000; v27++) {
- assert(v9() === true);
-}
Deleted: branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-4.js (254774 => 254775)
--- branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-4.js 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly-4.js 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,50 +0,0 @@
-// #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
-
-let count = 0;
-function bool() {
- ++count;
- return !!(count % 2);
-}
-noInline(bool);
-
-let o;
-function effects() { if (!o) return; o.f = 42; }
-noInline(effects);
-
-function escape(theO) { o = theO; }
-noInline(escape);
-
-function bar() {
- let o = {};
- let o2 = {};
- let p;
- for (let i = 0; i < 10; ++i) {
- o.f = o2;
- effects();
- let x = o.f;
- escape(o);
- if (bool())
- continue;
- p = x;
- }
- return p;
-}
-noInline(bar);
-
-for (let i = 0; i < 10000; ++i) {
- if (bar() !== 42)
- throw new Error;
-}
Deleted: branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly.js (254774 => 254775)
--- branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly.js 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/JSTests/stress/allocation-sinking-must-model-allocation-pointers-properly.js 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,51 +0,0 @@
-function alwaysFalse() { return false; }
-noInline(alwaysFalse);
-
-let count = 0;
-function sometimesZero() {
- count++;
- if (count % 3 === 0) {
- return 0;
- }
- return 1;
-}
-noInline(sometimesZero);
-
-function assert(b) {
- if (!b)
- throw new Error;
-}
-
-function v9() {
- const v14 = {};
- const v15 = {a: 1337};
- v14.phantom = v15;
-
- if (alwaysFalse())
- return 42;
-
- for (const v18 of "asdf") {
- v14.b = 43;
- }
-
- const v15Shadow = v14.phantom;
-
- let r;
- for (let i = 0; i < sometimesZero(); i++) {
- r = v15Shadow;
- }
-
- return r;
-}
-noInline(v9);
-
-let previousResult = v9();
-for (let v27 = 0; v27 < 100000; v27++) {
- let r = v9();
- if (typeof previousResult === "undefined") {
- assert(typeof r === "object");
- assert(r.a === 1337);
- } else
- assert(typeof r === "undefined");
- previousResult = r;
-}
Modified: branches/safari-608-branch/Source/_javascript_Core/ChangeLog (254774 => 254775)
--- branches/safari-608-branch/Source/_javascript_Core/ChangeLog 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/Source/_javascript_Core/ChangeLog 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,135 +1,3 @@
-2020-01-13 Alan Coon <[email protected]>
-
- Cherry-pick r254349. rdar://problem/58529693
-
- 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/_javascript_Core:
-
- 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:
-
- git-svn-id: https://svn.webkit.org/repository/webkit/trunk@254349 268f45cc-cd09-0410-ab3c-d52691b4dbfc
-
- 2020-01-10 Saam Barati <[email protected]>
-
- 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.
-
- 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:
-
2019-12-03 Alan Coon <[email protected]>
Cherry-pick r252674. rdar://problem/57609333
Modified: branches/safari-608-branch/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp (254774 => 254775)
--- branches/safari-608-branch/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2020-01-18 00:26:55 UTC (rev 254774)
+++ branches/safari-608-branch/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2020-01-18 00:27:34 UTC (rev 254775)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015-2020 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2018 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -392,7 +392,7 @@
Node* follow(Node* node) const
{
auto iter = m_pointers.find(node);
- ASSERT(iter == m_pointers.end() || (!iter->value || m_allocations.contains(iter->value)));
+ ASSERT(iter == m_pointers.end() || m_allocations.contains(iter->value));
return iter == m_pointers.end() ? nullptr : iter->value;
}
@@ -489,70 +489,7 @@
}
}
- {
- // 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);
- }
- }
- }
- }
+ mergePointerSets(m_pointers, other.m_pointers, toEscape);
for (Node* identifier : toEscape)
escapeAllocation(identifier);
@@ -587,8 +524,8 @@
// Pointers should point to an actual allocation
for (const auto& entry : m_pointers) {
- if (entry.value)
- ASSERT(m_allocations.contains(entry.value));
+ ASSERT_UNUSED(entry, entry.value);
+ ASSERT(m_allocations.contains(entry.value));
}
for (const auto& allocationEntry : m_allocations) {
@@ -618,6 +555,11 @@
return m_allocations;
}
+ const HashMap<Node*, Node*>& pointers() const
+ {
+ return m_pointers;
+ }
+
void dump(PrintStream& out) const
{
out.print(" Allocations:\n");
@@ -624,13 +566,8 @@
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, " => #");
- if (entry.value)
- out.print(entry.value, "\n");
- else
- out.print("TOP\n");
- }
+ for (const auto& entry : m_pointers)
+ out.print(" ", entry.key, " => #", entry.value, "\n");
}
bool reached() const
@@ -724,10 +661,8 @@
void prune()
{
NodeSet reachable;
- for (const auto& entry : m_pointers) {
- if (entry.value)
- reachable.addVoid(entry.value);
- }
+ for (const auto& entry : m_pointers)
+ reachable.addVoid(entry.value);
// Repeatedly mark as reachable allocations in fields of other
// reachable allocations
@@ -865,7 +800,7 @@
// live pointer, or (recursively) stored in a field of
// a live allocation.
//
- // This means we can accidentally leak non-dominating
+ // 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
@@ -874,17 +809,8 @@
// trigger an escape and get pruned during the merge.
m_heap.pruneByLiveness(m_combinedLiveness.liveAtTail[block]);
- 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];
+ for (BasicBlock* successorBlock : block->successors())
m_heapAtHead[successorBlock].merge(m_heap);
- if (heap != m_heapAtHead[successorBlock])
- changed = true;
- }
}
} while (changed);
}
