Changeset 183207 in webkit

Timestamp:

Apr 23, 2015, 1:47:31 PM (10 years ago)

Author:

[email protected]

Message:

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):

Location:

trunk/Source/JavaScriptCore

Files:

• CMakeLists.txt (modified) (1 diff)
• ChangeLog (modified) (1 diff)
• JavaScriptCore.vcxproj/JavaScriptCore.vcxproj (modified) (2 diffs)
• JavaScriptCore.xcodeproj/project.pbxproj (modified) (5 diffs)
• bytecode/BytecodeLivenessAnalysis.cpp (modified) (2 diffs)
• bytecode/FullBytecodeLiveness.h (modified) (2 diffs)
• bytecode/VirtualRegister.h (modified) (1 diff)
• dfg/DFGForAllKills.h (modified) (4 diffs)
• dfg/DFGGraph.cpp (modified) (2 diffs)
• dfg/DFGGraph.h (modified) (3 diffs)
• dfg/DFGMayExit.cpp (modified) (1 diff)
• dfg/DFGMovHintRemovalPhase.cpp (modified) (2 diffs)
• dfg/DFGNodeType.h (modified) (1 diff)
• dfg/DFGPhantomInsertionPhase.cpp (added)
• dfg/DFGPhantomInsertionPhase.h (added)
• dfg/DFGPlan.cpp (modified) (2 diffs)
• dfg/DFGScoreBoard.h (modified) (1 diff)
• dfg/DFGVirtualRegisterAllocationPhase.cpp (modified) (1 diff)
• ftl/FTLLowerDFGToLLVM.cpp (modified) (1 diff)
• tests/stress/phantom-inadequacy.js (added)

trunk/Source/JavaScriptCore/CMakeLists.txt

@@ -204 +204 @@
     dfg/DFGOperations.cpp
     dfg/DFGPhantomCanonicalizationPhase.cpp
+    dfg/DFGPhantomInsertionPhase.cpp
     dfg/DFGPhantomRemovalPhase.cpp
     dfg/DFGPhase.cpp

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2015-04-22  Filip Pizlo  <[email protected]>
+
+        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  <[email protected]>
 

trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj

@@ -448 +448 @@
     <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" />
@@ -1143 +1144 @@
     <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" />

trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

@@ -349 +349 @@
                 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 */; };
@@ -2084 +2086 @@
                 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>"; };
@@ -5025 +5029 @@
                                 0F7B365F197C525C00ED1DDC /* DFGPhantomCanonicalizationPhase.cpp */,
                                 0F7B3660197C525C00ED1DDC /* DFGPhantomCanonicalizationPhase.h */,
+                                0F6237951AE45CA700D402EA /* DFGPhantomInsertionPhase.cpp */,
+                                0F6237961AE45CA700D402EA /* DFGPhantomInsertionPhase.h */,
                                 0FBFDD02196C92BF007A5BFA /* DFGPhantomRemovalPhase.cpp */,
                                 0FBFDD03196C92BF007A5BFA /* DFGPhantomRemovalPhase.h */,
@@ -6221 +6227 @@
                                 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 */,
@@ -7474 +7481 @@
                                 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 */,

trunk/Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp

@@ -238 +238 @@
     FastBitVector out;
     
-    result.m_map.clear();
+    result.m_map.resize(m_codeBlock->instructions().size());
     
     for (unsigned i = m_basicBlocks.size(); i--;) {
@@ -250 +250 @@
             unsigned bytecodeOffset = block->bytecodeOffsets()[i];
             stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, out);
-            result.m_map.add(bytecodeOffset, out);
+            result.m_map[bytecodeOffset] = out;
         }
     }

trunk/Source/JavaScriptCore/bytecode/FullBytecodeLiveness.h

@@ -39 +39 @@
     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];
     }
     
@@ -52 +50 @@
     friend class BytecodeLivenessAnalysis;
     
-    BytecodeToBitmapMap m_map;
+    Vector<FastBitVector, 0, UnsafeVectorOverflow> m_map;
 };
 

trunk/Source/JavaScriptCore/bytecode/VirtualRegister.h

@@ -83 +83 @@
         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)
     {

trunk/Source/JavaScriptCore/dfg/DFGForAllKills.h

@@ -52 +52 @@
     
     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;
-            });
-    }
-}
-
-template<typename Functor>
-void forAllKilledOperands(Graph& graph, CodeOrigin before, Node* nodeAfter, const Functor& functor)
-{
+    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, 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) {
@@ -83 +96 @@
         // 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;
-        }
     }
     
@@ -107 +106 @@
     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);
-    }
+        });
 }
     
@@ -141 +160 @@
         });
 
-    CodeOrigin before;
+    Node* before = nullptr;
     if (nodeIndex)
-        before = block->at(nodeIndex - 1)->origin.forExit;
+        before = block->at(nodeIndex - 1);
 
     forAllKilledOperands(

trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp

@@ -945 +945 @@
         // 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())
@@ -955 +953 @@
     
     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;
 }
 

trunk/Source/JavaScriptCore/dfg/DFGGraph.h

@@ -30 +30 @@
 
 #include "AssemblyHelpers.h"
+#include "BytecodeLivenessAnalysisInlines.h"
 #include "CodeBlock.h"
 #include "DFGArgumentPosition.h"
@@ -42 +43 @@
 #include "DFGPrePostNumbering.h"
 #include "DFGScannable.h"
+#include "FullBytecodeLiveness.h"
 #include "JSStack.h"
 #include "MethodOfGettingAValueProfile.h"
@@ -678 +680 @@
     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*);

trunk/Source/JavaScriptCore/dfg/DFGMayExit.cpp

@@ -89 +89 @@
     case PhantomLocal:
     case CountExecution:
+    case Jump:
+    case Branch:
+    case Unreachable:
         break;
         

trunk/Source/JavaScriptCore/dfg/DFGMovHintRemovalPhase.cpp

@@ -81 +81 @@
         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)
@@ -115 +114 @@
             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

trunk/Source/JavaScriptCore/dfg/DFGNodeType.h

@@ -56 +56 @@
     /* 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) \
     \

trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp

@@ -53 +53 @@
 #include "DFGObjectAllocationSinkingPhase.h"
 #include "DFGPhantomCanonicalizationPhase.h"
+#include "DFGPhantomInsertionPhase.h"
 #include "DFGPhantomRemovalPhase.h"
 #include "DFGPredictionInjectionPhase.h"
@@ -321 +322 @@
         performCPSRethreading(dfg);
         performDCE(dfg);
+        performPhantomInsertion(dfg);
         performStackLayout(dfg);
         performVirtualRegisterAllocation(dfg);

trunk/Source/JavaScriptCore/dfg/DFGScoreBoard.h

@@ -56 +56 @@
     }
     
+    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
     }
 

trunk/Source/JavaScriptCore/dfg/DFGVirtualRegisterAllocationPhase.cpp

@@ -56 +56 @@
             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);

trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp

@@ -7200 +7200 @@
         
         AvailabilityMap availabilityMap = this->availabilityMap();
-        
-        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();
-        }
+        availabilityMap.m_locals.fill(Availability());
+        
+        m_graph.forAllLiveInBytecode(
+            codeOrigin,
+            [&] (VirtualRegister reg) {
+                availabilityMap.m_locals.operand(reg) =
+                    this->availabilityMap().m_locals.operand(reg);
+            });
         
         availabilityMap.prune();