Attachment 340103 Details for Bug 185452 – the patch

[patch] the patch

blah.patch (text/plain), 16.71 KB, created by Filip Pizlo on 2018-05-10 10:49:41 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2018-05-10 10:49:41 PDT

Size: 16.71 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 231607)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,50 @@
>+2018-05-09  Filip Pizlo  <fpizlo@apple.com>
>+
>+        InPlaceAbstractState::beginBasicBlock shouldn't copy all m_variables every time
>+        https://bugs.webkit.org/show_bug.cgi?id=185452
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        We were spending a lot of time in beginBasicBlock() just copying the state of all variables
>+        from the block head to InPlaceAbstractState::m_variables. It is necessary for
>+        InPlaceAbstractState to have its own copy since we need to mutate it separately from
>+        block->valuesAtHead. But most variables are untouched by most basic blocks, so this was a lot
>+        of superfluous work.
>+        
>+        This change adds a bitvector called m_activeVariables that tracks which variables have been
>+        copied. We lazily copy the variables on first use. Variables that were never copied also have
>+        a simplified merging path, which just needs to consider if the variable got clobbered between
>+        head and tail.
>+        
>+        This is a 1.5% speed-up on SunSpider-CompileTime and a 1.7% speed-up on V8Spider-CompileTime.
>+
>+        * bytecode/Operands.h:
>+        (JSC::Operands::argumentIndex const):
>+        (JSC::Operands::localIndex const):
>+        (JSC::Operands::argument):
>+        (JSC::Operands::argument const):
>+        (JSC::Operands::local):
>+        (JSC::Operands::local const):
>+        (JSC::Operands::operandIndex const):
>+        * dfg/DFGAbstractValue.h:
>+        (JSC::DFG::AbstractValue::fastForwardFromTo):
>+        * dfg/DFGCFAPhase.cpp:
>+        (JSC::DFG::CFAPhase::performForwardCFA):
>+        * dfg/DFGInPlaceAbstractState.cpp:
>+        (JSC::DFG::InPlaceAbstractState::beginBasicBlock):
>+        (JSC::DFG::InPlaceAbstractState::variablesForDebugging):
>+        (JSC::DFG::InPlaceAbstractState::activateAllVariables):
>+        (JSC::DFG::InPlaceAbstractState::endBasicBlock):
>+        (JSC::DFG::InPlaceAbstractState::activateVariable):
>+        (JSC::DFG::InPlaceAbstractState::mergeStateAtTail): Deleted.
>+        * dfg/DFGInPlaceAbstractState.h:
>+        (JSC::DFG::InPlaceAbstractState::variableAt):
>+        (JSC::DFG::InPlaceAbstractState::operand):
>+        (JSC::DFG::InPlaceAbstractState::local):
>+        (JSC::DFG::InPlaceAbstractState::argument):
>+        (JSC::DFG::InPlaceAbstractState::activateVariableIfNecessary):
>+        (JSC::DFG::InPlaceAbstractState::variablesForDebugging): Deleted.
>+
> 2018-05-09  Filip Pizlo  <fpizlo@apple.com>
> 
>         Speed up AbstractInterpreter::executeEdges
>Index: Source/JavaScriptCore/bytecode/Operands.h
>===================================================================
>--- Source/JavaScriptCore/bytecode/Operands.h	(revision 231607)
>+++ Source/JavaScriptCore/bytecode/Operands.h	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2011, 2012, 2013, 2015, 2016 Apple Inc. All rights reserved.
>+ * Copyright (C) 2011-2018 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -71,19 +71,28 @@ public:
>     size_t numberOfArguments() const { return m_numArguments; }
>     size_t numberOfLocals() const { return m_values.size() - m_numArguments; }
>     
>-    T& argument(size_t idx)
>+    size_t argumentIndex(size_t idx) const
>     {
>         ASSERT(idx < m_numArguments);
>-        return m_values[idx];
>+        return idx;
>+    }
>+    
>+    size_t localIndex(size_t idx) const
>+    {
>+        return m_numArguments + idx;
>+    }
>+    
>+    T& argument(size_t idx)
>+    {
>+        return m_values[argumentIndex(idx)];
>     }
>     const T& argument(size_t idx) const
>     {
>-        ASSERT(idx < m_numArguments);
>-        return m_values[idx];
>+        return m_values[argumentIndex(idx)];
>     }
>     
>-    T& local(size_t idx) { return m_values[m_numArguments + idx]; }
>-    const T& local(size_t idx) const { return m_values[m_numArguments + idx]; }
>+    T& local(size_t idx) { return m_values[localIndex(idx)]; }
>+    const T& local(size_t idx) const { return m_values[localIndex(idx)]; }
>     
>     template<OperandKind operandKind>
>     size_t sizeFor() const
>@@ -156,6 +165,18 @@ public:
>         setLocal(idx, value);
>     }
>     
>+    size_t operandIndex(int operand) const
>+    {
>+        if (operandIsArgument(operand))
>+            return argumentIndex(VirtualRegister(operand).toArgument());
>+        return localIndex(VirtualRegister(operand).toLocal());
>+    }
>+    
>+    size_t operandIndex(VirtualRegister virtualRegister) const
>+    {
>+        return operandIndex(virtualRegister.offset());
>+    }
>+    
>     T& operand(int operand)
>     {
>         if (operandIsArgument(operand))
>Index: Source/JavaScriptCore/dfg/DFGAbstractValue.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAbstractValue.h	(revision 231607)
>+++ Source/JavaScriptCore/dfg/DFGAbstractValue.h	(working copy)
>@@ -104,6 +104,22 @@ struct AbstractValue {
>         checkConsistency();
>     }
>     
>+    ALWAYS_INLINE void fastForwardFromTo(AbstractValueClobberEpoch oldEpoch, AbstractValueClobberEpoch newEpoch)
>+    {
>+        if (newEpoch == oldEpoch)
>+            return;
>+        
>+        if (!(m_type & SpecCell))
>+            return;
>+
>+        if (newEpoch.clobberEpoch() != oldEpoch.clobberEpoch())
>+            clobberStructures();
>+        if (newEpoch.structureClobberState() == StructuresAreWatched)
>+            m_structure.observeInvalidationPoint();
>+
>+        checkConsistency();
>+    }
>+    
>     ALWAYS_INLINE void fastForwardTo(AbstractValueClobberEpoch newEpoch)
>     {
>         if (newEpoch == m_effectEpoch)
>Index: Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGCFAPhase.cpp	(revision 231607)
>+++ Source/JavaScriptCore/dfg/DFGCFAPhase.cpp	(working copy)
>@@ -203,7 +203,7 @@ private:
>     {
>         ++m_count;
>         if (m_verbose)
>-            dataLogF("CFA [%u]\n", ++m_count);
>+            dataLogF("CFA [%u]\n", m_count);
>         
>         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
>             performBlockCFA(m_graph.block(blockIndex));
>Index: Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp	(revision 231607)
>+++ Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp	(working copy)
>@@ -54,31 +54,25 @@ InPlaceAbstractState::~InPlaceAbstractSt
> 
> void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
> {
>-    // This function is ~1.6-2% of execution time.
>-    
>     ASSERT(!m_block);
>     
>     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
>     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
>     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
> 
>-    m_abstractValues.resize(); // This part is ~0.1-0.4% of execution time.
>+    m_abstractValues.resize();
> 
>     AbstractValueClobberEpoch epoch = AbstractValueClobberEpoch::first(basicBlock->cfaStructureClobberStateAtHead);
>+    m_epochAtHead = epoch;
>     m_effectEpoch = epoch;
> 
>-    // This loop is 0.9-1.2% of execution time.
>-    // FIXME: Lazily populate m_variables when GetLocal/SetLocal happens. Apply the same idea to
>-    // merging. Alternatively, we could just use liveness here.
>-    // https://bugs.webkit.org/show_bug.cgi?id=185452
>-    for (size_t i = m_variables.size(); i--;) {
>-        AbstractValue& value = m_variables[i];
>-        value = basicBlock->valuesAtHead[i];
>-        value.m_effectEpoch = epoch;
>-    }
>+    m_block = basicBlock;
>+
>+    m_activeVariables.clearRange(0, std::min(m_variables.size(), m_activeVariables.size()));
>+    if (m_variables.size() > m_activeVariables.size())
>+        m_activeVariables.resize(m_variables.size());
>     
>     if (m_graph.m_form == SSA) {
>-        // This loop is 0.05-0.17% of execution time.
>         for (NodeAbstractValuePair& entry : basicBlock->ssa->valuesAtHead) {
>             if (entry.node.isStillValid()) {
>                 AbstractValue& value = m_abstractValues.at(entry.node);
>@@ -89,7 +83,6 @@ void InPlaceAbstractState::beginBasicBlo
>     }
>     basicBlock->cfaShouldRevisit = false;
>     basicBlock->cfaHasVisited = true;
>-    m_block = basicBlock;
>     m_isValid = true;
>     m_foundConstants = false;
>     m_branchDirection = InvalidBranchDirection;
>@@ -104,6 +97,18 @@ static void setLiveValues(Vector<NodeAbs
>         values.uncheckedAppend(NodeAbstractValuePair { node, AbstractValue() });
> }
> 
>+Operands<AbstractValue>& InPlaceAbstractState::variablesForDebugging()
>+{
>+    activateAllVariables();
>+    return m_variables;
>+}
>+
>+void InPlaceAbstractState::activateAllVariables()
>+{
>+    for (size_t i = m_variables.size(); i--;)
>+        activateVariableIfNecessary(i);
>+}
>+
> void InPlaceAbstractState::initialize()
> {
>     for (BasicBlock* entrypoint : m_graph.m_roots) {
>@@ -206,25 +211,67 @@ bool InPlaceAbstractState::endBasicBlock
>         return false;
>     }
> 
>-    block->cfaStructureClobberStateAtTail = m_structureClobberState;
>+    AbstractValueClobberEpoch epochAtHead = m_epochAtHead;
>+    AbstractValueClobberEpoch currentEpoch = m_effectEpoch;
> 
>+    block->cfaStructureClobberStateAtTail = m_structureClobberState;
>+    
>     switch (m_graph.m_form) {
>     case ThreadedCPS: {
>-        for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
>-            AbstractValue& destination = block->valuesAtTail.argument(argument);
>-            mergeStateAtTail(destination, this->argument(argument), block->variablesAtTail.argument(argument));
>-        }
>-
>-        for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
>-            AbstractValue& destination = block->valuesAtTail.local(local);
>-            mergeStateAtTail(destination, this->local(local), block->variablesAtTail.local(local));
>+        ASSERT(block->variablesAtTail.size() == block->valuesAtTail.size());
>+        ASSERT(block->variablesAtTail.size() == m_variables.size());
>+        for (size_t index = m_variables.size(); index--;) {
>+            Node* node = block->variablesAtTail[index];
>+            if (!node)
>+                continue;
>+            AbstractValue& destination = block->valuesAtTail[index];
>+            
>+            if (!m_activeVariables[index]) {
>+                destination = block->valuesAtHead[index];
>+                destination.fastForwardFromTo(epochAtHead, currentEpoch);
>+                continue;
>+            }
>+            
>+            switch (node->op()) {
>+            case Phi:
>+            case SetArgument:
>+            case PhantomLocal:
>+            case Flush:
>+                // The block transfers the value from head to tail.
>+                destination = variableAt(index);
>+                break;
>+                
>+            case GetLocal:
>+                // The block refines the value with additional speculations.
>+                destination = forNode(node);
>+                break;
>+                
>+            case SetLocal:
>+                // The block sets the variable, and potentially refines it, both
>+                // before and after setting it.
>+                destination = forNode(node->child1());
>+                break;
>+                
>+            default:
>+                RELEASE_ASSERT_NOT_REACHED();
>+                break;
>+            }
>         }
>         break;
>     }
> 
>     case SSA: {
>-        for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
>+        for (size_t i = 0; i < block->valuesAtTail.size(); ++i) {
>+            AbstractValue& destination = block->valuesAtTail[i];
>+
>+            if (!m_activeVariables[i]) {
>+                destination = block->valuesAtHead[i];
>+                destination.fastForwardFromTo(epochAtHead, currentEpoch);
>+                continue;
>+            }
>+            
>             block->valuesAtTail[i] = variableAt(i);
>+        }
> 
>         for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail)
>             valueAtTail.value = forNode(valueAtTail.node);
>@@ -248,40 +295,12 @@ void InPlaceAbstractState::reset()
>     m_structureClobberState = StructuresAreWatched;
> }
> 
>-void InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
>+void InPlaceAbstractState::activateVariable(size_t variableIndex)
> {
>-    if (!node)
>-        return;
>-
>-    const AbstractValue* source = nullptr;
>-    
>-    switch (node->op()) {
>-    case Phi:
>-    case SetArgument:
>-    case PhantomLocal:
>-    case Flush:
>-        // The block transfers the value from head to tail.
>-        source = &inVariable;
>-        break;
>-            
>-    case GetLocal:
>-        // The block refines the value with additional speculations.
>-        source = &forNode(node);
>-        break;
>-            
>-    case SetLocal:
>-        // The block sets the variable, and potentially refines it, both
>-        // before and after setting it.
>-        source = &forNode(node->child1());
>-        if (node->variableAccessData()->flushFormat() == FlushedDouble)
>-            RELEASE_ASSERT(!(source->m_type & ~SpecFullDouble));
>-        break;
>-        
>-    default:
>-        RELEASE_ASSERT_NOT_REACHED();
>-        break;
>-    }
>-    destination = *source;
>+    AbstractValue& value = m_variables[variableIndex];
>+    value = m_block->valuesAtHead[variableIndex];
>+    value.m_effectEpoch = m_epochAtHead;
>+    m_activeVariables[variableIndex] = true;
> }
> 
> bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
>Index: Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h	(revision 231607)
>+++ Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h	(working copy)
>@@ -156,15 +156,33 @@ public:
>         makeHeapTopForNode(edge.node());
>     }
>     
>-    Operands<AbstractValue>& variablesForDebugging() { return m_variables; }
>+    Operands<AbstractValue>& variablesForDebugging();
> 
>     unsigned numberOfArguments() const { return m_variables.numberOfArguments(); }
>     unsigned numberOfLocals() const { return m_variables.numberOfLocals(); }
>-    AbstractValue& operand(int operand) { return fastForward(m_variables.operand(operand)); }
>-    AbstractValue& operand(VirtualRegister operand) { return fastForward(m_variables.operand(operand)); }
>-    AbstractValue& local(size_t index) { return fastForward(m_variables.local(index)); }
>-    AbstractValue& argument(size_t index) { return fastForward(m_variables.argument(index)); }
>-    AbstractValue& variableAt(size_t index) { return fastForward(m_variables[index]); }
>+    
>+    AbstractValue& variableAt(size_t index)
>+    {
>+        activateVariableIfNecessary(index);
>+        return fastForward(m_variables[index]);
>+    }
>+
>+    AbstractValue& operand(int operand)
>+    {
>+        return variableAt(m_variables.operandIndex(operand));
>+    }
>+    
>+    AbstractValue& operand(VirtualRegister operand) { return this->operand(operand.offset()); }
>+    
>+    AbstractValue& local(size_t index)
>+    {
>+        return variableAt(m_variables.localIndex(index));
>+    }
>+    
>+    AbstractValue& argument(size_t index)
>+    {
>+        return variableAt(m_variables.argumentIndex(index));
>+    }
>     
>     // Call this before beginning CFA to initialize the abstract values of
>     // arguments, and to indicate which blocks should be listed for CFA
>@@ -247,14 +265,22 @@ public:
>     }
> 
> private:
>-    void mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
>-
>+    ALWAYS_INLINE void activateVariableIfNecessary(size_t variableIndex)
>+    {
>+        if (!m_activeVariables[variableIndex])
>+            activateVariable(variableIndex);
>+    }
>+    
>+    void activateVariable(size_t variableIndex);
>+    void activateAllVariables();
>+    
>     static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
>     
>     Graph& m_graph;
> 
>     FlowMap<AbstractValue>& m_abstractValues;
>     Operands<AbstractValue> m_variables;
>+    FastBitVector m_activeVariables;
>     BasicBlock* m_block;
>     
>     bool m_foundConstants;
>@@ -262,6 +288,7 @@ private:
>     bool m_isValid;
>     AbstractInterpreterClobberState m_clobberState;
>     StructureClobberState m_structureClobberState;
>+    AbstractValueClobberEpoch m_epochAtHead;
>     AbstractValueClobberEpoch m_effectEpoch;
>     
>     BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).

Flags:

msaboff: review+
ews-watchlist: commit-queue-

Actions: View | Formatted Diff | Diff

Attachments on bug 185452: 340009 | 340048 | 340050 | 340061 | 340103 | 340121