- Revision
- 184206
- Author
- [email protected]
- Date
- 2015-05-12 11:01:28 -0700 (Tue, 12 May 2015)
Log Message
OSR availability analysis would be more scalable (and correct) if it did more liveness pruning
https://bugs.webkit.org/show_bug.cgi?id=143078
Reviewed by Andreas Kling.
In https://bugs.webkit.org/show_bug.cgi?id=144883, we found an example of where liveness
pruning is actually necessary. Well, not quite: we just need to prune out keys from the
heap availability map where the base node doesn't dominate the point where we are asking
for availability. If we don't do this, then eventually the IR gets corrupt because we'll
insert PutHints that reference the base node in places where the base node doesn't
dominate. But if we're going to do any pruning, then it makes sense to prune by bytecode
liveness. This is the strongest possible pruning we can do, and it should be sound. We
shouldn't have a node available for a virtual register if that register is live and the
node doesn't dominate.
Making this work meant reusing the prune-to-liveness algorithm from the FTL backend. So, I
abstracted this a bit better. You can now availabilityMap.pruneByLiveness(graph, origin).
* dfg/DFGAvailabilityMap.cpp:
(JSC::DFG::AvailabilityMap::pruneHeap):
(JSC::DFG::AvailabilityMap::pruneByLiveness):
(JSC::DFG::AvailabilityMap::prune): Deleted.
* dfg/DFGAvailabilityMap.h:
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
(JSC::DFG::OSRAvailabilityAnalysisPhase::run):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::buildExitArguments):
* tests/stress/liveness-pruning-needed-for-osr-availability.js: Added. This is a proper regression test.
* tests/stress/liveness-pruning-needed-for-osr-availability-eager.js: Added. This is the original reduced test case, requires eager-no-cjit to fail prior to this changeset.
Modified Paths
Added Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (184205 => 184206)
--- trunk/Source/_javascript_Core/ChangeLog 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-05-12 18:01:28 UTC (rev 184206)
@@ -1,3 +1,35 @@
+2015-05-11 Filip Pizlo <[email protected]>
+
+ OSR availability analysis would be more scalable (and correct) if it did more liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=143078
+
+ Reviewed by Andreas Kling.
+
+ In https://bugs.webkit.org/show_bug.cgi?id=144883, we found an example of where liveness
+ pruning is actually necessary. Well, not quite: we just need to prune out keys from the
+ heap availability map where the base node doesn't dominate the point where we are asking
+ for availability. If we don't do this, then eventually the IR gets corrupt because we'll
+ insert PutHints that reference the base node in places where the base node doesn't
+ dominate. But if we're going to do any pruning, then it makes sense to prune by bytecode
+ liveness. This is the strongest possible pruning we can do, and it should be sound. We
+ shouldn't have a node available for a virtual register if that register is live and the
+ node doesn't dominate.
+
+ Making this work meant reusing the prune-to-liveness algorithm from the FTL backend. So, I
+ abstracted this a bit better. You can now availabilityMap.pruneByLiveness(graph, origin).
+
+ * dfg/DFGAvailabilityMap.cpp:
+ (JSC::DFG::AvailabilityMap::pruneHeap):
+ (JSC::DFG::AvailabilityMap::pruneByLiveness):
+ (JSC::DFG::AvailabilityMap::prune): Deleted.
+ * dfg/DFGAvailabilityMap.h:
+ * dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
+ (JSC::DFG::OSRAvailabilityAnalysisPhase::run):
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::LowerDFGToLLVM::buildExitArguments):
+ * tests/stress/liveness-pruning-needed-for-osr-availability.js: Added. This is a proper regression test.
+ * tests/stress/liveness-pruning-needed-for-osr-availability-eager.js: Added. This is the original reduced test case, requires eager-no-cjit to fail prior to this changeset.
+
2015-05-12 Gabor Loki <[email protected]>
Workaround for Cortex-A53 erratum 843419
Modified: trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.cpp (184205 => 184206)
--- trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.cpp 2015-05-12 18:01:28 UTC (rev 184206)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -28,12 +28,14 @@
#if ENABLE(DFG_JIT)
+#include "DFGGraph.h"
+#include "JSCInlines.h"
#include "OperandsInlines.h"
#include <wtf/ListDump.h>
namespace JSC { namespace DFG {
-void AvailabilityMap::prune()
+void AvailabilityMap::pruneHeap()
{
if (m_heap.isEmpty())
return;
@@ -61,6 +63,18 @@
m_heap = newHeap;
}
+void AvailabilityMap::pruneByLiveness(Graph& graph, CodeOrigin where)
+{
+ Operands<Availability> localsCopy(OperandsLike, m_locals);
+ graph.forAllLiveInBytecode(
+ where,
+ [&] (VirtualRegister reg) {
+ localsCopy.operand(reg) = m_locals.operand(reg);
+ });
+ m_locals = localsCopy;
+ pruneHeap();
+}
+
void AvailabilityMap::clear()
{
m_locals.fill(Availability());
Modified: trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.h (184205 => 184206)
--- trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.h 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/_javascript_Core/dfg/DFGAvailabilityMap.h 2015-05-12 18:01:28 UTC (rev 184206)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -34,7 +34,8 @@
namespace JSC { namespace DFG {
struct AvailabilityMap {
- void prune();
+ void pruneHeap();
+ void pruneByLiveness(Graph&, CodeOrigin);
void clear();
void dump(PrintStream& out) const;
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp (184205 => 184206)
--- trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-05-12 18:01:28 UTC (rev 184206)
@@ -82,10 +82,6 @@
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex)
calculator.executeNode(block->at(nodeIndex));
- // FIXME: we should probably prune by liveness here.
- // https://bugs.webkit.org/show_bug.cgi?id=143078
- calculator.m_availability.prune();
-
if (calculator.m_availability == block->ssa->availabilityAtTail)
continue;
@@ -95,6 +91,8 @@
for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
BasicBlock* successor = block->successor(successorIndex);
successor->ssa->availabilityAtHead.merge(calculator.m_availability);
+ successor->ssa->availabilityAtHead.pruneByLiveness(
+ m_graph, successor->firstOrigin().forExit);
}
}
} while (changed);
Modified: trunk/Source/_javascript_Core/ftl/FTLLowerDFGToLLVM.cpp (184205 => 184206)
--- trunk/Source/_javascript_Core/ftl/FTLLowerDFGToLLVM.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/_javascript_Core/ftl/FTLLowerDFGToLLVM.cpp 2015-05-12 18:01:28 UTC (rev 184206)
@@ -8006,17 +8006,8 @@
arguments.append(lowValue.value());
AvailabilityMap availabilityMap = this->availabilityMap();
- availabilityMap.m_locals.fill(Availability());
+ availabilityMap.pruneByLiveness(m_graph, codeOrigin);
- m_graph.forAllLiveInBytecode(
- codeOrigin,
- [&] (VirtualRegister reg) {
- availabilityMap.m_locals.operand(reg) =
- this->availabilityMap().m_locals.operand(reg);
- });
-
- availabilityMap.prune();
-
HashMap<Node*, ExitTimeObjectMaterialization*> map;
availabilityMap.forEachAvailability(
[&] (Availability availability) {
Added: trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js (0 => 184206)
--- trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js 2015-05-12 18:01:28 UTC (rev 184206)
@@ -0,0 +1,16 @@
+// Note that this only fails in eager compilation.
+
+function each(ary, func) {
+ if (ary)
+ for (var i = 0; i < ary.length && (!ary[i] ||!func(ary[i], i, ary)); i += 1);
+}
+
+var blah = function () {
+ var func = function() {
+ return (function () { }).apply(Object, arguments);
+ };
+ each([ {}, {} ], func);
+};
+
+for (var i = 0; i < 1000; i++)
+ blah();
Added: trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability.js (0 => 184206)
--- trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/liveness-pruning-needed-for-osr-availability.js 2015-05-12 18:01:28 UTC (rev 184206)
@@ -0,0 +1,15 @@
+function each(ary, func) {
+ for (var i = 0; i < ary.length && (!ary[i] ||!func(ary[i], i, ary)); i += 1);
+}
+
+function foo() {
+ each(
+ [ {}, {} ],
+ function () {
+ return (function (x) { })(arguments);
+ });
+};
+noInline(foo);
+
+for (var i = 0; i < 100000; i++)
+ foo();
