FTL should have an explicit notion of bytecode liveness
https://bugs.webkit.org/show_bug.cgi?id=124181
Source/JavaScriptCore:
Reviewed by Sam Weinig.
This makes FTL OSR exit use bytecode liveness analysis to determine which variables
to include values for. The decision of how to get the values of variables is based on
forward propagation of MovHints and SetLocals.
This fixes a bunch of bugs (like https://bugs.webkit.org/show_bug.cgi?id=124138 but
also others that I noticed when I started writing more targetted tests) and allows us
to remove some sketchy code.
* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/BytecodeBasicBlock.h:
* bytecode/BytecodeLivenessAnalysis.cpp:
(JSC::isValidRegisterForLiveness):
(JSC::setForOperand):
(JSC::computeUsesForBytecodeOffset):
(JSC::computeDefsForBytecodeOffset):
(JSC::stepOverInstruction):
(JSC::computeLocalLivenessForBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::runLivenessFixpoint):
(JSC::BytecodeLivenessAnalysis::operandIsLiveAtBytecodeOffset):
(JSC::getLivenessInfo):
(JSC::BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::computeFullLiveness):
* bytecode/BytecodeLivenessAnalysis.h:
* bytecode/BytecodeLivenessAnalysisInlines.h: Added.
(JSC::operandIsAlwaysLive):
(JSC::operandThatIsNotAlwaysLiveIsLive):
(JSC::operandIsLive):
* bytecode/CodeBlock.h:
(JSC::CodeBlock::captureCount):
(JSC::CodeBlock::captureStart):
(JSC::CodeBlock::captureEnd):
* bytecode/CodeOrigin.cpp:
(JSC::InlineCallFrame::dumpInContext):
* bytecode/FullBytecodeLiveness.h: Added.
(JSC::FullBytecodeLiveness::FullBytecodeLiveness):
(JSC::FullBytecodeLiveness::getOut):
(JSC::FullBytecodeLiveness::operandIsLive):
(JSC::FullBytecodeLiveness::getLiveness):
* dfg/DFGAvailability.cpp: Added.
(JSC::DFG::Availability::dump):
(JSC::DFG::Availability::dumpInContext):
* dfg/DFGAvailability.h: Added.
(JSC::DFG::Availability::Availability):
(JSC::DFG::Availability::unavailable):
(JSC::DFG::Availability::withFlush):
(JSC::DFG::Availability::withNode):
(JSC::DFG::Availability::withUnavailableNode):
(JSC::DFG::Availability::nodeIsUndecided):
(JSC::DFG::Availability::nodeIsUnavailable):
(JSC::DFG::Availability::hasNode):
(JSC::DFG::Availability::node):
(JSC::DFG::Availability::flushedAt):
(JSC::DFG::Availability::operator!):
(JSC::DFG::Availability::operator==):
(JSC::DFG::Availability::merge):
(JSC::DFG::Availability::mergeNodes):
(JSC::DFG::Availability::unavailableMarker):
* dfg/DFGBasicBlock.h:
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::parseBlock):
* dfg/DFGDisassembler.cpp:
(JSC::DFG::Disassembler::Disassembler):
* dfg/DFGFlushFormat.cpp:
(WTF::printInternal):
* dfg/DFGFlushFormat.h:
(JSC::DFG::resultFor):
(JSC::DFG::useKindFor):
(JSC::DFG::dataFormatFor):
* dfg/DFGFlushedAt.cpp:
(JSC::DFG::FlushedAt::dump):
* dfg/DFGFlushedAt.h:
(JSC::DFG::FlushedAt::FlushedAt):
(JSC::DFG::FlushedAt::merge):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::livenessFor):
(JSC::DFG::Graph::isLiveInBytecode):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::baselineCodeBlockFor):
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
(JSC::DFG::OSRAvailabilityAnalysisPhase::run):
* dfg/DFGOSRAvailabilityAnalysisPhase.h:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGResurrectionForValidationPhase.cpp: Added.
(JSC::DFG::ResurrectionForValidationPhase::ResurrectionForValidationPhase):
(JSC::DFG::ResurrectionForValidationPhase::run):
(JSC::DFG::performResurrectionForValidation):
* dfg/DFGResurrectionForValidationPhase.h: Added.
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
* dfg/DFGValueSource.h:
(JSC::DFG::ValueSource::forFlushFormat):
* dfg/DFGVariableAccessData.h:
* ftl/FTLExitValue.cpp:
(JSC::FTL::ExitValue::dumpInContext):
* ftl/FTLInlineCacheSize.cpp:
(JSC::FTL::sizeOfGetById):
* ftl/FTLLocation.cpp:
(JSC::FTL::Location::gpr):
(JSC::FTL::Location::fpr):
(JSC::FTL::Location::directGPR):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::LowerDFGToLLVM):
(JSC::FTL::LowerDFGToLLVM::compileBlock):
(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::compileSetLocal):
(JSC::FTL::LowerDFGToLLVM::compileZombieHint):
(JSC::FTL::LowerDFGToLLVM::compilePutById):
(JSC::FTL::LowerDFGToLLVM::compileInvalidationPoint):
(JSC::FTL::LowerDFGToLLVM::initializeOSRExitStateForBlock):
(JSC::FTL::LowerDFGToLLVM::appendOSRExit):
(JSC::FTL::LowerDFGToLLVM::emitOSRExitCall):
(JSC::FTL::LowerDFGToLLVM::buildExitArguments):
(JSC::FTL::LowerDFGToLLVM::addExitArgumentForNode):
(JSC::FTL::LowerDFGToLLVM::observeMovHint):
* ftl/FTLOutput.h:
(JSC::FTL::Output::alloca):
* ftl/FTLValueSource.cpp: Removed.
* ftl/FTLValueSource.h: Removed.
* llvm/LLVMAPIFunctions.h:
* runtime/DumpContext.cpp:
(JSC::DumpContext::DumpContext):
* runtime/DumpContext.h:
* runtime/Options.h:
* runtime/SymbolTable.h:
(JSC::SharedSymbolTable::captureStart):
(JSC::SharedSymbolTable::captureEnd):
(JSC::SharedSymbolTable::captureCount):
Tools:
Reviewed by Mark Hahnenberg.
* Scripts/run-jsc-stress-tests:
LayoutTests:
Reviewed by Mark Hahnenberg or Sam Weinig.
I totally added this test after the rest of the patch was r+'d. Under the right tier-up
modes this triggers one of the bugs that the rest of the patch is trying to avoid.
* js/regress/script-tests/weird-inlining-const-prop.js: Added.
(foo):
(bar):
(fuzz):
(testImpl):
(test):
* js/regress/weird-inlining-const-prop-expected.txt: Added.
* js/regress/weird-inlining-const-prop.html: Added.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@159394 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAvailability.cpp b/Source/JavaScriptCore/dfg/DFGAvailability.cpp
new file mode 100644
index 0000000..669c2b4
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGAvailability.cpp
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFGAvailability.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGNode.h"
+
+namespace JSC { namespace DFG {
+
+void Availability::dump(PrintStream& out) const
+{
+ out.print(m_flushedAt, "/");
+
+ if (nodeIsUndecided()) {
+ out.print("Undecided");
+ return;
+ }
+
+ if (nodeIsUnavailable()) {
+ out.print("Unavailable");
+ return;
+ }
+
+ out.print(node());
+}
+
+void Availability::dumpInContext(PrintStream& out, DumpContext*) const
+{
+ dump(out);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGAvailability.h b/Source/JavaScriptCore/dfg/DFGAvailability.h
new file mode 100644
index 0000000..fd9bf65
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGAvailability.h
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGAvailability_h
+#define DFGAvailability_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGFlushedAt.h"
+#include "DFGVariableAccessData.h"
+
+namespace JSC { namespace DFG {
+
+struct Node;
+
+class Availability {
+public:
+ Availability()
+ : m_node(0)
+ , m_flushedAt(DeadFlush)
+ {
+ }
+
+ explicit Availability(Node* node)
+ : m_node(node)
+ , m_flushedAt(ConflictingFlush)
+ {
+ }
+
+ explicit Availability(FlushedAt flushedAt)
+ : m_node(unavailableMarker())
+ , m_flushedAt(flushedAt)
+ {
+ }
+
+ Availability(Node* node, FlushedAt flushedAt)
+ : m_node(node)
+ , m_flushedAt(flushedAt)
+ {
+ }
+
+ static Availability unavailable()
+ {
+ return Availability(unavailableMarker(), FlushedAt(ConflictingFlush));
+ }
+
+ Availability withFlush(FlushedAt flush) const
+ {
+ return Availability(m_node, flush);
+ }
+
+ Availability withNode(Node* node) const
+ {
+ return Availability(node, m_flushedAt);
+ }
+
+ Availability withUnavailableNode() const
+ {
+ return withNode(unavailableMarker());
+ }
+
+ bool nodeIsUndecided() const { return !m_node; }
+ bool nodeIsUnavailable() const { return m_node == unavailableMarker(); }
+
+ bool hasNode() const { return !nodeIsUndecided() && !nodeIsUnavailable(); }
+
+ Node* node() const
+ {
+ ASSERT(!nodeIsUndecided());
+ ASSERT(!nodeIsUnavailable());
+ return m_node;
+ }
+
+ FlushedAt flushedAt() const { return m_flushedAt; }
+
+ bool operator!() const { return nodeIsUnavailable() && flushedAt().format() == ConflictingFlush; }
+
+ bool operator==(const Availability& other) const
+ {
+ return m_node == other.m_node
+ && m_flushedAt == other.m_flushedAt;
+ }
+
+ Availability merge(const Availability& other) const
+ {
+ return Availability(
+ mergeNodes(m_node, other.m_node),
+ m_flushedAt.merge(other.m_flushedAt));
+ }
+
+ void dump(PrintStream&) const;
+ void dumpInContext(PrintStream&, DumpContext*) const;
+
+private:
+ static Node* mergeNodes(Node* a, Node* b)
+ {
+ if (!a)
+ return b;
+ if (!b)
+ return a;
+ if (a == b)
+ return a;
+ return unavailableMarker();
+ }
+
+ static Node* unavailableMarker()
+ {
+ return bitwise_cast<Node*>(static_cast<intptr_t>(1));
+ }
+
+ Node* m_node;
+ FlushedAt m_flushedAt;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGAvailability_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGBasicBlock.h b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
index 7549410..a3a8012 100644
--- a/Source/JavaScriptCore/dfg/DFGBasicBlock.h
+++ b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
@@ -29,6 +29,7 @@
#if ENABLE(DFG_JIT)
#include "DFGAbstractValue.h"
+#include "DFGAvailability.h"
#include "DFGBranchDirection.h"
#include "DFGFlushedAt.h"
#include "DFGNode.h"
@@ -140,8 +141,8 @@
struct SSAData {
Operands<FlushedAt> flushAtHead;
Operands<FlushedAt> flushAtTail;
- Operands<Node*> availabilityAtHead;
- Operands<Node*> availabilityAtTail;
+ Operands<Availability> availabilityAtHead;
+ Operands<Availability> availabilityAtTail;
HashSet<Node*> liveAtHead;
HashSet<Node*> liveAtTail;
HashMap<Node*, AbstractValue> valuesAtHead;
diff --git a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
index ca61430..224d3d3 100644
--- a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
+++ b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
@@ -697,6 +697,15 @@
bool canFold(Node* node)
{
+ if (Options::validateFTLOSRExitLiveness()) {
+ // The static folding that the bytecode parser does results in the DFG
+ // being able to do some DCE that the bytecode liveness analysis would
+ // miss. Hence, we disable the static folding if we're validating FTL OSR
+ // exit liveness. This may be brutish, but this validator is powerful
+ // enough that it's worth it.
+ return false;
+ }
+
return node->isStronglyProvedConstantIn(inlineCallFrame());
}
@@ -3073,6 +3082,7 @@
break;
}
Node* base = cellConstantWithStructureCheck(globalObject, status.structureSet().singletonStructure());
+ addToGraph(Phantom, get(VirtualRegister(scope)));
if (JSValue specificValue = status.specificValue())
set(VirtualRegister(dst), cellConstant(specificValue.asCell()));
else
@@ -3081,6 +3091,7 @@
}
case GlobalVar:
case GlobalVarWithVarInjectionChecks: {
+ addToGraph(Phantom, get(VirtualRegister(scope)));
SymbolTableEntry entry = globalObject->symbolTable()->get(uid);
if (!entry.couldBeWatched() || !m_graph.watchpoints().isStillValid(entry.watchpointSet())) {
set(VirtualRegister(dst), addToGraph(GetGlobalVar, OpInfo(operand), OpInfo(prediction)));
@@ -3131,6 +3142,7 @@
break;
}
Node* base = cellConstantWithStructureCheck(globalObject, status.oldStructure());
+ addToGraph(Phantom, get(VirtualRegister(scope)));
handlePutByOffset(base, identifierNumber, static_cast<PropertyOffset>(operand), get(VirtualRegister(value)));
// Keep scope alive until after put.
addToGraph(Phantom, get(VirtualRegister(scope)));
@@ -3138,6 +3150,7 @@
}
case GlobalVar:
case GlobalVarWithVarInjectionChecks: {
+ addToGraph(Phantom, get(VirtualRegister(scope)));
SymbolTableEntry entry = globalObject->symbolTable()->get(uid);
ASSERT(!entry.couldBeWatched() || !m_graph.watchpoints().isStillValid(entry.watchpointSet()));
addToGraph(PutGlobalVar, OpInfo(operand), get(VirtualRegister(value)));
diff --git a/Source/JavaScriptCore/dfg/DFGDisassembler.cpp b/Source/JavaScriptCore/dfg/DFGDisassembler.cpp
index b8d0c6b..8fea10b 100644
--- a/Source/JavaScriptCore/dfg/DFGDisassembler.cpp
+++ b/Source/JavaScriptCore/dfg/DFGDisassembler.cpp
@@ -38,6 +38,7 @@
Disassembler::Disassembler(Graph& graph)
: m_graph(graph)
{
+ m_dumpContext.graph = &m_graph;
m_labelForBlockIndex.resize(graph.numBlocks());
}
diff --git a/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp b/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp
index 8e3f26b..073500e 100644
--- a/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp
+++ b/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp
@@ -56,6 +56,9 @@
case FlushedJSValue:
out.print("FlushedJSValue");
return;
+ case ConflictingFlush:
+ out.print("ConflictingFlush");
+ return;
}
RELEASE_ASSERT_NOT_REACHED();
}
diff --git a/Source/JavaScriptCore/dfg/DFGFlushFormat.h b/Source/JavaScriptCore/dfg/DFGFlushFormat.h
index be3f943..53fb5a9 100644
--- a/Source/JavaScriptCore/dfg/DFGFlushFormat.h
+++ b/Source/JavaScriptCore/dfg/DFGFlushFormat.h
@@ -45,7 +45,8 @@
FlushedDouble,
FlushedCell,
FlushedBoolean,
- FlushedJSValue
+ FlushedJSValue,
+ ConflictingFlush
};
inline NodeFlags resultFor(FlushFormat format)
@@ -54,6 +55,7 @@
case DeadFlush:
case FlushedJSValue:
case FlushedCell:
+ case ConflictingFlush:
return NodeResultJS;
case FlushedInt32:
return NodeResultInt32;
@@ -73,6 +75,7 @@
switch (format) {
case DeadFlush:
case FlushedJSValue:
+ case ConflictingFlush:
return UntypedUse;
case FlushedCell:
return CellUse;
@@ -93,6 +96,7 @@
{
switch (format) {
case DeadFlush:
+ case ConflictingFlush:
return DataFormatDead;
case FlushedJSValue:
return DataFormatJS;
diff --git a/Source/JavaScriptCore/dfg/DFGFlushedAt.cpp b/Source/JavaScriptCore/dfg/DFGFlushedAt.cpp
index d2e27d82..ce95f45 100644
--- a/Source/JavaScriptCore/dfg/DFGFlushedAt.cpp
+++ b/Source/JavaScriptCore/dfg/DFGFlushedAt.cpp
@@ -32,7 +32,7 @@
void FlushedAt::dump(PrintStream& out) const
{
- if (m_format == DeadFlush)
+ if (m_format == DeadFlush || m_format == ConflictingFlush)
out.print(m_format);
else
out.print("r", m_virtualRegister, ":", m_format);
diff --git a/Source/JavaScriptCore/dfg/DFGFlushedAt.h b/Source/JavaScriptCore/dfg/DFGFlushedAt.h
index cd8a53d..6dfe716 100644
--- a/Source/JavaScriptCore/dfg/DFGFlushedAt.h
+++ b/Source/JavaScriptCore/dfg/DFGFlushedAt.h
@@ -42,6 +42,12 @@
{
}
+ explicit FlushedAt(FlushFormat format)
+ : m_format(format)
+ {
+ ASSERT(format == DeadFlush || format == ConflictingFlush);
+ }
+
FlushedAt(FlushFormat format, VirtualRegister virtualRegister)
: m_format(format)
, m_virtualRegister(virtualRegister)
@@ -65,6 +71,17 @@
bool operator!=(const FlushedAt& other) const { return !(*this == other); }
+ FlushedAt merge(const FlushedAt& other) const
+ {
+ if (!*this)
+ return other;
+ if (!other)
+ return *this;
+ if (*this == other)
+ return *this;
+ return FlushedAt(ConflictingFlush);
+ }
+
void dump(PrintStream&) const;
void dumpInContext(PrintStream&, DumpContext*) const;
diff --git a/Source/JavaScriptCore/dfg/DFGGraph.cpp b/Source/JavaScriptCore/dfg/DFGGraph.cpp
index b0e993f..91a847a 100644
--- a/Source/JavaScriptCore/dfg/DFGGraph.cpp
+++ b/Source/JavaScriptCore/dfg/DFGGraph.cpp
@@ -26,11 +26,13 @@
#include "config.h"
#include "DFGGraph.h"
+#include "BytecodeLivenessAnalysisInlines.h"
#include "CodeBlock.h"
#include "CodeBlockWithJITType.h"
#include "DFGClobberSet.h"
#include "DFGJITCode.h"
#include "DFGVariableAccessDataDump.h"
+#include "FullBytecodeLiveness.h"
#include "FunctionExecutableDump.h"
#include "OperandsInlines.h"
#include "Operations.h"
@@ -393,6 +395,7 @@
void Graph::dump(PrintStream& out, DumpContext* context)
{
DumpContext myContext;
+ myContext.graph = this;
if (!context)
context = &myContext;
@@ -643,6 +646,58 @@
block->at(nodeIndex)->misc.owner = block;
}
}
+
+FullBytecodeLiveness& Graph::livenessFor(CodeBlock* codeBlock)
+{
+ HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>>::iterator iter = m_bytecodeLiveness.find(codeBlock);
+ if (iter != m_bytecodeLiveness.end())
+ return *iter->value;
+
+ std::unique_ptr<FullBytecodeLiveness> liveness = std::make_unique<FullBytecodeLiveness>();
+ codeBlock->livenessAnalysis().computeFullLiveness(*liveness);
+ FullBytecodeLiveness& result = *liveness;
+ m_bytecodeLiveness.add(codeBlock, std::move(liveness));
+ return result;
+}
+
+FullBytecodeLiveness& Graph::livenessFor(InlineCallFrame* inlineCallFrame)
+{
+ return livenessFor(baselineCodeBlockFor(inlineCallFrame));
+}
+
+bool Graph::isLiveInBytecode(VirtualRegister operand, CodeOrigin codeOrigin)
+{
+ for (;;) {
+ if (operand.offset() < codeOrigin.stackOffset() + JSStack::CallFrameHeaderSize) {
+ VirtualRegister reg = VirtualRegister(
+ operand.offset() - codeOrigin.stackOffset());
+
+ if (reg.isArgument()) {
+ RELEASE_ASSERT(reg.offset() < JSStack::CallFrameHeaderSize);
+
+ if (!codeOrigin.inlineCallFrame->isClosureCall)
+ return false;
+
+ if (reg.offset() == JSStack::Callee)
+ return true;
+ if (reg.offset() == JSStack::ScopeChain)
+ return true;
+
+ return false;
+ }
+
+ return livenessFor(codeOrigin.inlineCallFrame).operandIsLive(
+ reg.offset(), codeOrigin.bytecodeIndex);
+ }
+
+ if (!codeOrigin.inlineCallFrame)
+ break;
+
+ codeOrigin = codeOrigin.inlineCallFrame->caller;
+ }
+
+ return true;
+}
} } // namespace JSC::DFG
diff --git a/Source/JavaScriptCore/dfg/DFGGraph.h b/Source/JavaScriptCore/dfg/DFGGraph.h
index 6a73377..4723f95 100644
--- a/Source/JavaScriptCore/dfg/DFGGraph.h
+++ b/Source/JavaScriptCore/dfg/DFGGraph.h
@@ -416,6 +416,13 @@
return executableFor(codeOrigin.inlineCallFrame);
}
+ CodeBlock* baselineCodeBlockFor(InlineCallFrame* inlineCallFrame)
+ {
+ if (!inlineCallFrame)
+ return m_profiledBlock;
+ return baselineCodeBlockForInlineCallFrame(inlineCallFrame);
+ }
+
CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
{
return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
@@ -776,6 +783,10 @@
DesiredWatchpoints& watchpoints() { return m_plan.watchpoints; }
DesiredStructureChains& chains() { return m_plan.chains; }
+ FullBytecodeLiveness& livenessFor(CodeBlock*);
+ FullBytecodeLiveness& livenessFor(InlineCallFrame*);
+ bool isLiveInBytecode(VirtualRegister, CodeOrigin);
+
VM& m_vm;
Plan& m_plan;
CodeBlock* m_codeBlock;
@@ -797,6 +808,7 @@
SegmentedVector<SwitchData, 4> m_switchData;
Vector<InlineVariableData, 4> m_inlineVariableData;
OwnPtr<InlineCallFrameSet> m_inlineCallFrames;
+ HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
bool m_hasArguments;
HashSet<ExecutableBase*> m_executablesWhoseArgumentsEscaped;
BitVector m_lazyVars;
diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
index 5227b80..705408e 100644
--- a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
@@ -47,78 +47,97 @@
{
ASSERT(m_graph.m_form == SSA);
- Vector<BasicBlock*> depthFirst;
- m_graph.getBlocksInDepthFirstOrder(depthFirst);
-
- for (unsigned i = 0; i < depthFirst.size(); ++i) {
- BasicBlock* block = depthFirst[i];
- block->ssa->availabilityAtHead.fill(0);
- block->ssa->availabilityAtTail.fill(0);
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ block->ssa->availabilityAtHead.fill(Availability());
+ block->ssa->availabilityAtTail.fill(Availability());
}
- for (unsigned i = 0; i < depthFirst.size(); ++i) {
- BasicBlock* block = depthFirst[i];
-
- // We edit availabilityAtTail in-place, but first initialize it to
- // availabilityAtHead.
- Operands<Node*>& availability = block->ssa->availabilityAtTail;
- availability = block->ssa->availabilityAtHead;
-
- for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
- Node* node = block->at(nodeIndex);
- switch (node->op()) {
- case SetLocal:
- case MovHint:
- case MovHintAndCheck: {
- availability.operand(node->local()) = node->child1().node();
- break;
- }
-
- case ZombieHint: {
- availability.operand(node->local()) = 0;
- break;
- }
-
- case GetArgument: {
- availability.operand(node->local()) = node;
- break;
- }
-
- default:
- break;
- }
- }
-
- for (unsigned j = block->numSuccessors(); j--;) {
- BasicBlock* successor = block->successor(j);
- Operands<Node*>& successorAvailability = successor->ssa->availabilityAtHead;
- for (unsigned k = availability.size(); k--;) {
- Node* myNode = availability[k];
- if (!myNode)
- continue;
-
- if (!successor->ssa->liveAtHead.contains(myNode))
- continue;
-
- // Note that this may overwrite availability with a bogus node
- // at merge points. This is fine, since merge points have
- // MovHint(Phi)'s to work around this. The outcome of this is
- // you might have a program in which a node happens to remain
- // live into some block B, and separately (due to copy
- // propagation) just one of the predecessors of B issued a
- // MovHint putting that node into some local. Then in B we might
- // think that that node is a valid value for that local. Of
- // course if that local was actually live in B, B would have a
- // Phi for it. So essentially we'll have OSR exit dropping this
- // node's value into the local when we otherwise (in the DFG)
- // would have dropped undefined into the local. This seems
- // harmless.
-
- successorAvailability[k] = myNode;
- }
+ BasicBlock* root = m_graph.block(0);
+ for (unsigned argument = root->ssa->availabilityAtHead.numberOfArguments(); argument--;) {
+ root->ssa->availabilityAtHead.argument(argument) =
+ Availability::unavailable().withFlush(
+ FlushedAt(FlushedJSValue, virtualRegisterForArgument(argument)));
+ }
+ for (unsigned local = root->ssa->availabilityAtHead.numberOfLocals(); local--;)
+ root->ssa->availabilityAtHead.local(local) = Availability::unavailable();
+
+ if (m_graph.m_plan.mode == FTLForOSREntryMode) {
+ for (unsigned local = m_graph.m_profiledBlock->m_numCalleeRegisters; local--;) {
+ root->ssa->availabilityAtHead.local(local) =
+ Availability::unavailable().withFlush(
+ FlushedAt(FlushedJSValue, virtualRegisterForLocal(local)));
}
}
+ // This could be made more efficient by processing blocks in reverse postorder.
+ Operands<Availability> availability;
+ bool changed;
+ do {
+ changed = false;
+
+ for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ availability = block->ssa->availabilityAtHead;
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+
+ switch (node->op()) {
+ case SetLocal: {
+ VariableAccessData* variable = node->variableAccessData();
+ availability.operand(variable->local()) =
+ Availability(node->child1().node(), variable->flushedAt());
+ break;
+ }
+
+ case GetArgument: {
+ VariableAccessData* variable = node->variableAccessData();
+ availability.operand(variable->local()) =
+ Availability(node, variable->flushedAt());
+ break;
+ }
+
+ case MovHint:
+ case MovHintAndCheck: {
+ VariableAccessData* variable = node->variableAccessData();
+ availability.operand(variable->local()) =
+ Availability(node->child1().node());
+ break;
+ }
+
+ case ZombieHint: {
+ VariableAccessData* variable = node->variableAccessData();
+ availability.operand(variable->local()) = Availability::unavailable();
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ if (availability == block->ssa->availabilityAtTail)
+ continue;
+
+ block->ssa->availabilityAtTail = availability;
+ changed = true;
+
+ for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
+ BasicBlock* successor = block->successor(successorIndex);
+ for (unsigned i = availability.size(); i--;) {
+ successor->ssa->availabilityAtHead[i] = availability[i].merge(
+ successor->ssa->availabilityAtHead[i]);
+ }
+ }
+ }
+ } while (changed);
+
return true;
}
};
diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
index 6c37a9d..28bf505 100644
--- a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
+++ b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
@@ -36,9 +36,8 @@
class Graph;
-// Computes BasicBlock::ssa->availabiltiyAtHead/Tail. This relies on liveness
-// analysis phase having been run and the graph not having been transformed
-// after that.
+// Computes BasicBlock::ssa->availabiltiyAtHead/Tail. This is a forward flow type inference
+// over MovHints and SetLocals.
bool performOSRAvailabilityAnalysis(Graph&);
diff --git a/Source/JavaScriptCore/dfg/DFGPlan.cpp b/Source/JavaScriptCore/dfg/DFGPlan.cpp
index 365ec74..09926af 100644
--- a/Source/JavaScriptCore/dfg/DFGPlan.cpp
+++ b/Source/JavaScriptCore/dfg/DFGPlan.cpp
@@ -50,6 +50,7 @@
#include "DFGOSREntrypointCreationPhase.h"
#include "DFGPredictionInjectionPhase.h"
#include "DFGPredictionPropagationPhase.h"
+#include "DFGResurrectionForValidationPhase.h"
#include "DFGSSAConversionPhase.h"
#include "DFGStackLayoutPhase.h"
#include "DFGTierUpCheckInjectionPhase.h"
@@ -268,6 +269,8 @@
performLICM(dfg);
performLivenessAnalysis(dfg);
performCFA(dfg);
+ if (Options::validateFTLOSRExitLiveness())
+ performResurrectionForValidation(dfg);
performDCE(dfg); // We rely on this to convert dead SetLocals into the appropriate hint, and to kill dead code that won't be recognized as dead by LLVM.
performStackLayout(dfg);
performLivenessAnalysis(dfg);
diff --git a/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.cpp b/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.cpp
new file mode 100644
index 0000000..4c5f694
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.cpp
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFGResurrectionForValidationPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class ResurrectionForValidationPhase : public Phase {
+public:
+ ResurrectionForValidationPhase(Graph& graph)
+ : Phase(graph, "resurrection for validation")
+ {
+ }
+
+ bool run()
+ {
+ InsertionSet insertionSet(m_graph);
+
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (!node->hasResult())
+ continue;
+ insertionSet.insertNode(
+ nodeIndex + 1, SpecNone, Phantom, node->codeOrigin, Edge(node));
+ }
+
+ insertionSet.execute(block);
+ }
+
+ return true;
+ }
+};
+
+bool performResurrectionForValidation(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG Resurrection For Validation Phase");
+ return runPhase<ResurrectionForValidationPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.h b/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.h
new file mode 100644
index 0000000..98378ec
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGResurrectionForValidationPhase.h
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGResurrectionForValidationPhase_h
+#define DFGResurrectionForValidationPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Places a Phantom after every value-producing node, thereby disabling DCE from killing it.
+// This is useful for validating our OSR exit machinery by instituting the requirement that
+// any live-in-bytecode variable should be OSR-available. Without this phase, it's impossible
+// to make such an assertion because our DCE is more aggressive than the bytecode liveness
+// analysis.
+
+bool performResurrectionForValidation(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGResurrectionForValidationPhase_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp b/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
index fd68983..46689a2 100644
--- a/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
@@ -158,13 +158,35 @@
for (unsigned j = block->predecessors.size(); j--;) {
BasicBlock* predecessor = block->predecessors[j];
predecessor->appendNonTerminal(
- m_graph, SpecNone, Upsilon, block->last()->codeOrigin,
+ m_graph, SpecNone, Upsilon, predecessor->last()->codeOrigin,
OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
}
- m_insertionSet.insertNode(
- 0, SpecNone, MovHint, node->codeOrigin, OpInfo(variable),
- Edge(node));
+ if (m_flushedLocalOps.contains(node)) {
+ // Do nothing. For multiple reasons.
+
+ // Reason #1: If the local is flushed then we don't need to bother
+ // with a MovHint since every path to this point in the code will
+ // have flushed the bytecode variable using a SetLocal and hence
+ // the Availability::flushedAt() will agree, and that will be
+ // sufficient for figuring out how to recover the variable's value.
+
+ // Reason #2: If we had inserted a MovHint and the Phi function had
+ // died (because the only user of the value was the "flush" - i.e.
+ // some asynchronous runtime thingy) then the MovHint would turn
+ // into a ZombieHint, which would fool us into thinking that the
+ // variable is dead.
+
+ // Reason #3: If we had inserted a MovHint then even if the Phi
+ // stayed alive, we would still end up generating inefficient code
+ // since we would be telling the OSR exit compiler to use some SSA
+ // value for the bytecode variable rather than just telling it that
+ // the value was already on the stack.
+ } else {
+ m_insertionSet.insertNode(
+ 0, SpecNone, MovHint, node->codeOrigin, OpInfo(variable),
+ Edge(node));
+ }
}
}
diff --git a/Source/JavaScriptCore/dfg/DFGValueSource.h b/Source/JavaScriptCore/dfg/DFGValueSource.h
index 796c4d6..ff10892 100644
--- a/Source/JavaScriptCore/dfg/DFGValueSource.h
+++ b/Source/JavaScriptCore/dfg/DFGValueSource.h
@@ -145,6 +145,7 @@
{
switch (format) {
case DeadFlush:
+ case ConflictingFlush:
return ValueSource(SourceIsDead);
case FlushedJSValue:
return ValueSource(ValueInJSStack, where);
diff --git a/Source/JavaScriptCore/dfg/DFGVariableAccessData.h b/Source/JavaScriptCore/dfg/DFGVariableAccessData.h
index c9ba0c4..f9f4436 100644
--- a/Source/JavaScriptCore/dfg/DFGVariableAccessData.h
+++ b/Source/JavaScriptCore/dfg/DFGVariableAccessData.h
@@ -26,6 +26,7 @@
#ifndef DFGVariableAccessData_h
#define DFGVariableAccessData_h
+#include "DFGCommon.h"
#include "DFGDoubleFormatState.h"
#include "DFGFlushFormat.h"
#include "DFGFlushedAt.h"
@@ -39,6 +40,8 @@
namespace JSC { namespace DFG {
+struct Node;
+
enum DoubleBallot { VoteValue, VoteDouble };
class VariableAccessData : public UnionFind<VariableAccessData> {
