Title: [269107] trunk
- Revision
- 269107
- Author
- [email protected]
- Date
- 2020-10-28 10:32:26 -0700 (Wed, 28 Oct 2020)
Log Message
DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
https://bugs.webkit.org/show_bug.cgi?id=218073
Reviewed by Saam Barati.
JSTests:
The only testcase I managed to get for this bug loops forever when not crashing.
So I use a 1s timeout through --watchdog=1000.
* stress/bounds-checking-in-cold-loop.js: Added.
(true.vm.ftlTrue):
Source/_javascript_Core:
In DFGIntegerRangeOptimization, when visiting an Upsilon node, we call setEquivalence, that calls setRelationship.
But despite its name, this function does not overwrite a pre-existing relationship, it simply replaces it by an over-approximation of the intersection of the old and new relationship (see the filter method).
Since the old relationship is always (by definition) an over-approximation of this intersection, it will often do nothing at all if it cannot find a closer approximation.
This is a problem specifically for Upsilon nodes, because several of them can store to the same "shadow node" corresponding to a given Phi, so they are the only case where there can already be a completely different relationship for the same nodes (coming from a different Upsilon).
The fix is very simple thanks to a suggestion by Phil: we just remove all relationships referring to the shadow node just before executing an Upsilon.
This is correct since the upsilon effectively kills that shadow node, before making it live again with a different value, and we already aggressively prune the relationshipMaps by liveness.
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (269106 => 269107)
--- trunk/JSTests/ChangeLog 2020-10-28 16:17:10 UTC (rev 269106)
+++ trunk/JSTests/ChangeLog 2020-10-28 17:32:26 UTC (rev 269107)
@@ -1,3 +1,16 @@
+2020-10-28 Robin Morisset <[email protected]>
+
+ DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
+ https://bugs.webkit.org/show_bug.cgi?id=218073
+
+ Reviewed by Saam Barati.
+
+ The only testcase I managed to get for this bug loops forever when not crashing.
+ So I use a 1s timeout through --watchdog=1000.
+
+ * stress/bounds-checking-in-cold-loop.js: Added.
+ (true.vm.ftlTrue):
+
2020-10-24 Yusuke Suzuki <[email protected]>
[ECMA-402] Implement Intl.ListFormat
Added: trunk/JSTests/stress/bounds-checking-in-cold-loop.js (0 => 269107)
--- trunk/JSTests/stress/bounds-checking-in-cold-loop.js (rev 0)
+++ trunk/JSTests/stress/bounds-checking-in-cold-loop.js 2020-10-28 17:32:26 UTC (rev 269107)
@@ -0,0 +1,12 @@
+//@ runFTLEager("--watchdog=1000", "--watchdog-exception-ok")
+let a = [];
+a[0] = undefined;
+
+while (true) {
+ let i = 0;
+ a[0];
+ while ($vm.ftlTrue()) {
+ a[i++] = undefined;
+ }
+}
+
Modified: trunk/Source/_javascript_Core/ChangeLog (269106 => 269107)
--- trunk/Source/_javascript_Core/ChangeLog 2020-10-28 16:17:10 UTC (rev 269106)
+++ trunk/Source/_javascript_Core/ChangeLog 2020-10-28 17:32:26 UTC (rev 269107)
@@ -1,3 +1,20 @@
+2020-10-28 Robin Morisset <[email protected]>
+
+ DFGIntegerRangeOptimization is wrong for Upsilon (as 'shadow' nodes are not in SSA form)
+ https://bugs.webkit.org/show_bug.cgi?id=218073
+
+ Reviewed by Saam Barati.
+
+ In DFGIntegerRangeOptimization, when visiting an Upsilon node, we call setEquivalence, that calls setRelationship.
+ But despite its name, this function does not overwrite a pre-existing relationship, it simply replaces it by an over-approximation of the intersection of the old and new relationship (see the filter method).
+ Since the old relationship is always (by definition) an over-approximation of this intersection, it will often do nothing at all if it cannot find a closer approximation.
+ This is a problem specifically for Upsilon nodes, because several of them can store to the same "shadow node" corresponding to a given Phi, so they are the only case where there can already be a completely different relationship for the same nodes (coming from a different Upsilon).
+
+ The fix is very simple thanks to a suggestion by Phil: we just remove all relationships referring to the shadow node just before executing an Upsilon.
+ This is correct since the upsilon effectively kills that shadow node, before making it live again with a different value, and we already aggressively prune the relationshipMaps by liveness.
+
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+
2020-10-27 Michael Catanzaro <[email protected]>
-Wparentheses warning in OptionsList.h
Modified: trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp (269106 => 269107)
--- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2020-10-28 16:17:10 UTC (rev 269106)
+++ trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2020-10-28 17:32:26 UTC (rev 269107)
@@ -1503,9 +1503,12 @@
}
case Upsilon: {
- setEquivalence(
- node->child1().node(),
- NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
+ auto shadowNode = NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow);
+ // We must first remove all relationships involving the shadow node, because setEquivalence does not overwrite them.
+ // Overwriting is only required here because the shadowNodes are not in SSA form (can be written to by several Upsilons).
+ // Another way to think of it, is that we are maintaining the invariant that relationshipMaps are pruned by liveness.
+ kill(shadowNode);
+ setEquivalence(node->child1().node(), shadowNode);
break;
}
@@ -1520,6 +1523,22 @@
break;
}
}
+
+ void kill(NodeFlowProjection node)
+ {
+ m_relationships.remove(node);
+
+ for (auto& relationships : m_relationships.values()) {
+ unsigned i = 0, j = 0;
+ while (i < relationships.size()) {
+ const Relationship& rel = relationships[i++];
+ ASSERT(rel.left() != node);
+ if (rel.right() != node)
+ relationships[j++] = rel;
+ }
+ relationships.shrink(j);
+ }
+ }
void setEquivalence(NodeFlowProjection oldNode, NodeFlowProjection newNode)
{
@@ -1560,7 +1579,7 @@
return;
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
- dataLog(" Setting: ", relationship, " (ttl = ", timeToLive, ")\n");
+ dataLogLn(" Setting: ", relationship, " (ttl = ", timeToLive, ")");
auto result = relationshipMap.add(
relationship.left(), Vector<Relationship>());
@@ -1642,6 +1661,8 @@
if (Relationship filtered = otherRelationship.filter(relationship)) {
ASSERT(filtered.left() == relationship.left());
otherRelationship = filtered;
+ if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
+ dataLogLn(" filtered: ", filtered);
found = true;
}
}
@@ -1699,7 +1720,7 @@
toAdd.append(newRelationship);
}
}
-
+
if (!found)
relationships.append(relationship);
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
