Changeset 181467 in webkit


Ignore:
Timestamp:
Mar 12, 2015, 6:57:59 PM (10 years ago)
Author:
fpizlo@apple.com
Message:

Bytecode liveness analysis should have more lambdas and fewer sets
​https://bugs.webkit.org/show_bug.cgi?id=142647

Reviewed by Mark Lam.

Source/JavaScriptCore:

In bug 141174 I'll need to identify all of the bytecode kill sites. This requires hooking into
the bytecode analysis' stepOverFunction method, except in such a way that we observe uses that
are not in outs. This refactors stepOverFunction so that you can pass it use/def functors that
can either be used to propagate outs (as we do right now) or to additionally detect kills or
whatever else.

In order to achieve this, the liveness analysis was moved off of maintaining uses/defs
bitvectors. This wasn't helping the abstraction and was probably inefficient. The new code
should be a bit faster since we don't have to clear uses/defs bitvectors on each instruction. On
the other hand, being able to intercept each use means that our code for exception handlers is
no longer a bitwise-merge; it requires finding set bits. Fortunately, this code only kicks in
for instructions inside a try, and its performance is O(live at catch), so that's probably not
bad.

  • bytecode/BytecodeLivenessAnalysis.cpp:

(JSC::indexForOperand):
(JSC::stepOverInstruction):
(JSC::computeLocalLivenessForBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::computeFullLiveness):
(JSC::setForOperand): Deleted.

  • bytecode/BytecodeUseDef.h:

(JSC::computeUsesForBytecodeOffset):
(JSC::computeDefsForBytecodeOffset):

  • bytecode/CodeBlock.cpp:

Source/WTF:

Add a method for iterating each set bit in a FastBitVector. Uses a functor as a callback since
this allows for a more efficient algorithm.

  • wtf/FastBitVector.h:

(WTF::FastBitVector::forEachSetBit):

