⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 286030 in webkit


Ignore:
Timestamp:
Nov 18, 2021, 2:56:56 PM (5 years ago)
Author:
rmorisset@apple.com
Message:

DFGByteCodeParser.cpp should avoid resizing the Operands<> of every BasicBlock on every inlining
​https://bugs.webkit.org/show_bug.cgi?id=228053

Reviewed by Saam Barati.

The dfg bytecode parser only makes use of block->variablesAtTail.
But currently it updates the size of variablesAtHead, valuesAtHead, valuesAtTail and intersectionOfPastValuesAtHead every single time it changes the number of Tmps and/or Locals.
This happens notably whenever it inlines a function.

It is not nearly as cheap as it looks, as each resizing may reallocate a Vector, requires filling the new slots with zeros, and requires moving the existing values (which are all 0) to the new Vector.
This was obvious when looking at profiling of JS2: bzero + memmove are the two hottest C++ functions, and the manipulation of Operands is partly responsible.

This patch fixes this by only resizing block->variablesAtTail during the execution of the bytecode parser, and initializing all of the other operands at the very end of it.
It also merges the adjustment of numLocals and of numTmps for variablesAtTail during inlining, to avoid accidentally moving data twice.

On JetStream2 on an M1 MBP, it changes the total time spent in the DFGByteCodeParser from 1240-1260ms to 1155-1170ms.

  • bytecode/Operands.h:

(JSC::Operands::ensureLocalsAndTmps):

  • dfg/DFGBasicBlock.cpp:
  • dfg/DFGBasicBlock.h:
  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::ensureLocalsForVariablesAtTail):
(JSC::DFG::ByteCodeParser::ensureLocalsAndTmpsForVariablesAtTail):
(JSC::DFG::ByteCodeParser::allocateBlock):
(JSC::DFG::ByteCodeParser::allocateTargetableBlock):
(JSC::DFG::ByteCodeParser::allocateUntargetableBlock):
(JSC::DFG::ByteCodeParser::inlineCall):
(JSC::DFG::ByteCodeParser::handleVarargsInlining):
(JSC::DFG::ByteCodeParser::handleGetById):
(JSC::DFG::ByteCodeParser::handlePutById):
(JSC::DFG::ByteCodeParser::parse):

