dfg/DFGObjectMaterializationData.cpp
dfg/DFGOperations.cpp
dfg/DFGPhantomCanonicalizationPhase.cpp
+ dfg/DFGPhantomInsertionPhase.cpp
dfg/DFGPhantomRemovalPhase.cpp
dfg/DFGPhase.cpp
dfg/DFGPhiChildren.cpp
+2015-04-22 Filip Pizlo <fpizlo@apple.com>
+
+ DFG should insert Phantoms late using BytecodeKills and block-local OSR availability
+ https://bugs.webkit.org/show_bug.cgi?id=143735
+
+ Reviewed by Geoffrey Garen.
+
+ We've always had bugs arising from the fact that we would MovHint something into a local,
+ and then fail to keep it alive. We would then try to keep things alive by putting Phantoms
+ on those Nodes that were MovHinted. But this became increasingly tricky. Given the
+ sophistication of the transformations we are doing today, this approach is just not sound
+ anymore.
+
+ This comprehensively fixes these bugs by having the DFG backend automatically insert
+ Phantoms just before codegen based on bytecode liveness. To make this practical, this also
+ makes it much faster to query bytecode liveness.
+
+ It's about as perf-neutral as it gets for a change that increases compiler work without
+ actually optimizing anything. Later changes will remove the old Phantom-preserving logic,
+ which should then speed us up. I can't really report concrete slow-down numbers because
+ they are low enough to basically be in the noise. For example, a 20-iteration run of
+ SunSpider yields "maybe 0.8% slower", whatever that means.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * bytecode/BytecodeLivenessAnalysis.cpp:
+ (JSC::BytecodeLivenessAnalysis::computeFullLiveness):
+ * bytecode/FullBytecodeLiveness.h:
+ (JSC::FullBytecodeLiveness::getLiveness):
+ * bytecode/VirtualRegister.h:
+ (JSC::VirtualRegister::operator+):
+ (JSC::VirtualRegister::operator-):
+ * dfg/DFGForAllKills.h:
+ (JSC::DFG::forAllLiveNodesAtTail):
+ (JSC::DFG::forAllKilledOperands):
+ (JSC::DFG::forAllKilledNodesAtNodeIndex):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::isLiveInBytecode):
+ (JSC::DFG::Graph::localsLiveInBytecode):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::forAllLocalsLiveInBytecode):
+ (JSC::DFG::Graph::forAllLiveInBytecode):
+ * dfg/DFGMayExit.cpp:
+ (JSC::DFG::mayExit):
+ * dfg/DFGMovHintRemovalPhase.cpp:
+ * dfg/DFGNodeType.h:
+ * dfg/DFGPhantomInsertionPhase.cpp: Added.
+ (JSC::DFG::performPhantomInsertion):
+ * dfg/DFGPhantomInsertionPhase.h: Added.
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ * dfg/DFGScoreBoard.h:
+ (JSC::DFG::ScoreBoard::sortFree):
+ (JSC::DFG::ScoreBoard::assertClear):
+ * dfg/DFGVirtualRegisterAllocationPhase.cpp:
+ (JSC::DFG::VirtualRegisterAllocationPhase::run):
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::LowerDFGToLLVM::buildExitArguments):
+ * tests/stress/phantom-inadequacy.js: Added.
+ (bar):
+ (baz):
+ (foo):
+
2015-04-23 Filip Pizlo <fpizlo@apple.com>
Rename HardPhantom to MustGenerate.
<ClCompile Include="..\dfg\DFGObjectAllocationSinkingPhase.cpp" />
<ClCompile Include="..\dfg\DFGObjectMaterializationData.cpp" />
<ClCompile Include="..\dfg\DFGPhantomCanonicalizationPhase.cpp" />
+ <ClCompile Include="..\dfg\DFGPhantomInsertionPhase.cpp" />
<ClCompile Include="..\dfg\DFGPhantomRemovalPhase.cpp" />
<ClCompile Include="..\dfg\DFGPhase.cpp" />
<ClCompile Include="..\dfg\DFGPhiChildren.cpp" />
<ClInclude Include="..\dfg\DFGOSRExitJumpPlaceholder.h" />
<ClInclude Include="..\dfg\DFGOSRExitPreparation.h" />
<ClInclude Include="..\dfg\DFGPhantomCanonicalizationPhase.h" />
+ <ClInclude Include="..\dfg\DFGPhantomInsertionPhase.h" />
<ClInclude Include="..\dfg\DFGPhantomRemovalPhase.h" />
<ClInclude Include="..\dfg\DFGPhase.h" />
<ClInclude Include="..\dfg\DFGPhiChildren.h" />
0F620174143FCD330068B77C /* DFGVariableAccessData.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F620172143FCD2F0068B77C /* DFGVariableAccessData.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F620176143FCD3B0068B77C /* DFGBasicBlock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F620170143FCD2F0068B77C /* DFGBasicBlock.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F620177143FCD3F0068B77C /* DFGAbstractValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0F6237971AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6237951AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp */; };
+ 0F6237981AE45CA700D402EA /* DFGPhantomInsertionPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6237961AE45CA700D402EA /* DFGPhantomInsertionPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F63943F15C75F19006A597C /* DFGTypeCheckHoistingPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F63943D15C75F14006A597C /* DFGTypeCheckHoistingPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F63944015C75F1D006A597C /* DFGTypeCheckHoistingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F63943C15C75F14006A597C /* DFGTypeCheckHoistingPhase.cpp */; };
0F63945415D07055006A597C /* ArrayProfile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F63945115D07051006A597C /* ArrayProfile.cpp */; };
0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAbstractValue.h; path = dfg/DFGAbstractValue.h; sourceTree = "<group>"; };
0F620170143FCD2F0068B77C /* DFGBasicBlock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBasicBlock.h; path = dfg/DFGBasicBlock.h; sourceTree = "<group>"; };
0F620172143FCD2F0068B77C /* DFGVariableAccessData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGVariableAccessData.h; path = dfg/DFGVariableAccessData.h; sourceTree = "<group>"; };
+ 0F6237951AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPhantomInsertionPhase.cpp; path = dfg/DFGPhantomInsertionPhase.cpp; sourceTree = "<group>"; };
+ 0F6237961AE45CA700D402EA /* DFGPhantomInsertionPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPhantomInsertionPhase.h; path = dfg/DFGPhantomInsertionPhase.h; sourceTree = "<group>"; };
0F63943C15C75F14006A597C /* DFGTypeCheckHoistingPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGTypeCheckHoistingPhase.cpp; path = dfg/DFGTypeCheckHoistingPhase.cpp; sourceTree = "<group>"; };
0F63943D15C75F14006A597C /* DFGTypeCheckHoistingPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGTypeCheckHoistingPhase.h; path = dfg/DFGTypeCheckHoistingPhase.h; sourceTree = "<group>"; };
0F63945115D07051006A597C /* ArrayProfile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ArrayProfile.cpp; sourceTree = "<group>"; };
0F235BEA17178E7300690C7F /* DFGOSRExitPreparation.h */,
0F7B365F197C525C00ED1DDC /* DFGPhantomCanonicalizationPhase.cpp */,
0F7B3660197C525C00ED1DDC /* DFGPhantomCanonicalizationPhase.h */,
+ 0F6237951AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp */,
+ 0F6237961AE45CA700D402EA /* DFGPhantomInsertionPhase.h */,
0FBFDD02196C92BF007A5BFA /* DFGPhantomRemovalPhase.cpp */,
0FBFDD03196C92BF007A5BFA /* DFGPhantomRemovalPhase.h */,
0FFFC94F14EF909500C72532 /* DFGPhase.cpp */,
BC18C42E0E16F5CD00B34460 /* JSWrapperObject.h in Headers */,
BCFD8C930EEB2EE700283848 /* JumpTable.h in Headers */,
A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */,
+ 0F6237981AE45CA700D402EA /* DFGPhantomInsertionPhase.h in Headers */,
969A072A0ED1CE6900F1F681 /* Label.h in Headers */,
960097A60EBABB58007A7297 /* LabelScope.h in Headers */,
0FB5467714F59B5C002C2989 /* LazyOperandValueProfile.h in Headers */,
95AB83560DA43C3000BC83F3 /* ProfileNode.cpp in Sources */,
0FF729AD166AD35C000F5BA3 /* ProfilerBytecode.cpp in Sources */,
0FF729AE166AD35C000F5BA3 /* ProfilerBytecodes.cpp in Sources */,
+ 0F6237971AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp in Sources */,
0F13912916771C33009CCB07 /* ProfilerBytecodeSequence.cpp in Sources */,
0FF729AF166AD35C000F5BA3 /* ProfilerCompilation.cpp in Sources */,
0FF729B0166AD35C000F5BA3 /* ProfilerCompilationKind.cpp in Sources */,
{
FastBitVector out;
- result.m_map.clear();
+ result.m_map.resize(m_codeBlock->instructions().size());
for (unsigned i = m_basicBlocks.size(); i--;) {
BytecodeBasicBlock* block = m_basicBlocks[i].get();
for (unsigned i = block->bytecodeOffsets().size(); i--;) {
unsigned bytecodeOffset = block->bytecodeOffsets()[i];
stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, out);
- result.m_map.add(bytecodeOffset, out);
+ result.m_map[bytecodeOffset] = out;
}
}
}
public:
const FastBitVector& getLiveness(unsigned bytecodeIndex) const
{
- BytecodeToBitmapMap::const_iterator iter = m_map.find(bytecodeIndex);
- ASSERT(iter != m_map.end());
- return iter->value;
+ return m_map[bytecodeIndex];
}
bool operandIsLive(int operand, unsigned bytecodeIndex) const
private:
friend class BytecodeLivenessAnalysis;
- BytecodeToBitmapMap m_map;
+ Vector<FastBitVector, 0, UnsafeVectorOverflow> m_map;
};
} // namespace JSC
{
return VirtualRegister(offset() - value);
}
+ VirtualRegister operator+(VirtualRegister value) const
+ {
+ return VirtualRegister(offset() + value.offset());
+ }
+ VirtualRegister operator-(VirtualRegister value) const
+ {
+ return VirtualRegister(offset() - value.offset());
+ }
VirtualRegister& operator+=(int value)
{
return *this = *this + value;
DFG_ASSERT(graph, block->terminal(), block->terminal()->origin.forExit.isSet());
AvailabilityMap& availabilityMap = block->ssa->availabilityAtTail;
- for (unsigned i = availabilityMap.m_locals.size(); i--;) {
- VirtualRegister reg = availabilityMap.m_locals.virtualRegisterForIndex(i);
-
- if (!graph.isLiveInBytecode(reg, block->terminal()->origin.forExit))
- continue;
-
- availabilityMap.closeStartingWithLocal(
- reg,
- [&] (Node* node) -> bool {
- return seen.contains(node);
- },
- [&] (Node* node) -> bool {
- if (!seen.add(node).isNewEntry)
- return false;
- functor(node);
- return true;
- });
- }
+ graph.forAllLocalsLiveInBytecode(
+ block->terminal()->origin.forExit,
+ [&] (VirtualRegister reg) {
+ availabilityMap.closeStartingWithLocal(
+ reg,
+ [&] (Node* node) -> bool {
+ return seen.contains(node);
+ },
+ [&] (Node* node) -> bool {
+ if (!seen.add(node).isNewEntry)
+ return false;
+ functor(node);
+ return true;
+ });
+ });
}
+// This tells you those things that die on the boundary between nodeBefore and nodeAfter. It is
+// conservative in the sense that it might resort to telling you some things that are still live at
+// nodeAfter.
template<typename Functor>
-void forAllKilledOperands(Graph& graph, CodeOrigin before, Node* nodeAfter, const Functor& functor)
+void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const Functor& functor)
{
+ CodeOrigin before = nodeBefore->origin.forExit;
CodeOrigin after = nodeAfter->origin.forExit;
+ VirtualRegister alreadyNoted;
+ if (!!after) {
+ // If we MovHint something that is live at the time, then we kill the old value.
+ if (nodeAfter->containsMovHint()) {
+ VirtualRegister reg = nodeAfter->unlinkedLocal();
+ if (graph.isLiveInBytecode(reg, after)) {
+ functor(reg);
+ alreadyNoted = reg;
+ }
+ }
+ }
+
if (!before) {
if (!after)
return;
// The true before-origin is the origin at predecessors that jump to us. But there can be
// many such predecessors and they will likely all have a different origin. So, it's better
// to do the conservative thing.
- for (unsigned i = graph.block(0)->variablesAtHead.numberOfLocals(); i--;) {
- VirtualRegister reg = virtualRegisterForLocal(i);
- if (graph.isLiveInBytecode(reg, after))
- functor(reg);
- }
+ graph.forAllLocalsLiveInBytecode(after, functor);
return;
}
- // If we MovHint something that is live at the time, then we kill the old value.
- VirtualRegister alreadyNoted;
- if (nodeAfter->containsMovHint()) {
- VirtualRegister reg = nodeAfter->unlinkedLocal();
- if (graph.isLiveInBytecode(reg, after)) {
- functor(reg);
- alreadyNoted = reg;
- }
- }
-
if (before == after)
return;
// before could be unset even if after is, but the opposite cannot happen.
ASSERT(!!after);
+ // It's easier to do this if the inline call frames are the same. This is way faster than the
+ // other loop, below.
+ if (before.inlineCallFrame == after.inlineCallFrame) {
+ int stackOffset = before.inlineCallFrame ? before.inlineCallFrame->stackOffset : 0;
+ CodeBlock* codeBlock = graph.baselineCodeBlockFor(before.inlineCallFrame);
+ FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
+ const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
+ const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
+
+ for (unsigned relativeLocal = codeBlock->m_numCalleeRegisters; relativeLocal--;) {
+ if (liveBefore.get(relativeLocal) && !liveAfter.get(relativeLocal))
+ functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
+ }
+
+ return;
+ }
+
// Detect kills the super conservative way: it is killed if it was live before and dead after.
- for (unsigned i = graph.block(0)->variablesAtHead.numberOfLocals(); i--;) {
- VirtualRegister reg = virtualRegisterForLocal(i);
- if (reg == alreadyNoted)
- continue;
- if (graph.isLiveInBytecode(reg, before) && !graph.isLiveInBytecode(reg, after))
+ BitVector liveAfter = graph.localsLiveInBytecode(after);
+ graph.forAllLocalsLiveInBytecode(
+ before,
+ [&] (VirtualRegister reg) {
+ if (reg == alreadyNoted)
+ return;
+ if (liveAfter.get(reg.toLocal()))
+ return;
functor(reg);
- }
+ });
}
// Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
}
});
- CodeOrigin before;
+ Node* before = nullptr;
if (nodeIndex)
- before = block->at(nodeIndex - 1)->origin.forExit;
+ before = block->at(nodeIndex - 1);
forAllKilledOperands(
graph, before, node,
// Arguments are always live. This would be redundant if it wasn't for our
// op_call_varargs inlining.
- // FIXME: 'this' might not be live, but we don't have a way of knowing.
- // https://bugs.webkit.org/show_bug.cgi?id=128519
if (reg.isArgument()
&& static_cast<size_t>(reg.toArgument()) < inlineCallFrame->arguments.size())
return true;
return true;
}
+BitVector Graph::localsLiveInBytecode(CodeOrigin codeOrigin)
+{
+ BitVector result;
+ result.ensureSize(block(0)->variablesAtHead.numberOfLocals());
+ forAllLocalsLiveInBytecode(
+ codeOrigin,
+ [&] (VirtualRegister reg) {
+ ASSERT(reg.isLocal());
+ result.quickSet(reg.toLocal());
+ });
+ return result;
+}
+
unsigned Graph::frameRegisterCount()
{
unsigned result = m_nextMachineLocal + std::max(m_parameterSlots, static_cast<unsigned>(maxFrameExtentForSlowPathCallInRegisters));
#if ENABLE(DFG_JIT)
#include "AssemblyHelpers.h"
+#include "BytecodeLivenessAnalysisInlines.h"
#include "CodeBlock.h"
#include "DFGArgumentPosition.h"
#include "DFGBasicBlock.h"
#include "DFGPlan.h"
#include "DFGPrePostNumbering.h"
#include "DFGScannable.h"
+#include "FullBytecodeLiveness.h"
#include "JSStack.h"
#include "MethodOfGettingAValueProfile.h"
#include <unordered_map>
FullBytecodeLiveness& livenessFor(CodeBlock*);
FullBytecodeLiveness& livenessFor(InlineCallFrame*);
+
+ // Quickly query if a single local is live at the given point. This is faster than calling
+ // forAllLiveInBytecode() if you will only query one local. But, if you want to know all of the
+ // locals live, then calling this for each local is much slower than forAllLiveInBytecode().
bool isLiveInBytecode(VirtualRegister, CodeOrigin);
+ // Quickly get all of the non-argument locals live at the given point. This doesn't give you
+ // any arguments because those are all presumed live. You can call forAllLiveInBytecode() to
+ // also get the arguments. This is much faster than calling isLiveInBytecode() for each local.
+ template<typename Functor>
+ void forAllLocalsLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
+ {
+ // Support for not redundantly reporting arguments. Necessary because in case of a varargs
+ // call, only the callee knows that arguments are live while in the case of a non-varargs
+ // call, both callee and caller will see the variables live.
+ VirtualRegister exclusionStart;
+ VirtualRegister exclusionEnd;
+
+ for (;;) {
+ InlineCallFrame* inlineCallFrame = codeOrigin.inlineCallFrame;
+ VirtualRegister stackOffset(inlineCallFrame ? inlineCallFrame->stackOffset : 0);
+
+ if (inlineCallFrame) {
+ if (inlineCallFrame->isClosureCall)
+ functor(stackOffset + JSStack::Callee);
+ if (inlineCallFrame->isVarargs())
+ functor(stackOffset + JSStack::ArgumentCount);
+ }
+
+ CodeBlock* codeBlock = baselineCodeBlockFor(inlineCallFrame);
+ FullBytecodeLiveness& fullLiveness = livenessFor(codeBlock);
+ const FastBitVector& liveness = fullLiveness.getLiveness(codeOrigin.bytecodeIndex);
+ for (unsigned relativeLocal = codeBlock->m_numCalleeRegisters; relativeLocal--;) {
+ VirtualRegister reg = stackOffset + virtualRegisterForLocal(relativeLocal);
+
+ // Don't report if our callee already reported.
+ if (reg >= exclusionStart && reg < exclusionEnd)
+ continue;
+
+ if (liveness.get(relativeLocal))
+ functor(reg);
+ }
+
+ if (!inlineCallFrame)
+ break;
+
+ // Arguments are always live. This would be redundant if it wasn't for our
+ // op_call_varargs inlining. See the comment above.
+ exclusionStart = stackOffset + CallFrame::argumentOffsetIncludingThis(0);
+ exclusionEnd = stackOffset + CallFrame::argumentOffsetIncludingThis(inlineCallFrame->arguments.size());
+
+ // We will always have a "this" argument and exclusionStart should be a smaller stack
+ // offset than exclusionEnd.
+ ASSERT(exclusionStart < exclusionEnd);
+
+ for (VirtualRegister reg = exclusionStart; reg < exclusionEnd; reg += 1)
+ functor(reg);
+
+ codeOrigin = inlineCallFrame->caller;
+ }
+ }
+
+ // Get a BitVector of all of the non-argument locals live right now. This is mostly useful if
+ // you want to compare two sets of live locals from two different CodeOrigins.
+ BitVector localsLiveInBytecode(CodeOrigin);
+
+ // Tells you all of the arguments and locals live at the given CodeOrigin. This is a small
+ // extension to forAllLocalsLiveInBytecode(), since all arguments are always presumed live.
+ template<typename Functor>
+ void forAllLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
+ {
+ forAllLocalsLiveInBytecode(codeOrigin, functor);
+
+ // Report all arguments as being live.
+ for (unsigned argument = block(0)->variablesAtHead.numberOfArguments(); argument--;)
+ functor(virtualRegisterForArgument(argument));
+ }
+
BytecodeKills& killsFor(CodeBlock*);
BytecodeKills& killsFor(InlineCallFrame*);
case GetScope:
case PhantomLocal:
case CountExecution:
+ case Jump:
+ case Branch:
+ case Unreachable:
break;
default:
Epoch currentEpoch = Epoch::first();
- for (unsigned i = m_state.size(); i--;) {
- VirtualRegister reg = m_state.virtualRegisterForIndex(i);
- if (m_graph.isLiveInBytecode(reg, block->terminal()->origin.forExit))
- m_state[i] = currentEpoch;
- else
- m_state[i] = Epoch();
- }
+ m_state.fill(Epoch());
+ m_graph.forAllLiveInBytecode(
+ block->terminal()->origin.forExit,
+ [&] (VirtualRegister reg) {
+ m_state.operand(reg) = currentEpoch;
+ });
if (verbose)
dataLog(" Locals: ", m_state, "\n");
if (nodeIndex) {
forAllKilledOperands(
- m_graph, block->at(nodeIndex - 1)->origin.forExit, node,
+ m_graph, block->at(nodeIndex - 1), node,
[&] (VirtualRegister reg) {
// This function is a bit sloppy - it might claim to kill a local even if
// it's still live after. We need to protect against that.
/* Nodes for local variable access. These nodes are linked together using Phi nodes. */\
/* Any two nodes that are part of the same Phi graph will share the same */\
/* VariableAccessData, and thus will share predictions. FIXME: We should come up with */\
- /* better names for a lot of these. https://bugs.webkit.org/show_bug.cgi?id=137307 */\
- macro(GetLocal, NodeResultJS) \
+ /* better names for a lot of these. https://bugs.webkit.org/show_bug.cgi?id=137307. */\
+ /* Note that GetLocal is MustGenerate because it's our only way of knowing that some other */\
+ /* basic block might have read a local variable in bytecode. We only remove GetLocals if it */\
+ /* is redundant because of an earlier GetLocal or SetLocal in the same block. We could make */\
+ /* these not MustGenerate and use a more sophisticated analysis to insert PhantomLocals in */\
+ /* the same way that we insert Phantoms. https://bugs.webkit.org/show_bug.cgi?id=144086 */\
+ macro(GetLocal, NodeResultJS | NodeMustGenerate) \
macro(SetLocal, 0) \
\
macro(PutStack, NodeMustGenerate) \
--- /dev/null
+/*
+ * Copyright (C) 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
+ * 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 "DFGPhantomInsertionPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "BytecodeLivenessAnalysisInlines.h"
+#include "DFGForAllKills.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGMayExit.h"
+#include "DFGPhase.h"
+#include "DFGPredictionPropagationPhase.h"
+#include "DFGVariableAccessDataDump.h"
+#include "JSCInlines.h"
+#include "OperandsInlines.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+bool verbose = false;
+
+class PhantomInsertionPhase : public Phase {
+public:
+ PhantomInsertionPhase(Graph& graph)
+ : Phase(graph, "phantom insertion")
+ , m_insertionSet(graph)
+ , m_values(OperandsLike, graph.block(0)->variablesAtHead)
+ {
+ }
+
+ bool run()
+ {
+ // We assume that DCE has already run. If we run before DCE then we think that all
+ // SetLocals execute, which is inaccurate. That causes us to insert too few Phantoms.
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_refCountState == ExactRefCount);
+
+ if (verbose) {
+ dataLog("Graph before Phantom insertion:\n");
+ m_graph.dump();
+ }
+
+ m_graph.clearEpochs();
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder())
+ handleBlock(block);
+
+ if (verbose) {
+ dataLog("Graph after Phantom insertion:\n");
+ m_graph.dump();
+ }
+
+ return true;
+ }
+
+private:
+ void handleBlock(BasicBlock* block)
+ {
+ m_values.fill(nullptr);
+
+ Epoch currentEpoch = Epoch::first();
+ unsigned lastExitingIndex = 0;
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (verbose)
+ dataLog("Considering ", node, "\n");
+
+ switch (node->op()) {
+ case MovHint:
+ m_values.operand(node->unlinkedLocal()) = node->child1().node();
+ break;
+
+ case ZombieHint:
+ m_values.operand(node->unlinkedLocal()) = nullptr;
+ break;
+
+ case SetLocal:
+ case GetLocal:
+ case SetArgument:
+ m_values.operand(node->local()) = nullptr;
+ break;
+
+ default:
+ break;
+ }
+
+ if (mayExit(m_graph, node)) {
+ currentEpoch.bump();
+ lastExitingIndex = nodeIndex;
+ }
+
+ m_graph.doToChildren(
+ node,
+ [&] (Edge edge) {
+ edge->setEpoch(currentEpoch);
+ });
+
+ node->setEpoch(currentEpoch);
+
+ auto killAction = [&] (VirtualRegister reg) {
+ if (verbose)
+ dataLog(" Killed operand: ", reg, "\n");
+
+ Node* killedNode = m_values.operand(reg);
+ if (!killedNode)
+ return;
+
+ // We only need to insert a Phantom if the node hasn't been used since the last
+ // exit, and was born before the last exit.
+ if (killedNode->epoch() == currentEpoch)
+ return;
+
+ if (verbose) {
+ dataLog(
+ " Inserting Phantom on ", killedNode, " after ",
+ block->at(lastExitingIndex), "\n");
+ }
+
+ // We have exact ref counts, so creating a new use means that we have to increment
+ // the ref count.
+ killedNode->postfixRef();
+
+ m_insertionSet.insertNode(
+ lastExitingIndex + 1, SpecNone, Phantom, block->at(lastExitingIndex)->origin,
+ killedNode->defaultEdge());
+ };
+
+ if (nodeIndex + 1 == block->size()) {
+ // Should a MovHinted value be kept alive? If the value has been SetLocal'd then
+ // the answer is no. But we may have a value that is live here and dead in
+ // successors because we had jettisoned those successors that would have used the
+ // value. Hence, anything live here should be kept alive.
+ m_graph.forAllLiveInBytecode(node->origin.forExit, killAction);
+ } else
+ forAllKilledOperands(m_graph, node, block->at(nodeIndex + 1), killAction);
+ }
+
+ m_insertionSet.execute(block);
+ }
+
+ InsertionSet m_insertionSet;
+ Operands<Node*> m_values;
+};
+
+} // anonymous namespace
+
+bool performPhantomInsertion(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG Phantom Insertion Phase");
+ return runPhase<PhantomInsertionPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
--- /dev/null
+/*
+ * Copyright (C) 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
+ * 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 DFGPhantomInsertionPhase_h
+#define DFGPhantomInsertionPhase_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Inserts Phantoms based on bytecode liveness.
+
+bool performPhantomInsertion(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGPhantomInsertionPhase_h
#include "DFGOSREntrypointCreationPhase.h"
#include "DFGObjectAllocationSinkingPhase.h"
#include "DFGPhantomCanonicalizationPhase.h"
+#include "DFGPhantomInsertionPhase.h"
#include "DFGPhantomRemovalPhase.h"
#include "DFGPredictionInjectionPhase.h"
#include "DFGPredictionPropagationPhase.h"
performPhantomRemoval(dfg);
performCPSRethreading(dfg);
performDCE(dfg);
+ performPhantomInsertion(dfg);
performStackLayout(dfg);
performVirtualRegisterAllocation(dfg);
performWatchpointCollection(dfg);
assertClear();
}
+ void sortFree()
+ {
+ std::sort(m_free.begin(), m_free.end());
+ }
+
void assertClear()
{
-#if !ASSERT_DISABLED
+ if (ASSERT_DISABLED)
+ return;
+
// For every entry in the used list the use count of the virtual register should be zero, or max, due to it being a preserved local.
for (size_t i = 0; i < m_used.size(); ++i)
- ASSERT(!m_used[i] || m_used[i] == max());
+ RELEASE_ASSERT(!m_used[i] || m_used[i] == max());
// For every entry in the free list, the use count should be zero.
for (size_t i = 0; i < m_free.size(); ++i)
- ASSERT(!m_used[m_free[i]]);
+ RELEASE_ASSERT(!m_used[m_free[i]]);
// There must not be duplicates in the free list.
for (size_t i = 0; i < m_free.size(); ++i) {
for (size_t j = i + 1; j < m_free.size(); ++j)
- ASSERT(m_free[i] != m_free[j]);
+ RELEASE_ASSERT(m_free[i] != m_free[j]);
}
-#endif
}
VirtualRegister allocate()
continue;
if (!block->isReachable)
continue;
+ if (!ASSERT_DISABLED) {
+ // Force usage of highest-numbered virtual registers.
+ scoreBoard.sortFree();
+ }
for (size_t indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
Node* node = block->at(indexInBlock);
arguments.append(lowValue.value());
AvailabilityMap availabilityMap = this->availabilityMap();
+ availabilityMap.m_locals.fill(Availability());
- for (unsigned i = 0; i < exit.m_values.size(); ++i) {
- int operand = exit.m_values.operandForIndex(i);
- bool isLive = m_graph.isLiveInBytecode(VirtualRegister(operand), codeOrigin);
- if (!isLive)
- availabilityMap.m_locals[i] = Availability();
- }
+ m_graph.forAllLiveInBytecode(
+ codeOrigin,
+ [&] (VirtualRegister reg) {
+ availabilityMap.m_locals.operand(reg) =
+ this->availabilityMap().m_locals.operand(reg);
+ });
availabilityMap.prune();
--- /dev/null
+function bar() {
+ return 42.5;
+}
+noInline(bar);
+
+function baz(value) {
+ if (value != 42.5)
+ throw "Error: bad value: " + value;
+}
+noInline(baz);
+
+var True = true;
+function foo(a) {
+ var x = bar();
+ var tmp = 0;
+ if (True) {
+ var tmp2 = x;
+ tmp = a + 1;
+ baz(tmp2);
+ }
+ return x + 1 + tmp;
+}
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(1);
+ if (result != 42.5 + 1 + 1 + 1)
+ throw "Error: bad result: " + result;
+}
+
+var result = foo(2147483647);
+if (result != 42.5 + 1 + 2147483647 + 1)
+ throw "Error: bad result at end: " + result;
git://git.webkit.org / WebKit-https.git / commitdiff