Title: [198621] trunk/Source/_javascript_Core
- Revision
- 198621
- Author
- [email protected]
- Date
- 2016-03-24 02:02:55 -0700 (Thu, 24 Mar 2016)
Log Message
[JSC] In some cases, the integer range optimization phase never converges
https://bugs.webkit.org/show_bug.cgi?id=155828
rdar://problem/25155460
Patch by Benjamin Poulain <[email protected]> on 2016-03-24
Reviewed by Filip Pizlo.
In certain conditions, the integer range optimization phase continuously
changes the representation of the same truth, preventing it from
converging to a stable state.
The bug starts by having the same ground truth incomming into a block
in different valid forms. For example, you can have x < 42 coming as:
1) x < 42
2) x < 41 + 1
3) x < 43 - 1
Having those 3 alone coming from predecessors would be okay, we would
just accumulate them. The problem is when you have a combination
of rule that filter out the previously obtained truth, then add a new
form of the same truth.
Let's use the test case as an example. We have two incoming blocks:
Block #1:
-i < 42
-i != 41
Block #2:
-i < 41
-i == 42 - 42 (i == 0 refining the rule above).
Let say that our conditions at head are now [i < 41, i < 42 - 1].
If we merge block #2:
-i < 42 and i < 41 -> i < 42
-i < 42 and i < 42 - 1 -> i < 42
-i != 41 and i < 41 -> i < 41
-i != 41 and i < 42 - 1 -> nothing
The new head is: [i < 41, i < 42]
If we merge block #1:
-i < 41 and i < 41 -> i < 41
-i < 41 and i < 42 -> i < 42
-i == 42 - 42 and i < 41 -> (i < 41 and i < 42 - 1)
-i == 42 - 42 and i < 42 -> i < 42
After filter, we are back to [i < 41, i < 42 - 1].
There are several variations of this idea where the same truth
rotate different forms with each merge().
One possible solution is to make filter() more aggressive
to avoid the better form occuring at merge(). I'll probably
do that at some point but that seems fragile since the same
problem could reappear if merge() is later improved.
For this patch, I went with a more generic solution after
merge(): if the generated form is equivalent to one that
previously existed at head, pick the existing form.
In the previous example, what happens is we only have
either [i < 41] or [i < 42 - 1] but never both simultaneously.
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* tests/stress/integer-range-optimization-constant-representation-1.js: Added.
* tests/stress/integer-range-optimization-constant-representation-2.js: Added.
Two variation. One timeout in release because of the additional flags.
The other is gets more type of run but only assert in debug.
Modified Paths
Added Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (198620 => 198621)
--- trunk/Source/_javascript_Core/ChangeLog 2016-03-24 08:10:01 UTC (rev 198620)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-03-24 09:02:55 UTC (rev 198621)
@@ -1,3 +1,73 @@
+2016-03-24 Benjamin Poulain <[email protected]>
+
+ [JSC] In some cases, the integer range optimization phase never converges
+ https://bugs.webkit.org/show_bug.cgi?id=155828
+ rdar://problem/25155460
+
+ Reviewed by Filip Pizlo.
+
+ In certain conditions, the integer range optimization phase continuously
+ changes the representation of the same truth, preventing it from
+ converging to a stable state.
+
+ The bug starts by having the same ground truth incomming into a block
+ in different valid forms. For example, you can have x < 42 coming as:
+ 1) x < 42
+ 2) x < 41 + 1
+ 3) x < 43 - 1
+
+ Having those 3 alone coming from predecessors would be okay, we would
+ just accumulate them. The problem is when you have a combination
+ of rule that filter out the previously obtained truth, then add a new
+ form of the same truth.
+
+ Let's use the test case as an example. We have two incoming blocks:
+ Block #1:
+ -i < 42
+ -i != 41
+ Block #2:
+ -i < 41
+ -i == 42 - 42 (i == 0 refining the rule above).
+
+ Let say that our conditions at head are now [i < 41, i < 42 - 1].
+
+ If we merge block #2:
+ -i < 42 and i < 41 -> i < 42
+ -i < 42 and i < 42 - 1 -> i < 42
+ -i != 41 and i < 41 -> i < 41
+ -i != 41 and i < 42 - 1 -> nothing
+
+ The new head is: [i < 41, i < 42]
+
+ If we merge block #1:
+ -i < 41 and i < 41 -> i < 41
+ -i < 41 and i < 42 -> i < 42
+ -i == 42 - 42 and i < 41 -> (i < 41 and i < 42 - 1)
+ -i == 42 - 42 and i < 42 -> i < 42
+
+ After filter, we are back to [i < 41, i < 42 - 1].
+
+ There are several variations of this idea where the same truth
+ rotate different forms with each merge().
+
+ One possible solution is to make filter() more aggressive
+ to avoid the better form occuring at merge(). I'll probably
+ do that at some point but that seems fragile since the same
+ problem could reappear if merge() is later improved.
+
+ For this patch, I went with a more generic solution after
+ merge(): if the generated form is equivalent to one that
+ previously existed at head, pick the existing form.
+
+ In the previous example, what happens is we only have
+ either [i < 41] or [i < 42 - 1] but never both simultaneously.
+
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+ * tests/stress/integer-range-optimization-constant-representation-1.js: Added.
+ * tests/stress/integer-range-optimization-constant-representation-2.js: Added.
+ Two variation. One timeout in release because of the additional flags.
+ The other is gets more type of run but only assert in debug.
+
2016-03-23 Commit Queue <[email protected]>
Unreviewed, rolling out r198582.
Modified: trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp (198620 => 198621)
--- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-03-24 08:10:01 UTC (rev 198620)
+++ trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-03-24 09:02:55 UTC (rev 198621)
@@ -42,6 +42,7 @@
namespace {
const bool verbose = false;
+const unsigned giveUpThreshold = 50;
int64_t clampedSumImpl() { return 0; }
@@ -217,6 +218,19 @@
return m_left == other.m_left
&& m_right == other.m_right;
}
+
+ bool isEquivalentTo(const Relationship& other) const
+ {
+ if (m_left != other.m_left || m_kind != other.m_kind)
+ return false;
+
+ if (*this == other)
+ return true;
+
+ if (m_right->isInt32Constant() && other.m_right->isInt32Constant())
+ return (m_right->asInt32() + m_offset) == (other.m_right->asInt32() + other.m_offset);
+ return false;
+ }
bool operator==(const Relationship& other) const
{
@@ -1072,6 +1086,19 @@
// the comment above Relationship::merge() for details.
bool changed = true;
while (changed) {
+ ++m_iterations;
+ if (m_iterations >= giveUpThreshold) {
+ // This case is not necessarily wrong but it can be a sign that this phase
+ // does not converge.
+ // If you hit this assertion for a legitimate case, update the giveUpThreshold
+ // to the smallest values that converges.
+ ASSERT_NOT_REACHED();
+
+ // In release, do not risk holding the thread for too long since this phase
+ // is really slow.
+ return false;
+ }
+
changed = false;
for (unsigned postOrderIndex = postOrder.size(); postOrderIndex--;) {
BasicBlock* block = postOrder[postOrderIndex];
@@ -1682,7 +1709,13 @@
changed = true;
continue;
}
-
+
+ Vector<Relationship> constantRelationshipsAtHead;
+ for (Relationship& relationshipAtHead : entry.value) {
+ if (relationshipAtHead.right()->isInt32Constant())
+ constantRelationshipsAtHead.append(relationshipAtHead);
+ }
+
Vector<Relationship> mergedRelationships;
for (Relationship targetRelationship : entry.value) {
for (Relationship sourceRelationship : iter->value) {
@@ -1693,6 +1726,24 @@
[&] (Relationship newRelationship) {
if (verbose)
dataLog(" Got ", newRelationship, "\n");
+
+ if (newRelationship.right()->isInt32Constant()) {
+ // We can produce a relationship with a constant equivalent to
+ // an existing relationship yet of a different form. For example:
+ //
+ // @a == @b(42) + 0
+ // @a == @c(41) + 1
+ //
+ // We do not want to perpetually switch between those two forms,
+ // so we always prefer the one already at head.
+
+ for (Relationship& existingRelationshipAtHead : constantRelationshipsAtHead) {
+ if (existingRelationshipAtHead.isEquivalentTo(newRelationship)) {
+ newRelationship = existingRelationshipAtHead;
+ break;
+ }
+ }
+ }
// We need to filter() to avoid exponential explosion of identical
// relationships. We do this here to avoid making setOneSide() do
@@ -1764,6 +1815,8 @@
BlockSet m_seenBlocks;
BlockMap<RelationshipMap> m_relationshipsAtHead;
InsertionSet m_insertionSet;
+
+ unsigned m_iterations { 0 };
};
} // anonymous namespace
Added: trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-1.js (0 => 198621)
--- trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-1.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-1.js 2016-03-24 09:02:55 UTC (rev 198621)
@@ -0,0 +1,46 @@
+//@ run("integer-range-optimization-constant-representation", *NO_CJIT_OPTIONS, "--useConcurrentJIT=false")
+//@ run("integer-range-optimization-constant-representation", *FTL_OPTIONS, "--useConcurrentJIT=false")
+
+function opaque()
+{
+ // This exists to hide side effects to the optimizer.
+}
+noInline(opaque);
+
+function test(i, opaqueCondition) {
+ do {
+ if (opaqueCondition == 1) {
+ if (i < 42) {
+ opaque(i);
+ if (i != 41) {
+ break;
+ }
+ }
+ } else if (opaqueCondition == 2) {
+ if (i < 42) {
+ opaque(i);
+ if (i < 41) {
+ opaque(i);
+ if (i == 0) {
+ break;
+ }
+ }
+ }
+ }
+ } while (true);
+
+ opaque(i);
+ opaque(42);
+ opaque(41);
+ return i;
+}
+noInline(test);
+
+function loop() {
+ for (let i = 0; i < 1e6; ++i)
+ test(1, 1);
+}
+noInline(loop);
+noDFG(loop);
+
+loop();
\ No newline at end of file
Added: trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-2.js (0 => 198621)
--- trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-2.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/integer-range-optimization-constant-representation-2.js 2016-03-24 09:02:55 UTC (rev 198621)
@@ -0,0 +1,43 @@
+function opaque()
+{
+ // This exists to hide side effects to the optimizer.
+}
+noInline(opaque);
+
+function test(i, opaqueCondition) {
+ do {
+ if (opaqueCondition == 1) {
+ if (i < 42) {
+ opaque(i);
+ if (i != 41) {
+ break;
+ }
+ }
+ } else if (opaqueCondition == 2) {
+ if (i < 42) {
+ opaque(i);
+ if (i < 41) {
+ opaque(i);
+ if (i == 0) {
+ break;
+ }
+ }
+ }
+ }
+ } while (true);
+
+ opaque(i);
+ opaque(42);
+ opaque(41);
+ return i;
+}
+noInline(test);
+
+function loop() {
+ for (let i = 0; i < 1e6; ++i)
+ test(1, 1);
+}
+noInline(loop);
+noDFG(loop);
+
+loop();
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
