- Revision
- 267114
- Author
- tzaga...@apple.com
- Date
- 2020-09-15 16:46:09 -0700 (Tue, 15 Sep 2020)
Log Message
Object allocation sinking forgets escaped nodes when structure changes
https://bugs.webkit.org/show_bug.cgi?id=216214
<rdar://problem/68518460>
Reviewed by Saam Barati.
JSTests:
* stress/allocation-sinking-changing-structures.js: Added.
(main.v4.get v4):
(main):
Source/_javascript_Core:
Consider the following program:
bb0:
a: NewObject
b: CreateActivation()
_: Branch(bb2, bb1)
bb1:
_: PutByOffset(a, 'x', 42)
_: PutStrucute(a, {x: 0})
_: Branch(bb2, bb1)
bb2:
_: CheckStructure(a, {x: 0})
_: PutClosureVar(b, 0, Kill:a)
_: Branch(bb3, bb2)
bb3:
c: GetClosureVar(b, 0)
_: PutByOffset(global, 'y', c)
_: Return
Due to the order we visit the program, we'll visit bb2 before bb1. The first time we visit bb2, heapAtHead will be:
#@a: ObjectAllocation({})
#@b: ActivationAllocation()
@a => #@a
@b => #@b
Now CheckStructure would always fail, so it will escape @a and heapAtTail will be:
#@a: EscapedAllocation()
#@b: ActivationAllocation()
@a => #@a
@b => #@b
And after pruning:
#@b: ActivationAllocation()
@b => #@b
Now, we'll visit bb3 and then bb1. When we visit bb1 we'll set the structure {x: 0} for the #@a and eventually visit bb2 again. This time around CheckStructure will no longer escape @a, since the allocation has the right structure, and heapAtTail will be:
#@a: ObjectAllocation({x: 0})
#@b: ActivationAllocation(0: #@a)
@b => #@b
However, we now have to merge into bb3, which has heapAtHead:
#@b: ActivationAllocation()
@b => #@b
Since we can't add the extra field to the activation, we'll end up escaping @a at the edge and therefore pruning #@b, which will leave the heap for bb3 unchanged.
That's a problem, since PutClosureVar didn't see the escaped object, but GetClosureVar thinks it's escaped. The materialization for @a will be placed after the
PutClosureVar, at end of bb2, when the node is already dead. When computing the SSA defs, the PutByOffset at bb3 will then see @a (which at this point will be a
PhantomNewObject) instead of its materialization.
The issue happens because we don't allow allocations to add extra fields while merging, but we do allow adding new structures. This results in different decisions
being made about what escapes in CheckStructure and MultiGetByOffset. To avoid this problem, we track two sets of structures: structures and structuresForMaterialization.
The first is used for checks and should never grow while the second is used for materialization and is allowed to grow.
* dfg/DFGObjectAllocationSinkingPhase.cpp:
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (267113 => 267114)
--- trunk/JSTests/ChangeLog 2020-09-15 23:38:23 UTC (rev 267113)
+++ trunk/JSTests/ChangeLog 2020-09-15 23:46:09 UTC (rev 267114)
@@ -1,3 +1,15 @@
+2020-09-15 Tadeu Zagallo <tzaga...@apple.com>
+
+ Object allocation sinking forgets escaped nodes when structure changes
+ https://bugs.webkit.org/show_bug.cgi?id=216214
+ <rdar://problem/68518460>
+
+ Reviewed by Saam Barati.
+
+ * stress/allocation-sinking-changing-structures.js: Added.
+ (main.v4.get v4):
+ (main):
+
2020-09-15 Saam Barati <sbar...@apple.com>
CustomFunctionEquivalence PropertyCondition needs to check if the structure has the property
Added: trunk/JSTests/stress/allocation-sinking-changing-structures.js (0 => 267114)
--- trunk/JSTests/stress/allocation-sinking-changing-structures.js (rev 0)
+++ trunk/JSTests/stress/allocation-sinking-changing-structures.js 2020-09-15 23:46:09 UTC (rev 267114)
@@ -0,0 +1,30 @@
+function main() {
+ const v1 = {};
+ const foo = {}
+ v1.p = foo;
+
+ const v3 = [1];
+ v3.toString = undefined;
+ if (!v3) {
+ v4 = {
+ get v4(){
+ v4;
+ }
+ }
+ }
+
+ for (const v5 of "a") {
+ v1.b = 43;
+ }
+
+ const v4 = v1.p;
+
+ let = String.fromCharCode("");
+ for (let i = 0; i < 2; i++) {
+ r = v4;
+ }
+}
+
+for (let v0 = 0; v0 < 100000; v0++) {
+ main();
+}
Modified: trunk/Source/_javascript_Core/ChangeLog (267113 => 267114)
--- trunk/Source/_javascript_Core/ChangeLog 2020-09-15 23:38:23 UTC (rev 267113)
+++ trunk/Source/_javascript_Core/ChangeLog 2020-09-15 23:46:09 UTC (rev 267114)
@@ -1,3 +1,65 @@
+2020-09-15 Tadeu Zagallo <tzaga...@apple.com>
+
+ Object allocation sinking forgets escaped nodes when structure changes
+ https://bugs.webkit.org/show_bug.cgi?id=216214
+ <rdar://problem/68518460>
+
+ Reviewed by Saam Barati.
+
+ Consider the following program:
+ bb0:
+ a: NewObject
+ b: CreateActivation()
+ _: Branch(bb2, bb1)
+ bb1:
+ _: PutByOffset(a, 'x', 42)
+ _: PutStrucute(a, {x: 0})
+ _: Branch(bb2, bb1)
+ bb2:
+ _: CheckStructure(a, {x: 0})
+ _: PutClosureVar(b, 0, Kill:a)
+ _: Branch(bb3, bb2)
+ bb3:
+ c: GetClosureVar(b, 0)
+ _: PutByOffset(global, 'y', c)
+ _: Return
+
+ Due to the order we visit the program, we'll visit bb2 before bb1. The first time we visit bb2, heapAtHead will be:
+ #@a: ObjectAllocation({})
+ #@b: ActivationAllocation()
+ @a => #@a
+ @b => #@b
+
+ Now CheckStructure would always fail, so it will escape @a and heapAtTail will be:
+ #@a: EscapedAllocation()
+ #@b: ActivationAllocation()
+ @a => #@a
+ @b => #@b
+
+ And after pruning:
+ #@b: ActivationAllocation()
+ @b => #@b
+
+ Now, we'll visit bb3 and then bb1. When we visit bb1 we'll set the structure {x: 0} for the #@a and eventually visit bb2 again. This time around CheckStructure will no longer escape @a, since the allocation has the right structure, and heapAtTail will be:
+ #@a: ObjectAllocation({x: 0})
+ #@b: ActivationAllocation(0: #@a)
+ @b => #@b
+
+ However, we now have to merge into bb3, which has heapAtHead:
+ #@b: ActivationAllocation()
+ @b => #@b
+
+ Since we can't add the extra field to the activation, we'll end up escaping @a at the edge and therefore pruning #@b, which will leave the heap for bb3 unchanged.
+ That's a problem, since PutClosureVar didn't see the escaped object, but GetClosureVar thinks it's escaped. The materialization for @a will be placed after the
+ PutClosureVar, at end of bb2, when the node is already dead. When computing the SSA defs, the PutByOffset at bb3 will then see @a (which at this point will be a
+ PhantomNewObject) instead of its materialization.
+
+ The issue happens because we don't allow allocations to add extra fields while merging, but we do allow adding new structures. This results in different decisions
+ being made about what escapes in CheckStructure and MultiGetByOffset. To avoid this problem, we track two sets of structures: structures and structuresForMaterialization.
+ The first is used for checks and should never grow while the second is used for materialization and is allowed to grow.
+
+ * dfg/DFGObjectAllocationSinkingPhase.cpp:
+
2020-09-15 Saam Barati <sbar...@apple.com>
CustomFunctionEquivalence PropertyCondition needs to check if the structure has the property
Modified: trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp (267113 => 267114)
--- trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2020-09-15 23:38:23 UTC (rev 267113)
+++ trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2020-09-15 23:46:09 UTC (rev 267114)
@@ -202,13 +202,16 @@
{
ASSERT(hasStructures() && !structures.isEmpty());
m_structures = structures;
+ m_structuresForMaterialization = structures;
return *this;
}
- Allocation& mergeStructures(const RegisteredStructureSet& structures)
+ Allocation& mergeStructures(const Allocation& other)
{
- ASSERT(hasStructures() || structures.isEmpty());
- m_structures.merge(structures);
+ ASSERT(hasStructures() || (other.structuresForMaterialization().isEmpty() && other.structures().isEmpty()));
+ m_structures.filter(other.structures());
+ m_structuresForMaterialization.merge(other.structuresForMaterialization());
+ ASSERT(m_structures.isSubsetOf(m_structuresForMaterialization));
return *this;
}
@@ -216,6 +219,7 @@
{
ASSERT(hasStructures());
m_structures.filter(structures);
+ m_structuresForMaterialization.filter(structures);
RELEASE_ASSERT(!m_structures.isEmpty());
return *this;
}
@@ -225,6 +229,11 @@
return m_structures;
}
+ const RegisteredStructureSet& structuresForMaterialization() const
+ {
+ return m_structuresForMaterialization;
+ }
+
Node* identifier() const { return m_identifier; }
Kind kind() const { return m_kind; }
@@ -264,7 +273,8 @@
return m_identifier == other.m_identifier
&& m_kind == other.m_kind
&& m_fields == other.m_fields
- && m_structures == other.m_structures;
+ && m_structures == other.m_structures
+ && m_structuresForMaterialization == other.m_structuresForMaterialization;
}
bool operator!=(const Allocation& other) const
@@ -317,10 +327,10 @@
break;
}
out.print("Allocation(");
- if (!m_structures.isEmpty())
- out.print(inContext(m_structures.toStructureSet(), context));
+ if (!m_structuresForMaterialization.isEmpty())
+ out.print(inContext(m_structuresForMaterialization.toStructureSet(), context));
if (!m_fields.isEmpty()) {
- if (!m_structures.isEmpty())
+ if (!m_structuresForMaterialization.isEmpty())
out.print(", ");
out.print(mapDump(m_fields, " => #", ", "));
}
@@ -331,7 +341,14 @@
Node* m_identifier; // This is the actual node that created the allocation
Kind m_kind;
Fields m_fields;
+
+ // This set of structures is the intersection of structures seen at control flow edges. It's used
+ // for checks and speculation since it can't be widened.
RegisteredStructureSet m_structures;
+
+ // The second set of structures is the union of the structures at control flow edges. It's used
+ // for materializations, where we need to generate code for all possible incoming structures.
+ RegisteredStructureSet m_structuresForMaterialization;
};
class LocalHeap {
@@ -503,7 +520,7 @@
toEscape.addVoid(fieldEntry.value);
} else {
mergePointerSets(allocationEntry.value.fields(), allocationIter->value.fields(), toEscape);
- allocationEntry.value.mergeStructures(allocationIter->value.structures());
+ allocationEntry.value.mergeStructures(allocationIter->value);
}
}
@@ -1446,7 +1463,6 @@
if (DFGObjectAllocationSinkingPhaseInternal::verbose)
dataLog("Candidates: ", listDump(m_sinkCandidates), "\n");
-
// Create the materialization nodes.
forEachEscapee([&] (HashMap<Node*, Allocation>& escapees, Node* where) {
placeMaterializations(WTFMove(escapees), where);
@@ -1681,7 +1697,7 @@
return m_graph.addNode(
allocation.identifier()->prediction(), Node::VarArg, MaterializeNewObject,
where->origin.withSemantic(allocation.identifier()->origin.semantic),
- OpInfo(m_graph.addStructureSet(allocation.structures())), OpInfo(data), 0, 0);
+ OpInfo(m_graph.addStructureSet(allocation.structuresForMaterialization())), OpInfo(data), 0, 0);
}
case Allocation::Kind::AsyncGeneratorFunction:
@@ -2476,7 +2492,7 @@
UniquedStringImpl* uid = m_graph.identifiers()[identifierNumber];
Vector<RegisteredStructure> structures;
- for (RegisteredStructure structure : allocation.structures()) {
+ for (RegisteredStructure structure : allocation.structuresForMaterialization()) {
// This structure set is conservative. This set can include Structure which does not have a legit property.
// We filter out such an apparently inappropriate structures here since MultiPutByOffset assumes all the structures
// have valid corresponding offset for the given property.
