DFG should insert Phantoms late using BytecodeKills and block-local OSR availability
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Apr 2015 20:47:31 +0000 (20:47 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Apr 2015 20:47:31 +0000 (20:47 +0000)
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183207 268f45cc-cd09-0410-ab3c-d52691b4dbfc

20 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp
Source/JavaScriptCore/bytecode/FullBytecodeLiveness.h
Source/JavaScriptCore/bytecode/VirtualRegister.h
Source/JavaScriptCore/dfg/DFGForAllKills.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/dfg/DFGScoreBoard.h
Source/JavaScriptCore/dfg/DFGVirtualRegisterAllocationPhase.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/tests/stress/phantom-inadequacy.js [new file with mode: 0644]

index 2ac036a..518b474 100644 (file)
@@ -203,6 +203,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGObjectMaterializationData.cpp
     dfg/DFGOperations.cpp
     dfg/DFGPhantomCanonicalizationPhase.cpp
+    dfg/DFGPhantomInsertionPhase.cpp
     dfg/DFGPhantomRemovalPhase.cpp
     dfg/DFGPhase.cpp
     dfg/DFGPhiChildren.cpp
index 1c23fd1..f8e95d7 100644 (file)
@@ -1,3 +1,67 @@
+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.
index 905f4df..02e379c 100644 (file)
     <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" />
index b8083ba..c790580 100644 (file)
                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 */,
index e7dfc94..80173ac 100644 (file)
@@ -237,7 +237,7 @@ void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
 {
     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();
@@ -249,7 +249,7 @@ void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
         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;
         }
     }
 }
index 9287b39..864af75 100644 (file)
@@ -38,9 +38,7 @@ class FullBytecodeLiveness {
 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
@@ -51,7 +49,7 @@ public:
 private:
     friend class BytecodeLivenessAnalysis;
     
-    BytecodeToBitmapMap m_map;
+    Vector<FastBitVector, 0, UnsafeVectorOverflow> m_map;
 };
 
 } // namespace JSC
index 07504a3..613088e 100644 (file)
@@ -82,6 +82,14 @@ public:
     {
         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;
index e12167c..33dafb8 100644 (file)
@@ -51,69 +51,88 @@ void forAllLiveNodesAtTail(Graph& graph, BasicBlock* block, const Functor& funct
     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.
@@ -140,9 +159,9 @@ void forAllKilledNodesAtNodeIndex(
             }
         });
 
-    CodeOrigin before;
+    Node* before = nullptr;
     if (nodeIndex)
-        before = block->at(nodeIndex - 1)->origin.forExit;
+        before = block->at(nodeIndex - 1);
 
     forAllKilledOperands(
         graph, before, node,
index 1dd4197..4c2d3fb 100644 (file)
@@ -944,8 +944,6 @@ bool Graph::isLiveInBytecode(VirtualRegister operand, CodeOrigin codeOrigin)
 
         // 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;
@@ -956,6 +954,19 @@ bool Graph::isLiveInBytecode(VirtualRegister operand, CodeOrigin codeOrigin)
     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));
index 4eabdcc..c5c10d4 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "AssemblyHelpers.h"
+#include "BytecodeLivenessAnalysisInlines.h"
 #include "CodeBlock.h"
 #include "DFGArgumentPosition.h"
 #include "DFGBasicBlock.h"
@@ -41,6 +42,7 @@
 #include "DFGPlan.h"
 #include "DFGPrePostNumbering.h"
 #include "DFGScannable.h"
+#include "FullBytecodeLiveness.h"
 #include "JSStack.h"
 #include "MethodOfGettingAValueProfile.h"
 #include <unordered_map>
@@ -677,8 +679,84 @@ public:
     
     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*);
     
index c142744..135eb51 100644 (file)
@@ -88,6 +88,9 @@ bool mayExit(Graph& graph, Node* node)
     case GetScope:
     case PhantomLocal:
     case CountExecution:
+    case Jump:
+    case Branch:
+    case Unreachable:
         break;
         
     default:
index a908bc7..e2cf37e 100644 (file)
@@ -80,13 +80,12 @@ private:
         
         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");
@@ -114,7 +113,7 @@ private:
             
             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.
index f82d912..b2fd743 100644 (file)
@@ -55,8 +55,13 @@ namespace JSC { namespace DFG {
     /* 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) \
diff --git a/Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.cpp b/Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.cpp
new file mode 100644 (file)
index 0000000..7171698
--- /dev/null
@@ -0,0 +1,181 @@
+/*
+ * 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)
+
diff --git a/Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.h b/Source/JavaScriptCore/dfg/DFGPhantomInsertionPhase.h
new file mode 100644 (file)
index 0000000..902975b
--- /dev/null
@@ -0,0 +1,43 @@
+/*
+ * 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
index f51bee0..0b618dc 100644 (file)
@@ -52,6 +52,7 @@
 #include "DFGOSREntrypointCreationPhase.h"
 #include "DFGObjectAllocationSinkingPhase.h"
 #include "DFGPhantomCanonicalizationPhase.h"
+#include "DFGPhantomInsertionPhase.h"
 #include "DFGPhantomRemovalPhase.h"
 #include "DFGPredictionInjectionPhase.h"
 #include "DFGPredictionPropagationPhase.h"
@@ -320,6 +321,7 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
         performPhantomRemoval(dfg);
         performCPSRethreading(dfg);
         performDCE(dfg);
+        performPhantomInsertion(dfg);
         performStackLayout(dfg);
         performVirtualRegisterAllocation(dfg);
         performWatchpointCollection(dfg);
index 15af609..c8795c8 100644 (file)
@@ -55,21 +55,27 @@ public:
         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()
index dba9f12..e5e133d 100644 (file)
@@ -55,6 +55,10 @@ public:
                 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);
         
index 90cb9aa..69d6962 100644 (file)
@@ -7199,13 +7199,14 @@ private:
             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();
         
diff --git a/Source/JavaScriptCore/tests/stress/phantom-inadequacy.js b/Source/JavaScriptCore/tests/stress/phantom-inadequacy.js
new file mode 100644 (file)
index 0000000..bb72e22
--- /dev/null
@@ -0,0 +1,33 @@
+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;