Location:
trunk/Source/JavaScriptCore
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r286020 r286030  
     12021-11-18  Robin Morisset  <rmorisset@apple.com>
     2
     3        DFGByteCodeParser.cpp should avoid resizing the Operands<> of every BasicBlock on every inlining
     4        https://bugs.webkit.org/show_bug.cgi?id=228053
     5
     6        Reviewed by Saam Barati.
     7
     8        The dfg bytecode parser only makes use of block->variablesAtTail.
     9        But currently it updates the size of variablesAtHead, valuesAtHead, valuesAtTail and intersectionOfPastValuesAtHead every single time it changes the number of Tmps and/or Locals.
     10        This happens notably whenever it inlines a function.
     11
     12        It is not nearly as cheap as it looks, as each resizing may reallocate a Vector, requires filling the new slots with zeros, and requires moving the existing values (which are all 0) to the new Vector.
     13        This was obvious when looking at profiling of JS2: bzero + memmove are the two hottest C++ functions, and the manipulation of Operands is partly responsible.
     14
     15        This patch fixes this by only resizing block->variablesAtTail during the execution of the bytecode parser, and initializing all of the other operands at the very end of it.
     16        It also merges the adjustment of numLocals and of numTmps for variablesAtTail during inlining, to avoid accidentally moving data twice.
     17
     18        On JetStream2 on an M1 MBP, it changes the total time spent in the DFGByteCodeParser from 1240-1260ms to 1155-1170ms.
     19
     20        * bytecode/Operands.h:
     21        (JSC::Operands::ensureLocalsAndTmps):
     22        * dfg/DFGBasicBlock.cpp:
     23        * dfg/DFGBasicBlock.h:
     24        * dfg/DFGByteCodeParser.cpp:
     25        (JSC::DFG::ByteCodeParser::ensureLocalsForVariablesAtTail):
     26        (JSC::DFG::ByteCodeParser::ensureLocalsAndTmpsForVariablesAtTail):
     27        (JSC::DFG::ByteCodeParser::allocateBlock):
     28        (JSC::DFG::ByteCodeParser::allocateTargetableBlock):
     29        (JSC::DFG::ByteCodeParser::allocateUntargetableBlock):
     30        (JSC::DFG::ByteCodeParser::inlineCall):
     31        (JSC::DFG::ByteCodeParser::handleVarargsInlining):
     32        (JSC::DFG::ByteCodeParser::handleGetById):
     33        (JSC::DFG::ByteCodeParser::handlePutById):
     34        (JSC::DFG::ByteCodeParser::parse):
     35
    1362021-11-18  Yusuke Suzuki  <ysuzuki@apple.com>
    237

  • trunk/Source/JavaScriptCore/bytecode/Operands.h

    r283623 r286030  
    275275    }
    276276
    277     void ensureTmps(size_t size, const T& ensuredValue = T())
    278     {
    279         if (size <= numberOfTmps())
    280             return;
     277    void ensureLocalsAndTmps(size_t newNumLocals, size_t newNumTmps, const T& ensuredValue = T())
     278    {
     279        ASSERT(newNumLocals >= numberOfLocals());
     280        ASSERT(newNumTmps >= numberOfTmps());
     281
     282        size_t oldNumLocals = numberOfLocals();
     283        size_t oldNumTmps = numberOfTmps();
    281284
    282285        size_t oldSize = m_values.size();
    283         size_t newSize = numberOfArguments() + numberOfLocals() + size;
     286        size_t newSize = numberOfArguments() + newNumLocals + newNumTmps;
    284287        m_values.grow(newSize);
    285288
     289        for (size_t i = 0; i < oldNumTmps; ++i)
     290            m_values[newSize - 1 - i] = m_values[tmpIndex(oldNumTmps - 1 - i)];
     291
     292        m_numLocals = newNumLocals;
    286293        if (ensuredValue != T() || !WTF::VectorTraits<T>::needsInitialization) {
     294            for (size_t i = 0; i < newNumLocals - oldNumLocals; ++i)
     295                m_values[localIndex(oldNumLocals + i)] = ensuredValue;
    287296            for (size_t i = oldSize; i < newSize; ++i)
    288297                m_values[i] = ensuredValue;

  • trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.cpp

    r266242 r286030  
    6262BasicBlock::~BasicBlock()
    6363{
    64 }
    65 
    66 void BasicBlock::ensureLocals(unsigned newNumLocals)
    67 {
    68     variablesAtHead.ensureLocals(newNumLocals);
    69     variablesAtTail.ensureLocals(newNumLocals);
    70     valuesAtHead.ensureLocals(newNumLocals);
    71     valuesAtTail.ensureLocals(newNumLocals);
    72     intersectionOfPastValuesAtHead.ensureLocals(newNumLocals, AbstractValue::fullTop());
    73 }
    74 
    75 void BasicBlock::ensureTmps(unsigned newNumTmps)
    76 {
    77     variablesAtHead.ensureTmps(newNumTmps);
    78     variablesAtTail.ensureTmps(newNumTmps);
    79     valuesAtHead.ensureTmps(newNumTmps);
    80     valuesAtTail.ensureTmps(newNumTmps);
    81     intersectionOfPastValuesAtHead.ensureTmps(newNumTmps, AbstractValue::fullTop());
    8264}
    8365

  • trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h

    r266242 r286030  
    5454    ~BasicBlock();
    5555   
    56     void ensureLocals(unsigned newNumLocals);
    57     void ensureTmps(unsigned newNumTmps);
    58    
    5956    size_t size() const { return m_nodes.size(); }
    6057    bool isEmpty() const { return !size(); }

  • trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp

    r285525 r286030  
    139139    void parseCodeBlock();
    140140   
    141     void ensureLocals(unsigned newNumLocals)
     141    void ensureLocalsForVariablesAtTail(unsigned newNumLocals)
    142142    {
    143143        VERBOSE_LOG("   ensureLocals: trying to raise m_numLocals from ", m_numLocals, " to ", newNumLocals, "\n");
    … …  
    146146        m_numLocals = newNumLocals;
    147147        for (size_t i = 0; i < m_graph.numBlocks(); ++i)
    148             m_graph.block(i)->ensureLocals(newNumLocals);
    149     }
    150 
    151     void ensureTmps(unsigned newNumTmps)
     148            m_graph.block(i)->variablesAtTail.ensureLocals(newNumLocals);
     149    }
     150
     151    void ensureLocalsAndTmpsForVariablesAtTail(unsigned newNumLocals, unsigned newNumTmps)
    152152    {
    153         VERBOSE_LOG("   ensureTmps: trying to raise m_numTmps from ", m_numTmps, " to ", newNumTmps, "\n");
    154         if (newNumTmps <= m_numTmps)
     153        VERBOSE_LOG("   ensureLocalsAndTmps: trying to raise m_numLocals/m_numTmps from ", m_numLocals, "/", m_numTmps, " to ", newNumLocals, "/", newNumTmps, "\n");
     154        if (newNumLocals <= m_numLocals && newNumTmps <= m_numTmps)
    155155            return;
    156         m_numTmps = newNumTmps;
     156        m_numLocals = std::max(m_numLocals, newNumLocals);
     157        m_numTmps = std::max(m_numTmps, newNumTmps);
    157158        for (size_t i = 0; i < m_graph.numBlocks(); ++i)
    158             m_graph.block(i)->ensureTmps(newNumTmps);
     159            m_graph.block(i)->variablesAtTail.ensureLocalsAndTmps(m_numLocals, m_numTmps);
    159160    }
    160161
    … …  
    172173    BasicBlock* allocateTargetableBlock(BytecodeIndex);
    173174    BasicBlock* allocateUntargetableBlock();
     175    // Helper for allocateTargetableBlock and allocateUntargetableBlock, do not use directly
     176    BasicBlock* allocateBlock(BytecodeIndex);
    174177    // An untargetable block can be given a bytecodeIndex to be later managed by linkBlock, but only once, and it can never go in the other direction
    175178    void makeBlockTargetable(BasicBlock*, BytecodeIndex);
    … …  
    12631266};
    12641267
     1268BasicBlock* ByteCodeParser::allocateBlock(BytecodeIndex bytecodeIndex)
     1269{
     1270    // We don't bother initializing most Operands here, since inlining can change the number of locals and tmps.
     1271    // We only initialize variablesAtTail because it is the only part which is used in the bytecode parser
     1272    // We will initialize all of the other Operands in bulk at the end of the phase.
     1273    Ref<BasicBlock> block = adoptRef(*new BasicBlock(bytecodeIndex, 0, 0, 0, 1));
     1274    BasicBlock* blockPtr = block.ptr();
     1275    blockPtr->variablesAtTail = Operands<Node*>(m_numArguments, m_numLocals, m_numTmps);
     1276    m_graph.appendBlock(WTFMove(block));
     1277    return blockPtr;
     1278}
     1279
    12651280BasicBlock* ByteCodeParser::allocateTargetableBlock(BytecodeIndex bytecodeIndex)
    12661281{
    12671282    ASSERT(bytecodeIndex);
    1268     Ref<BasicBlock> block = adoptRef(*new BasicBlock(bytecodeIndex, m_numArguments, m_numLocals, m_numTmps, 1));
    1269     BasicBlock* blockPtr = block.ptr();
    12701283    // m_blockLinkingTargets must always be sorted in increasing order of bytecodeBegin
    12711284    if (m_inlineStackTop->m_blockLinkingTargets.size())
    12721285        ASSERT(m_inlineStackTop->m_blockLinkingTargets.last()->bytecodeBegin.offset() < bytecodeIndex.offset());
     1286    BasicBlock* blockPtr = allocateBlock(bytecodeIndex);
    12731287    m_inlineStackTop->m_blockLinkingTargets.append(blockPtr);
    1274     m_graph.appendBlock(WTFMove(block));
    12751288    return blockPtr;
    12761289}
    … …  
    12781291BasicBlock* ByteCodeParser::allocateUntargetableBlock()
    12791292{
    1280     Ref<BasicBlock> block = adoptRef(*new BasicBlock(BytecodeIndex(), m_numArguments, m_numLocals, m_numTmps, 1));
    1281     BasicBlock* blockPtr = block.ptr();
    1282     m_graph.appendBlock(WTFMove(block));
     1293    BasicBlock* blockPtr = allocateBlock(BytecodeIndex());
    12831294    VERBOSE_LOG("Adding new untargetable block: ", blockPtr->index, "\n");
    12841295    return blockPtr;
    … …  
    16781689    Operand inlineCallFrameStart = VirtualRegister(m_inlineStackTop->remapOperand(VirtualRegister(registerOffsetAfterFixup)).value() + CallFrame::headerSizeInRegisters);
    16791690   
    1680     ensureLocals(
    1681         inlineCallFrameStart.toLocal() + 1 +
    1682         CallFrame::headerSizeInRegisters + codeBlock->numCalleeLocals());
    1683    
    1684     ensureTmps((m_inlineStackTop->m_inlineCallFrame ? m_inlineStackTop->m_inlineCallFrame->tmpOffset : 0) + m_inlineStackTop->m_codeBlock->numTmps() + codeBlock->numTmps());
     1691    unsigned numLocals = inlineCallFrameStart.toLocal() + 1 + CallFrame::headerSizeInRegisters + codeBlock->numCalleeLocals();
     1692    unsigned numTmps = (m_inlineStackTop->m_inlineCallFrame ? m_inlineStackTop->m_inlineCallFrame->tmpOffset : 0) + m_inlineStackTop->m_codeBlock->numTmps() + codeBlock->numTmps();
     1693    ensureLocalsAndTmpsForVariablesAtTail(numLocals, numTmps);
    16851694
    16861695    size_t argumentPositionStart = m_graph.m_argumentPositions.size();
    … …  
    19952004        m_inlineStackTop->remapOperand(VirtualRegister(registerOffset)).virtualRegister().offset();
    19962005       
    1997         ensureLocals(VirtualRegister(remappedRegisterOffset).toLocal());
     2006        ensureLocalsForVariablesAtTail(VirtualRegister(remappedRegisterOffset).toLocal());
    19982007       
    19992008        int argumentStart = registerOffset + CallFrame::headerSizeInRegisters;
    … …  
    47924801        -registerOffset);
    47934802   
    4794     ensureLocals(
     4803    ensureLocalsForVariablesAtTail(
    47954804        m_inlineStackTop->remapOperand(
    47964805            VirtualRegister(registerOffset)).toLocal());
    … …  
    51865195            -registerOffset);
    51875196   
    5188         ensureLocals(
     5197        ensureLocalsForVariablesAtTail(
    51895198            m_inlineStackTop->remapOperand(
    51905199                VirtualRegister(registerOffset)).toLocal());
    … …  
    90419050    linkBlocks(inlineStackEntry.m_unlinkedBlocks, inlineStackEntry.m_blockLinkingTargets);
    90429051
     9052    for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
     9053        // We kept block->variablesAtTail updated throughout, but not the other Operands, to avoid having to resize them every time we inline
     9054        ASSERT(block->variablesAtTail.numberOfArguments() == m_numArguments);
     9055        ASSERT(block->variablesAtTail.numberOfLocals() == m_numLocals);
     9056        ASSERT(block->variablesAtTail.numberOfTmps() == m_numTmps);
     9057        block->variablesAtHead = Operands<Node*>(OperandsLike, block->variablesAtTail);
     9058        block->valuesAtHead = Operands<AbstractValue>(OperandsLike, block->variablesAtTail);
     9059        block->valuesAtTail = Operands<AbstractValue>(OperandsLike, block->variablesAtTail);
     9060        block->intersectionOfPastValuesAtHead = Operands<AbstractValue>(OperandsLike, block->variablesAtTail);
     9061    }
     9062
    90439063    // We run backwards propagation now because the soundness of that phase
    90449064    // relies on seeing the graph as if it were an IR over bytecode, since
    … …  
    91579177    m_graph.killUnreachableBlocks();
    91589178
    9159     for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
    9160         BasicBlock* block = m_graph.block(blockIndex);
    9161         if (!block)
    9162             continue;
    9163         ASSERT(block->variablesAtHead.numberOfLocals() == m_graph.block(0)->variablesAtHead.numberOfLocals());
    9164         ASSERT(block->variablesAtHead.numberOfArguments() == m_graph.block(0)->variablesAtHead.numberOfArguments());
    9165         ASSERT(block->variablesAtTail.numberOfLocals() == m_graph.block(0)->variablesAtHead.numberOfLocals());
    9166         ASSERT(block->variablesAtTail.numberOfArguments() == m_graph.block(0)->variablesAtHead.numberOfArguments());
    9167     }
    9168 
    91699179    m_graph.m_tmps = m_numTmps;
    91709180    m_graph.m_localVars = m_numLocals;
Note: See TracChangeset for help on using the changeset viewer.