- Revision
- 265685
- Author
- [email protected]
- Date
- 2020-08-14 11:42:54 -0700 (Fri, 14 Aug 2020)
Log Message
OSRAvailabilityAnalysis shouldn't mark GetStack nodes directly as valid places for recovery
https://bugs.webkit.org/show_bug.cgi?id=215434
Reviewed by Saam Barati.
JSTests:
* stress/for-of-post-sinking-osr-availability.js: Added.
(foo):
Source/_javascript_Core:
It's somewhat subtle why we cannot use the node for the GetStack
itself in the Availability's node field. The reason is that if we
did we would need to make any phase that converts nodes to
GetStack availability aware. For instance, a place where this
could come up is in constant folding if you had a graph like the
following, which could arise from PutStack sinking:
BB#1:
@1: NewObject()
@2: MovHint(@1, inline-arg1)
@3: Jump(#2, #3)
BB#2:
@4: PutStack(@1, inline-arg1)
@5: GetMyArgumentByVal(inline-arg1)
@6: Jump(#3)
BB#3:
@7: InvalidationPoint()
If constant folding converts @5 to a GetStack then at @7
inline-arg1 won't be available since at the end of BB#1 our
availability is (@1, DeadFlush) and (@5,
FlushedAt(inline-arg1)). When that gets merged at BB#3 then the
availability will be (nullptr, ConflictingFlush).
This patch also makes validation check that availability is sane
at each pontential exit site if
Options::validateFTLOSRExitLiveness() is set. Since this is
actually a Phase we also need to make sure that we don't infinite
loop, so there is now a m_isValidating field on m_graph. The
validateOSRExitAvailability phase is also careful not to modify
the Graph, in order to avoid masking bugs when validating.
In a followup patch I intend to look into why MovHint elimination
will convert:
@2: MovHint(@0, loc1, bc#1, ExitInvalid)
@3: KillStack(loc1, bc#2, ExitValid)
@4: MovHint(@1 loc1, bc#2, ExitInvalid)
into
@2: ZombieHint(@0, loc1, bc#1, ExitInvalid)
@3: KillStack(loc1, bc#2, ExitValid)
@4: MovHint(@1 loc1, bc#2, ExitInvalid)
when loc1 is live in the bytecode at bc#2. But for now, the
validation rule works around this by only checking when mayExit
and the nodes exitOK agree exiting is possible.
* dfg/DFGGraph.h:
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
(JSC::DFG::OSRAvailabilityAnalysisPhase::OSRAvailabilityAnalysisPhase):
(JSC::DFG::OSRAvailabilityAnalysisPhase::run):
(JSC::DFG::performOSRAvailabilityAnalysis):
(JSC::DFG::validateOSRExitAvailability):
(JSC::DFG::LocalOSRAvailabilityCalculator::executeNode):
* dfg/DFGOSRAvailabilityAnalysisPhase.h:
* dfg/DFGPhase.h:
(JSC::DFG::runPhase):
* dfg/DFGValidate.cpp:
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (265684 => 265685)
--- trunk/JSTests/ChangeLog 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/JSTests/ChangeLog 2020-08-14 18:42:54 UTC (rev 265685)
@@ -1,3 +1,13 @@
+2020-08-12 Keith Miller <[email protected]>
+
+ OSRAvailabilityAnalysis shouldn't mark GetStack nodes directly as valid places for recovery
+ https://bugs.webkit.org/show_bug.cgi?id=215434
+
+ Reviewed by Saam Barati.
+
+ * stress/for-of-post-sinking-osr-availability.js: Added.
+ (foo):
+
2020-08-13 Alexey Shvayka <[email protected]>
Cache Structure::attributeChangeTransition()
Added: trunk/JSTests/stress/for-of-post-sinking-osr-availability.js (0 => 265685)
--- trunk/JSTests/stress/for-of-post-sinking-osr-availability.js (rev 0)
+++ trunk/JSTests/stress/for-of-post-sinking-osr-availability.js 2020-08-14 18:42:54 UTC (rev 265685)
@@ -0,0 +1,7 @@
+function foo() {
+ Array.of({});
+}
+
+for (let i=0; i<10; i++) {
+ foo();
+}
Modified: trunk/Source/_javascript_Core/ChangeLog (265684 => 265685)
--- trunk/Source/_javascript_Core/ChangeLog 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/ChangeLog 2020-08-14 18:42:54 UTC (rev 265685)
@@ -1,3 +1,73 @@
+2020-08-12 Keith Miller <[email protected]>
+
+ OSRAvailabilityAnalysis shouldn't mark GetStack nodes directly as valid places for recovery
+ https://bugs.webkit.org/show_bug.cgi?id=215434
+
+ Reviewed by Saam Barati.
+
+ It's somewhat subtle why we cannot use the node for the GetStack
+ itself in the Availability's node field. The reason is that if we
+ did we would need to make any phase that converts nodes to
+ GetStack availability aware. For instance, a place where this
+ could come up is in constant folding if you had a graph like the
+ following, which could arise from PutStack sinking:
+
+ BB#1:
+ @1: NewObject()
+ @2: MovHint(@1, inline-arg1)
+ @3: Jump(#2, #3)
+
+ BB#2:
+ @4: PutStack(@1, inline-arg1)
+ @5: GetMyArgumentByVal(inline-arg1)
+ @6: Jump(#3)
+
+ BB#3:
+ @7: InvalidationPoint()
+
+ If constant folding converts @5 to a GetStack then at @7
+ inline-arg1 won't be available since at the end of BB#1 our
+ availability is (@1, DeadFlush) and (@5,
+ FlushedAt(inline-arg1)). When that gets merged at BB#3 then the
+ availability will be (nullptr, ConflictingFlush).
+
+ This patch also makes validation check that availability is sane
+ at each pontential exit site if
+ Options::validateFTLOSRExitLiveness() is set. Since this is
+ actually a Phase we also need to make sure that we don't infinite
+ loop, so there is now a m_isValidating field on m_graph. The
+ validateOSRExitAvailability phase is also careful not to modify
+ the Graph, in order to avoid masking bugs when validating.
+
+ In a followup patch I intend to look into why MovHint elimination
+ will convert:
+
+ @2: MovHint(@0, loc1, bc#1, ExitInvalid)
+ @3: KillStack(loc1, bc#2, ExitValid)
+ @4: MovHint(@1 loc1, bc#2, ExitInvalid)
+
+ into
+
+ @2: ZombieHint(@0, loc1, bc#1, ExitInvalid)
+ @3: KillStack(loc1, bc#2, ExitValid)
+ @4: MovHint(@1 loc1, bc#2, ExitInvalid)
+
+ when loc1 is live in the bytecode at bc#2. But for now, the
+ validation rule works around this by only checking when mayExit
+ and the nodes exitOK agree exiting is possible.
+
+ * dfg/DFGGraph.h:
+ * dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
+ (JSC::DFG::OSRAvailabilityAnalysisPhase::OSRAvailabilityAnalysisPhase):
+ (JSC::DFG::OSRAvailabilityAnalysisPhase::run):
+ (JSC::DFG::performOSRAvailabilityAnalysis):
+ (JSC::DFG::validateOSRExitAvailability):
+ (JSC::DFG::LocalOSRAvailabilityCalculator::executeNode):
+ * dfg/DFGOSRAvailabilityAnalysisPhase.h:
+ * dfg/DFGPhase.h:
+ (JSC::DFG::runPhase):
+ * dfg/DFGValidate.cpp:
+
2020-08-13 Alexey Shvayka <[email protected]>
Cache Structure::attributeChangeTransition()
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (265684 => 265685)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2020-08-14 18:42:54 UTC (rev 265685)
@@ -686,7 +686,7 @@
{
}
- NaturalBlockIterable(Graph& graph)
+ NaturalBlockIterable(const Graph& graph)
: m_graph(&graph)
{
}
@@ -699,7 +699,7 @@
{
}
- iterator(Graph& graph, BlockIndex index)
+ iterator(const Graph& graph, BlockIndex index)
: m_graph(&graph)
, m_index(findNext(index))
{
@@ -734,7 +734,7 @@
return index;
}
- Graph* m_graph;
+ const Graph* m_graph;
BlockIndex m_index;
};
@@ -749,10 +749,10 @@
}
private:
- Graph* m_graph;
+ const Graph* m_graph;
};
- NaturalBlockIterable blocksInNaturalOrder()
+ NaturalBlockIterable blocksInNaturalOrder() const
{
return NaturalBlockIterable(*this);
}
@@ -1172,6 +1172,7 @@
bool m_hasDebuggerEnabled;
bool m_hasExceptionHandlers { false };
bool m_isInSSAConversion { false };
+ bool m_isValidating { false };
Optional<uint32_t> m_maxLocalsForCatchOSREntry;
std::unique_ptr<FlowIndexing> m_indexingCache;
std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp (265684 => 265685)
--- trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2020-08-14 18:42:54 UTC (rev 265685)
@@ -28,17 +28,21 @@
#if ENABLE(DFG_JIT)
-#include "DFGGraph.h"
+#include "DFGBlockMapInlines.h"
+#include "DFGMayExit.h"
#include "DFGPhase.h"
#include "JSCJSValueInlines.h"
namespace JSC { namespace DFG {
+template<typename HeadFunctor, typename TailFunctor>
class OSRAvailabilityAnalysisPhase : public Phase {
static constexpr bool verbose = false;
public:
- OSRAvailabilityAnalysisPhase(Graph& graph)
+ OSRAvailabilityAnalysisPhase(Graph& graph, HeadFunctor& availabilityAtHead, TailFunctor& availabilityAtTail)
: Phase(graph, "OSR availability analysis")
+ , availabilityAtHead(availabilityAtHead)
+ , availabilityAtTail(availabilityAtTail)
{
}
@@ -50,21 +54,21 @@
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
- block->ssa->availabilityAtHead.clear();
- block->ssa->availabilityAtTail.clear();
+ availabilityAtHead(block).clear();
+ availabilityAtTail(block).clear();
}
BasicBlock* root = m_graph.block(0);
- root->ssa->availabilityAtHead.m_locals.fill(Availability::unavailable());
+ availabilityAtHead(root).m_locals.fill(Availability::unavailable());
for (unsigned argument = 0; argument < m_graph.block(0)->valuesAtHead.numberOfArguments(); ++argument)
- root->ssa->availabilityAtHead.m_locals.argument(argument) = Availability::unavailable();
+ availabilityAtHead(root).m_locals.argument(argument) = Availability(FlushedAt(FlushedJSValue, virtualRegisterForArgumentIncludingThis(argument)));
// This could be made more efficient by processing blocks in reverse postorder.
- auto dumpAvailability = [] (BasicBlock* block) {
- dataLogLn(block->ssa->availabilityAtHead);
- dataLogLn(block->ssa->availabilityAtTail);
+ auto dumpAvailability = [&] (BasicBlock* block) {
+ dataLogLn("Head: ", availabilityAtHead(block));
+ dataLogLn("Tail: ", availabilityAtTail(block));
};
auto dumpBytecodeLivenessAtHead = [&] (BasicBlock* block) {
@@ -82,24 +86,21 @@
do {
changed = false;
- for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
-
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
if (verbose) {
dataLogLn("Before changing Block #", block->index);
dumpAvailability(block);
}
- calculator.beginBlock(block);
+
+ calculator.m_availability = availabilityAtHead(block);
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex)
calculator.executeNode(block->at(nodeIndex));
- if (calculator.m_availability == block->ssa->availabilityAtTail)
+ if (calculator.m_availability == availabilityAtTail(block))
continue;
- block->ssa->availabilityAtTail = calculator.m_availability;
+ availabilityAtTail(block) = calculator.m_availability;
changed = true;
if (verbose) {
@@ -109,12 +110,12 @@
for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
BasicBlock* successor = block->successor(successorIndex);
- successor->ssa->availabilityAtHead.merge(calculator.m_availability);
+ availabilityAtHead(successor).merge(calculator.m_availability);
}
for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
BasicBlock* successor = block->successor(successorIndex);
- successor->ssa->availabilityAtHead.pruneByLiveness(
+ availabilityAtHead(successor).pruneByLiveness(
m_graph, successor->at(0)->origin.forExit);
if (verbose) {
dataLogLn("After pruning Block #", successor->index);
@@ -127,15 +128,13 @@
if (validationEnabled()) {
- for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ calculator.m_availability = availabilityAtHead(block);
- calculator.beginBlock(block);
-
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- if (block->at(nodeIndex)->origin.exitOK) {
+ Node* node = block->at(nodeIndex);
+ // FIXME: The mayExit status of a node doesn't seem like it should mean we don't need to have everything available.
+ if (mayExit(m_graph, node) != DoesNotExit && node->origin.exitOK) {
// If we're allowed to exit here, the heap must be in a state
// where exiting wouldn't crash. These particular fields are
// required for correctness because we use them during OSR exit
@@ -142,8 +141,9 @@
// to do meaningful things. It would be wrong for any of them
// to be dead.
- AvailabilityMap availabilityMap = calculator.m_availability;
- availabilityMap.pruneByLiveness(m_graph, block->at(nodeIndex)->origin.forExit);
+ CodeOrigin exitOrigin = node->origin.forExit;
+ AvailabilityMap& availabilityMap = calculator.m_availability;
+ availabilityMap.pruneByLiveness(m_graph, exitOrigin);
for (auto heapPair : availabilityMap.m_heap) {
switch (heapPair.key.kind()) {
@@ -163,6 +163,16 @@
break;
}
}
+
+ // FIXME: It seems like we should be able to do at least some validation when OSR entering. https://bugs.webkit.org/show_bug.cgi?id=215511
+ if (m_graph.m_plan.mode() != FTLForOSREntryMode) {
+ for (size_t i = 0; i < availabilityMap.m_locals.size(); ++i) {
+ Operand operand = availabilityMap.m_locals.operandForIndex(i);
+ Availability availability = availabilityMap.m_locals[i];
+ if (availability.isDead() && m_graph.isLiveInBytecode(operand, exitOrigin))
+ DFG_CRASH(m_graph, node, toCString("Live bytecode local not available: operand = ", operand, ", availabilityMap = ", availabilityMap, ", origin = ", exitOrigin).data());
+ }
+ }
}
calculator.executeNode(block->at(nodeIndex));
@@ -173,13 +183,33 @@
return true;
}
+ HeadFunctor& availabilityAtHead;
+ TailFunctor& availabilityAtTail;
};
bool performOSRAvailabilityAnalysis(Graph& graph)
{
- return runPhase<OSRAvailabilityAnalysisPhase>(graph);
+ auto availabilityAtHead = [&] (BasicBlock* block) -> AvailabilityMap& { return block->ssa->availabilityAtHead; };
+ auto availabilityAtTail = [&] (BasicBlock* block) -> AvailabilityMap& { return block->ssa->availabilityAtTail; };
+ return runPhase<OSRAvailabilityAnalysisPhase<decltype(availabilityAtHead), decltype(availabilityAtTail)>>(graph, availabilityAtHead, availabilityAtTail);
}
+void validateOSRExitAvailability(Graph& graph)
+{
+ BlockMap<AvailabilityMap> availabilityMapAtHead(graph);
+ BlockMap<AvailabilityMap> availabilityMapAtTail(graph);
+
+ for (BasicBlock* block : graph.blocksInNaturalOrder()) {
+ availabilityMapAtHead[block] = AvailabilityMap(block->ssa->availabilityAtHead);
+ availabilityMapAtTail[block] = AvailabilityMap(block->ssa->availabilityAtTail);
+ }
+
+ auto availabilityAtHead = [&] (BasicBlock* block) -> AvailabilityMap& { return availabilityMapAtHead[block]; };
+ auto availabilityAtTail = [&] (BasicBlock* block) -> AvailabilityMap& { return availabilityMapAtTail[block]; };
+ OSRAvailabilityAnalysisPhase phase(graph, availabilityAtHead, availabilityAtTail);
+ phase.run();
+}
+
LocalOSRAvailabilityCalculator::LocalOSRAvailabilityCalculator(Graph& graph)
: m_graph(graph)
{
@@ -202,6 +232,24 @@
void LocalOSRAvailabilityCalculator::executeNode(Node* node)
{
switch (node->op()) {
+
+ // It's somewhat subtle why we cannot use the node for the GetStack itself in the Availability's node field. The reason is that if we did we would need to make any phase that converts nodes to GetStack availability aware. For instance a place where this could come up is if you had a graph like:
+
+ // BB#1:
+ // @1: NewObject()
+ // @2: MovHint(@1, inline-arg1)
+ // @3: Jump(#2, #3)
+
+ // BB#2:
+ // @4: PutStack(@1, inline-arg1)
+ // @5: GetMyArgumentByVal(inline-arg1)
+ // @6: Jump(#3)
+
+ // BB#3:
+ // @7: InvalidationPoint()
+
+ // If constant folding converts @5 to a GetStack then at @7 inline-arg1 won't be available since at the end of BB#1 our availability is (@1, DeadFlush) and (@5, FlushedAt(inline-arg1)). When that gets merged at BB#3 then the availability will be (nullptr, ConflictingFlush).
+ case GetStack:
case PutStack: {
StackAccessData* data = ""
m_availability.m_locals.operand(data->operand).setFlush(data->flushedAt());
@@ -213,12 +261,6 @@
break;
}
- case GetStack: {
- StackAccessData* data = ""
- m_availability.m_locals.operand(data->operand) = Availability(node, data->flushedAt());
- break;
- }
-
case MovHint: {
m_availability.m_locals.operand(node->unlinkedOperand()).setNode(node->child1().node());
break;
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.h (265684 => 265685)
--- trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.h 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRAvailabilityAnalysisPhase.h 2020-08-14 18:42:54 UTC (rev 265685)
@@ -41,6 +41,9 @@
bool performOSRAvailabilityAnalysis(Graph&);
+// Unlike the phase above this function doesn't mutate the graph's BasicBlock SSA metadata. Also, does nothing if !validationEnabled()
+void validateOSRExitAvailability(Graph&);
+
// Local calculator for figuring out the availability at any node in a basic block. Requires
// having run the availability analysis.
class LocalOSRAvailabilityCalculator {
Modified: trunk/Source/_javascript_Core/dfg/DFGPhase.h (265684 => 265685)
--- trunk/Source/_javascript_Core/dfg/DFGPhase.h 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/dfg/DFGPhase.h 2020-08-14 18:42:54 UTC (rev 265685)
@@ -88,10 +88,10 @@
return result;
}
-template<typename PhaseType>
-bool runPhase(Graph& graph)
+template<typename PhaseType, typename... Args>
+bool runPhase(Graph& graph, Args... args)
{
- PhaseType phase(graph);
+ PhaseType phase(graph, args...);
return runAndLog(phase);
}
Modified: trunk/Source/_javascript_Core/dfg/DFGValidate.cpp (265684 => 265685)
--- trunk/Source/_javascript_Core/dfg/DFGValidate.cpp 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/dfg/DFGValidate.cpp 2020-08-14 18:42:54 UTC (rev 265685)
@@ -33,6 +33,7 @@
#include "DFGClobbersExitState.h"
#include "DFGDominators.h"
#include "DFGMayExit.h"
+#include "DFGOSRAvailabilityAnalysisPhase.h"
#include <wtf/Assertions.h>
namespace JSC { namespace DFG {
@@ -82,6 +83,11 @@
void validate()
{
+ if (m_graph.m_isValidating)
+ return;
+
+ auto isValidating = SetForScope(m_graph.m_isValidating, true);
+
// NB. This code is not written for performance, since it is not intended to run
// in release builds.
@@ -801,14 +807,13 @@
auto& dominators = m_graph.ensureSSADominators();
+ if (Options::validateFTLOSRExitLiveness())
+ validateOSRExitAvailability(m_graph);
+
for (unsigned entrypointIndex : m_graph.m_entrypointIndexToCatchBytecodeIndex.keys())
VALIDATE((), entrypointIndex > 0); // By convention, 0 is the entrypoint index for the op_enter entrypoint, which can not be in a catch.
- for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
-
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
VALIDATE((block), block->phis.isEmpty());
bool didSeeExitOK = false;
Modified: trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp (265684 => 265685)
--- trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2020-08-14 18:39:15 UTC (rev 265684)
+++ trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2020-08-14 18:42:54 UTC (rev 265685)
@@ -19048,6 +19048,7 @@
Availability availability = availabilityMap.m_locals[i];
+ // FIXME: It seems like we should be able to do at least some validation when OSR entering. https://bugs.webkit.org/show_bug.cgi?id=215511
if (Options::validateFTLOSRExitLiveness()
&& m_graph.m_plan.mode() != FTLForOSREntryMode) {