Location:
trunk/Source
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r181466 r181467  
     12015-03-12  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Bytecode liveness analysis should have more lambdas and fewer sets
     4        https://bugs.webkit.org/show_bug.cgi?id=142647
     5
     6        Reviewed by Mark Lam.
     7       
     8        In bug 141174 I'll need to identify all of the bytecode kill sites. This requires hooking into
     9        the bytecode analysis' stepOverFunction method, except in such a way that we observe uses that
     10        are not in outs. This refactors stepOverFunction so that you can pass it use/def functors that
     11        can either be used to propagate outs (as we do right now) or to additionally detect kills or
     12        whatever else.
     13       
     14        In order to achieve this, the liveness analysis was moved off of maintaining uses/defs
     15        bitvectors. This wasn't helping the abstraction and was probably inefficient. The new code
     16        should be a bit faster since we don't have to clear uses/defs bitvectors on each instruction. On
     17        the other hand, being able to intercept each use means that our code for exception handlers is
     18        no longer a bitwise-merge; it requires finding set bits. Fortunately, this code only kicks in
     19        for instructions inside a try, and its performance is O(live at catch), so that's probably not
     20        bad.
     21
     22        * bytecode/BytecodeLivenessAnalysis.cpp:
     23        (JSC::indexForOperand):
     24        (JSC::stepOverInstruction):
     25        (JSC::computeLocalLivenessForBytecodeOffset):
     26        (JSC::BytecodeLivenessAnalysis::computeFullLiveness):
     27        (JSC::setForOperand): Deleted.
     28        * bytecode/BytecodeUseDef.h:
     29        (JSC::computeUsesForBytecodeOffset):
     30        (JSC::computeDefsForBytecodeOffset):
     31        * bytecode/CodeBlock.cpp:
     32
    1332015-03-12  Ryosuke Niwa  <rniwa@webkit.org>
    234

  • trunk/Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp

    r159943 r181467  
    11/*
    2  * Copyright (C) 2013 Apple Inc. All rights reserved.
     2 * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    5959}
    6060
    61 static void setForOperand(CodeBlock* codeBlock, FastBitVector& bits, int operand)
     61static unsigned indexForOperand(CodeBlock* codeBlock, int operand)
    6262{
    6363    ASSERT(isValidRegisterForLiveness(codeBlock, operand));
    6464    VirtualRegister virtualReg(operand);
    6565    if (virtualReg.offset() > codeBlock->captureStart())
    66         bits.set(virtualReg.toLocal());
    67     else
    68         bits.set(virtualReg.toLocal() - codeBlock->captureCount());
    69 }
    70 
    71 namespace {
    72 
    73 class SetBit {
    74 public:
    75     SetBit(FastBitVector& bits)
    76         : m_bits(bits)
    77     {
    78     }
    79    
    80     void operator()(CodeBlock* codeBlock, Instruction*, OpcodeID, int operand)
    81     {
    82         if (isValidRegisterForLiveness(codeBlock, operand))
    83             setForOperand(codeBlock, m_bits, operand);
    84     }
    85    
    86 private:
    87     FastBitVector& m_bits;
    88 };
    89 
    90 } // anonymous namespace
     66        return virtualReg.toLocal();
     67    return virtualReg.toLocal() - codeBlock->captureCount();
     68}
    9169
    9270static unsigned getLeaderOffsetForBasicBlock(RefPtr<BytecodeBasicBlock>* basicBlock)
    … …  
    134112}
    135113
    136 static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& uses, FastBitVector& defs, FastBitVector& out)
    137 {
    138     uses.clearAll();
    139     defs.clearAll();
    140    
    141     SetBit setUses(uses);
    142     SetBit setDefs(defs);
    143     computeUsesForBytecodeOffset(codeBlock, bytecodeOffset, setUses);
    144     computeDefsForBytecodeOffset(codeBlock, bytecodeOffset, setDefs);
    145    
    146     out.exclude(defs);
    147     out.merge(uses);
    148    
     114// Simplified interface to bytecode use/def, which determines defs first and then uses, and includes
     115// exception handlers in the uses.
     116template<typename UseFunctor, typename DefFunctor>
     117static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, const UseFunctor& use, const DefFunctor& def)
     118{
     119    // This abstractly execute the instruction in reverse. Instructions logically first use operands and
     120    // then define operands. This logical ordering is necessary for operations that use and def the same
     121    // operand, like:
     122    //
     123    //     op_add loc1, loc1, loc2
     124    //
     125    // The use of loc1 happens before the def of loc1. That's a semantic requirement since the add
     126    // operation cannot travel forward in time to read the value that it will produce after reading that
     127    // value. Since we are executing in reverse, this means that we must do defs before uses (reverse of
     128    // uses before defs).
     129    //
     130    // Since this is a liveness analysis, this ordering ends up being particularly important: if we did
     131    // uses before defs, then the add operation above would appear to not have loc1 live, since we'd
     132    // first add it to the out set (the use), and then we'd remove it (the def).
     133   
     134    computeDefsForBytecodeOffset(
     135        codeBlock, bytecodeOffset,
     136        [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
     137            if (isValidRegisterForLiveness(codeBlock, operand))
     138                def(indexForOperand(codeBlock, operand));
     139        });
     140   
     141    computeUsesForBytecodeOffset(
     142        codeBlock, bytecodeOffset,
     143        [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
     144            if (isValidRegisterForLiveness(codeBlock, operand))
     145                use(indexForOperand(codeBlock, operand));
     146        });
     147       
    149148    // If we have an exception handler, we want the live-in variables of the
    150149    // exception handler block to be included in the live-in of this particular bytecode.
    … …  
    152151        BytecodeBasicBlock* handlerBlock = findBasicBlockWithLeaderOffset(basicBlocks, handler->target);
    153152        ASSERT(handlerBlock);
    154         out.merge(handlerBlock->in());
    155     }
     153        handlerBlock->in().forEachSetBit(use);
     154    }
     155}
     156
     157static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& out)
     158{
     159    stepOverInstruction(
     160        codeBlock, basicBlocks, bytecodeOffset,
     161        [&] (unsigned bitIndex) {
     162            // This is the use functor, so we set the bit.
     163            out.set(bitIndex);
     164        },
     165        [&] (unsigned bitIndex) {
     166            // This is the def functor, so we clear the bit.
     167            out.clear(bitIndex);
     168        });
    156169}
    157170
    … …  
    162175
    163176    FastBitVector out = block->out();
    164 
    165     FastBitVector uses;
    166     FastBitVector defs;
    167     uses.resize(out.numBits());
    168     defs.resize(out.numBits());
    169177
    170178    for (int i = block->bytecodeOffsets().size() - 1; i >= 0; i--) {
    … …  
    173181            break;
    174182       
    175         stepOverInstruction(codeBlock, basicBlocks, bytecodeOffset, uses, defs, out);
     183        stepOverInstruction(codeBlock, basicBlocks, bytecodeOffset, out);
    176184    }
    177185
    … …  
    278286{
    279287    FastBitVector out;
    280     FastBitVector uses;
    281     FastBitVector defs;
    282288   
    283289    result.m_codeBlock = m_codeBlock;
    … …  
    290296       
    291297        out = block->out();
    292         uses.resize(out.numBits());
    293         defs.resize(out.numBits());
    294298       
    295299        for (unsigned i = block->bytecodeOffsets().size(); i--;) {
    296300            unsigned bytecodeOffset = block->bytecodeOffsets()[i];
    297             stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, uses, defs, out);
     301            stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, out);
    298302            result.m_map.add(bytecodeOffset, out);
    299303        }

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

    r181466 r181467  
    11/*
    2  * Copyright (C) 2013 Apple Inc. All rights reserved.
     2 * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3333template<typename Functor>
    3434void computeUsesForBytecodeOffset(
    35     CodeBlock* codeBlock, unsigned bytecodeOffset, Functor& functor)
     35    CodeBlock* codeBlock, unsigned bytecodeOffset, const Functor& functor)
    3636{
    3737    Interpreter* interpreter = codeBlock->vm()->interpreter;
    … …  
    236236
    237237template<typename Functor>
    238 void computeDefsForBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, Functor& functor)
     238void computeDefsForBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, const Functor& functor)
    239239{
    240240    Interpreter* interpreter = codeBlock->vm()->interpreter;

  • trunk/Source/JavaScriptCore/bytecode/CodeBlock.cpp

    r181466 r181467  
    38823882
    38833883struct VerifyCapturedDef {
    3884     void operator()(CodeBlock* codeBlock, Instruction* instruction, OpcodeID opcodeID, int operand)
     3884    void operator()(CodeBlock* codeBlock, Instruction* instruction, OpcodeID opcodeID, int operand) const
    38853885    {
    38863886        unsigned bytecodeOffset = instruction - codeBlock->instructions().begin();

  • trunk/Source/WTF/ChangeLog

    r181462 r181467  
     12015-03-12  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Bytecode liveness analysis should have more lambdas and fewer sets
     4        https://bugs.webkit.org/show_bug.cgi?id=142647
     5
     6        Reviewed by Mark Lam.
     7       
     8        Add a method for iterating each set bit in a FastBitVector. Uses a functor as a callback since
     9        this allows for a more efficient algorithm.
     10
     11        * wtf/FastBitVector.h:
     12        (WTF::FastBitVector::forEachSetBit):
     13
    1142015-03-12  Michael Saboff  <msaboff@apple.com>
    215

  • trunk/Source/WTF/wtf/FastBitVector.h

    r159825 r181467  
    178178    }
    179179   
     180    template<typename Functor>
     181    void forEachSetBit(const Functor& functor)
     182    {
     183        unsigned n = arrayLength();
     184        for (unsigned i = 0; i < n; ++i) {
     185            uint32_t word = m_array[i];
     186            unsigned j = i << 5;
     187            while (word) {
     188                if (word & 1)
     189                    functor(j);
     190                word >>= 1;
     191                j++;
     192            }
     193        }
     194    }
     195   
    180196    WTF_EXPORT_PRIVATE void dump(PrintStream&) const;
    181197   
Note: See TracChangeset for help on using the changeset viewer.