Ignore:
Timestamp:
Aug 25, 2016, 3:55:10 PM (9 years ago)
Author:
Yusuke Suzuki
Message:

[DFG][FTL] Implement ES6 Generators in DFG / FTL
​https://bugs.webkit.org/show_bug.cgi?id=152723

Reviewed by Filip Pizlo.

JSTests:

  • stress/generator-fib-ftl-and-array.js: Added.

(fib):

  • stress/generator-fib-ftl-and-object.js: Added.

(fib):

  • stress/generator-fib-ftl-and-string.js: Added.

(fib):

  • stress/generator-fib-ftl.js: Added.

(fib):

  • stress/generator-frame-empty.js: Added.

(shouldThrow):
(shouldThrow.fib):

  • stress/generator-reduced-save-point-put-to-scope.js: Added.

(shouldBe):
(gen):

  • stress/generator-transfer-register-beyond-mutiple-yields.js: Added.

(shouldBe):
(gen):

Source/JavaScriptCore:

This patch introduces DFG and FTL support for ES6 generators.
ES6 generator is compiled by the BytecodeGenerator. But at the last phase, BytecodeGenerator performs "generatorification" onto the unlinked code.
In BytecodeGenerator phase, we just emit op_yield for each yield point. And we don't emit any generator related switch, save, and resume sequences
here. Those are emitted by the generatorification phase.

So the graph is super simple! Before the generatorification, the graph looks like this.

op_enter -> ...... -> op_yield -> ..... -> op_yield -> ...

Roughly speaking, in the generatorification phase, we turn out which variables should be saved and resumed at each op_yield.
This is done by liveness analysis. After that, we convert op_yield to the sequence of "op_put_to_scope", "op_ret", and "op_get_from_scope".
op_put_to_scope and op_get_from_scope sequences are corresponding to the save and resume sequences. We set up the scope for the generator frame and
perform op_put_to_scope and op_get_from_scope onto it. The live registers are saved and resumed over the generator's next() calls by using this
special generator frame scope. And we also set up the global switch for the generator.

In the generatorification phase,

  1. We construct the BytecodeGraph from the unlinked instructions. This constructs the basic blocks, and it is used in the subsequent analysis.
  2. We perform the analysis onto the unlinked code. We extract the live variables at each op_yield.
  3. We insert the get_from_scope and put_to_scope at each op_yield. Which registers should be saved and resumed is offered by (2). Then, clip the op_yield themselves. And we also insert the switch_imm. The jump targets of this switch are just after this op_switch_imm and each op_yield point.

One interesting point is the try-range. We split the try-range at the op_yield point in BytecodeGenerator phase.
This drops the hacky thing that is introduced in [1].
If the try-range covers the resume sequences, the exception handler's use-registers are incorrectly transferred to the entry block.
For example,

handler uses r2

try-range

label:(entry block can jump here)

r1 = get_from_scope # resume sequence starts | use r2 is transferred to the entry block!
r2 = get_from_scope |
starts usual sequences |
... |

Handler's r2 use should be considered at the r1 = get_from_scope point.
Previously, we handle this edge case by treating op_resume specially in the liveness analysis[1].
To drop this workaround, we split the try-range not to cover this resume sequence.

handler uses r2

try-range

label:(entry block can jump here)

r1 = get_from_scope # resume sequence starts
r2 = get_from_scope
starts usual sequences try-range should start from here.
... |

OK. Let's show the detailed example.

  1. First, there is the normal bytecode sequence. Here, | represents the offsets, and [] represents the bytecodes.

bytecodes | [ ] | [ ] | [ ] | [ ] | [ ] | [ ] |
try-range <----------------------------------->

  1. When we emit the op_yield in the bytecode generator, we carefully split the try-range.

bytecodes | [ ] | [ ] | [op_yield] | [ ] | [ ] | [ ] |
try-range <-----------> <----------------->

  1. And in the generatorification phase, we insert the switch's jump target and save & resume sequences. And we also drop op_yield.

Insert save seq Insert resume seq
before op_yield. after op_yield's point.

v v

bytecodes | [ ] | [ ] | [op_yield] | [ ] | [ ] | [ ] |
try-range <-----------> <----------------->

|

Jump to here. Drop this op_yield.

  1. The final layout is the following.

bytecodes | [ ] | [ ][save seq][op_ret] | [resume seq] | [ ] | [ ] | [ ] |
try-range <-----------------------------> <---------------->


Jump to here.

The rewriting done by the BytecodeRewriter is executed in a batch manner. Since these modification changes the basic blocks and size of unlinked instructions,
BytecodeRewriter also performs the offset adjustment for UnlinkedCodeBlock. So, this rewriting is performed onto the BytecodeGraph rather than BytecodeBasicBlock.
The reason why we take this design is simple: we don't want to newly create the basic blocks and opcodes for this early phase like DFG. Instead, we perform the
modification and adjustment to the unlinked instructions and UnlinkedCodeBlock in a in-place manner.

Bytecode rewriting functionality is offered by BytecodeRewriter. BytecodeRewriter allows us to insert any bytecodes to any places
in a in-place manner. BytecodeRewriter handles the original bytecode offsets as labels. And you can insert bytecodes before and after
these labels. You can also insert any jumps to any places. When you insert jumps, you need to specify jump target with this labels.
These labels (original bytecode offsets) are automatically converted to the appropriate offsets by BytecodeRewriter.

After that phase, the data flow of the generator-saved-and-resumed-registers are explicitly represented by the get_from_scope and put_to_scope.
And the switch is inserted to represent the actual control flow for the generator. And op_yield is removed. Since we use the existing bytecodes (op_switch_imm, op_put_to_scope
op_ret, and op_get_from_scope), DFG and FTL changes are not necessary. This patch also drops data structures and implementations for the old generator,
op_resume, op_save implementations and GeneratorFrame.

Note that this patch does not leverage the recent multi entrypoints support in B3. After this patch is introduced, we will submit a new patch that leverages the multi
entrypoints for generator's resume and sees the performance gain.

Microbenchmarks related to generators show up to 2.9x improvements.

Baseline Patched

generator-fib 102.0116+-3.2880 34.9670+-0.2221 definitely 2.9174x faster
generator-sunspider-access-nsieve 5.8596+-0.0371 4.9051+-0.0720 definitely 1.1946x faster
generator-with-several-types 332.1478+-4.2425 124.6642+-2.4826 definitely 2.6643x faster

<geometric> 58.2998+-0.7758 27.7425+-0.2577 definitely 2.1015x faster

In ES6SampleBench's Basic, we can observe 41% improvement (Macbook Pro).

Baseline:

Geometric Mean Result: 133.55 ms +- 4.49 ms

Benchmark First Iteration Worst 2% Steady State
Air 54.03 ms +- 7.51 ms 29.06 ms +- 3.13 ms 2276.59 ms +- 61.17 ms
Basic 30.18 ms +- 1.86 ms 18.85 ms +- 0.45 ms 2851.16 ms +- 41.87 ms

Patched:

Geometric Mean Result: 121.78 ms +- 3.96 ms

Benchmark First Iteration Worst 2% Steady State
Air 52.09 ms +- 6.89 ms 29.59 ms +- 3.16 ms 2239.90 ms +- 54.60 ms
Basic 29.28 ms +- 1.46 ms 16.26 ms +- 0.66 ms 2025.15 ms +- 38.56 ms

[1]: ​https://bugs.webkit.org/show_bug.cgi?id=159281

  • CMakeLists.txt:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • builtins/GeneratorPrototype.js:

(globalPrivate.generatorResume):

  • bytecode/BytecodeBasicBlock.cpp:

(JSC::BytecodeBasicBlock::shrinkToFit):
(JSC::BytecodeBasicBlock::computeImpl):
(JSC::BytecodeBasicBlock::compute):
(JSC::isBranch): Deleted.
(JSC::isUnconditionalBranch): Deleted.
(JSC::isTerminal): Deleted.
(JSC::isThrow): Deleted.
(JSC::linkBlocks): Deleted.
(JSC::computeBytecodeBasicBlocks): Deleted.

  • bytecode/BytecodeBasicBlock.h:

(JSC::BytecodeBasicBlock::isEntryBlock):
(JSC::BytecodeBasicBlock::isExitBlock):
(JSC::BytecodeBasicBlock::leaderOffset):
(JSC::BytecodeBasicBlock::totalLength):
(JSC::BytecodeBasicBlock::offsets):
(JSC::BytecodeBasicBlock::successors):
(JSC::BytecodeBasicBlock::index):
(JSC::BytecodeBasicBlock::addSuccessor):
(JSC::BytecodeBasicBlock::BytecodeBasicBlock):
(JSC::BytecodeBasicBlock::addLength):
(JSC::BytecodeBasicBlock::leaderBytecodeOffset): Deleted.
(JSC::BytecodeBasicBlock::totalBytecodeLength): Deleted.
(JSC::BytecodeBasicBlock::bytecodeOffsets): Deleted.
(JSC::BytecodeBasicBlock::addBytecodeLength): Deleted.

  • bytecode/BytecodeGeneratorification.cpp: Added.

(JSC::BytecodeGeneratorification::BytecodeGeneratorification):
(JSC::BytecodeGeneratorification::graph):
(JSC::BytecodeGeneratorification::yields):
(JSC::BytecodeGeneratorification::enterPoint):
(JSC::BytecodeGeneratorification::storageForGeneratorLocal):
(JSC::GeneratorLivenessAnalysis::GeneratorLivenessAnalysis):
(JSC::GeneratorLivenessAnalysis::computeDefsForBytecodeOffset):
(JSC::GeneratorLivenessAnalysis::computeUsesForBytecodeOffset):
(JSC::GeneratorLivenessAnalysis::run):
(JSC::BytecodeGeneratorification::run):
(JSC::performGeneratorification):

  • bytecode/BytecodeGeneratorification.h: Copied from Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysisInlines.h.
  • bytecode/BytecodeGraph.h: Added.

(JSC::BytecodeGraph::codeBlock):
(JSC::BytecodeGraph::instructions):
(JSC::BytecodeGraph::basicBlocksInReverseOrder):
(JSC::BytecodeGraph::blockContainsBytecodeOffset):
(JSC::BytecodeGraph::findBasicBlockForBytecodeOffset):
(JSC::BytecodeGraph::findBasicBlockWithLeaderOffset):
(JSC::BytecodeGraph::size):
(JSC::BytecodeGraph::at):
(JSC::BytecodeGraph::operator[]):
(JSC::BytecodeGraph::begin):
(JSC::BytecodeGraph::end):
(JSC::BytecodeGraph::first):
(JSC::BytecodeGraph::last):
(JSC::BytecodeGraph<Block>::BytecodeGraph):

  • bytecode/BytecodeList.json:
  • bytecode/BytecodeLivenessAnalysis.cpp:

(JSC::BytecodeLivenessAnalysis::BytecodeLivenessAnalysis):
(JSC::BytecodeLivenessAnalysis::computeDefsForBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::computeUsesForBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::computeFullLiveness):
(JSC::BytecodeLivenessAnalysis::computeKills):
(JSC::BytecodeLivenessAnalysis::dumpResults):
(JSC::BytecodeLivenessAnalysis::compute):
(JSC::isValidRegisterForLiveness): Deleted.
(JSC::getLeaderOffsetForBasicBlock): Deleted.
(JSC::findBasicBlockWithLeaderOffset): Deleted.
(JSC::blockContainsBytecodeOffset): Deleted.
(JSC::findBasicBlockForBytecodeOffset): Deleted.
(JSC::stepOverInstruction): Deleted.
(JSC::computeLocalLivenessForBytecodeOffset): Deleted.
(JSC::computeLocalLivenessForBlock): Deleted.
(JSC::BytecodeLivenessAnalysis::runLivenessFixpoint): Deleted.

  • bytecode/BytecodeLivenessAnalysis.h:
  • bytecode/BytecodeLivenessAnalysisInlines.h:

(JSC::isValidRegisterForLiveness):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::computeLocalLivenessForBytecodeOffset):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::computeLocalLivenessForBlock):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::getLivenessInfoAtBytecodeOffset):
(JSC::BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint):

  • bytecode/BytecodeRewriter.cpp: Added.

(JSC::BytecodeRewriter::applyModification):
(JSC::BytecodeRewriter::execute):
(JSC::BytecodeRewriter::adjustJumpTargetsInFragment):
(JSC::BytecodeRewriter::insertImpl):
(JSC::BytecodeRewriter::adjustJumpTarget):

  • bytecode/BytecodeRewriter.h: Added.

(JSC::BytecodeRewriter::InsertionPoint::InsertionPoint):
(JSC::BytecodeRewriter::InsertionPoint::operator<):
(JSC::BytecodeRewriter::InsertionPoint::operator==):
(JSC::BytecodeRewriter::Insertion::length):
(JSC::BytecodeRewriter::Fragment::Fragment):
(JSC::BytecodeRewriter::Fragment::appendInstruction):
(JSC::BytecodeRewriter::BytecodeRewriter):
(JSC::BytecodeRewriter::insertFragmentBefore):
(JSC::BytecodeRewriter::insertFragmentAfter):
(JSC::BytecodeRewriter::removeBytecode):
(JSC::BytecodeRewriter::graph):
(JSC::BytecodeRewriter::adjustAbsoluteOffset):
(JSC::BytecodeRewriter::adjustJumpTarget):
(JSC::BytecodeRewriter::calculateDifference):

  • bytecode/BytecodeUseDef.h:

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

  • bytecode/CodeBlock.cpp:

(JSC::CodeBlock::dumpBytecode):
(JSC::CodeBlock::finishCreation):
(JSC::CodeBlock::handlerForIndex):
(JSC::CodeBlock::shrinkToFit):
(JSC::CodeBlock::valueProfileForBytecodeOffset):
(JSC::CodeBlock::livenessAnalysisSlow):

  • bytecode/CodeBlock.h:

(JSC::CodeBlock::isConstantRegisterIndex):
(JSC::CodeBlock::livenessAnalysis):
(JSC::CodeBlock::liveCalleeLocalsAtYield): Deleted.

  • bytecode/HandlerInfo.h:

(JSC::HandlerInfoBase::handlerForIndex):

  • bytecode/Opcode.h:

(JSC::isBranch):
(JSC::isUnconditionalBranch):
(JSC::isTerminal):
(JSC::isThrow):

  • bytecode/PreciseJumpTargets.cpp:

(JSC::getJumpTargetsForBytecodeOffset):
(JSC::computePreciseJumpTargetsInternal):
(JSC::computePreciseJumpTargets):
(JSC::recomputePreciseJumpTargets):
(JSC::findJumpTargetsForBytecodeOffset):

  • bytecode/PreciseJumpTargets.h:
  • bytecode/PreciseJumpTargetsInlines.h: Added.

(JSC::extractStoredJumpTargetsForBytecodeOffset):

  • bytecode/UnlinkedCodeBlock.cpp:

(JSC::UnlinkedCodeBlock::handlerForBytecodeOffset):
(JSC::UnlinkedCodeBlock::handlerForIndex):
(JSC::UnlinkedCodeBlock::applyModification):

  • bytecode/UnlinkedCodeBlock.h:

(JSC::UnlinkedStringJumpTable::offsetForValue):
(JSC::UnlinkedCodeBlock::numCalleeLocals):

  • bytecode/VirtualRegister.h:
  • bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::generate):
(JSC::BytecodeGenerator::BytecodeGenerator):
(JSC::BytecodeGenerator::emitComplexPopScopes):
(JSC::prepareJumpTableForStringSwitch):
(JSC::BytecodeGenerator::emitYieldPoint):
(JSC::BytecodeGenerator::emitSave): Deleted.
(JSC::BytecodeGenerator::emitResume): Deleted.
(JSC::BytecodeGenerator::emitGeneratorStateLabel): Deleted.
(JSC::BytecodeGenerator::beginGenerator): Deleted.
(JSC::BytecodeGenerator::endGenerator): Deleted.

  • bytecompiler/BytecodeGenerator.h:

(JSC::BytecodeGenerator::generatorStateRegister):
(JSC::BytecodeGenerator::generatorValueRegister):
(JSC::BytecodeGenerator::generatorResumeModeRegister):
(JSC::BytecodeGenerator::generatorFrameRegister):

  • bytecompiler/NodesCodegen.cpp:

(JSC::FunctionNode::emitBytecode):

  • dfg/DFGOperations.cpp:
  • interpreter/Interpreter.cpp:

(JSC::findExceptionHandler):
(JSC::GetCatchHandlerFunctor::operator()):
(JSC::UnwindFunctor::operator()):

  • interpreter/Interpreter.h:
  • interpreter/InterpreterInlines.h: Copied from Source/JavaScriptCore/bytecode/PreciseJumpTargets.h.

(JSC::Interpreter::getOpcodeID):

  • jit/JIT.cpp:

(JSC::JIT::privateCompileMainPass):

  • jit/JIT.h:
  • jit/JITOpcodes.cpp:

(JSC::JIT::emit_op_save): Deleted.
(JSC::JIT::emit_op_resume): Deleted.

  • llint/LowLevelInterpreter.asm:
  • parser/Parser.cpp:

(JSC::Parser<LexerType>::parseInner):
(JSC::Parser<LexerType>::parseGeneratorFunctionSourceElements):
(JSC::Parser<LexerType>::createGeneratorParameters):

  • parser/Parser.h:
  • runtime/CommonSlowPaths.cpp:

(JSC::SLOW_PATH_DECL): Deleted.

  • runtime/CommonSlowPaths.h:
  • runtime/GeneratorFrame.cpp: Removed.

(JSC::GeneratorFrame::GeneratorFrame): Deleted.
(JSC::GeneratorFrame::finishCreation): Deleted.
(JSC::GeneratorFrame::createStructure): Deleted.
(JSC::GeneratorFrame::create): Deleted.
(JSC::GeneratorFrame::save): Deleted.
(JSC::GeneratorFrame::resume): Deleted.
(JSC::GeneratorFrame::visitChildren): Deleted.

  • runtime/GeneratorFrame.h: Removed.

(JSC::GeneratorFrame::locals): Deleted.
(JSC::GeneratorFrame::localAt): Deleted.
(JSC::GeneratorFrame::offsetOfLocals): Deleted.
(JSC::GeneratorFrame::allocationSizeForLocals): Deleted.

  • runtime/JSGeneratorFunction.h:
  • runtime/VM.cpp:

(JSC::VM::VM):

  • runtime/VM.h:

Source/WTF:

  • wtf/FastBitVector.h:

(WTF::FastBitVector::FastBitVector):

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r204912 r204994  
    3232#include "CodeBlock.h"
    3333#include "FullBytecodeLiveness.h"
    34 #include "PreciseJumpTargets.h"
     34#include "InterpreterInlines.h"
    3535
    3636namespace JSC {
    3737
    3838BytecodeLivenessAnalysis::BytecodeLivenessAnalysis(CodeBlock* codeBlock)
    39     : m_codeBlock(codeBlock)
     39    : m_graph(codeBlock, codeBlock->instructions())
    4040{
    41     ASSERT(m_codeBlock);
    4241    compute();
    4342}
    4443
    45 static bool isValidRegisterForLiveness(CodeBlock* codeBlock, int operand)
     44template<typename Functor>
     45void BytecodeLivenessAnalysis::computeDefsForBytecodeOffset(CodeBlock* codeBlock, OpcodeID opcodeID, Instruction* instruction, FastBitVector&, const Functor& functor)
    4646{
    47     if (codeBlock->isConstantRegisterIndex(operand))
    48         return false;
    49    
    50     VirtualRegister virtualReg(operand);
    51     return virtualReg.isLocal();
     47    JSC::computeDefsForBytecodeOffset(codeBlock, opcodeID, instruction, functor);
    5248}
    5349
    54 static unsigned getLeaderOffsetForBasicBlock(std::unique_ptr<BytecodeBasicBlock>* basicBlock)
     50template<typename Functor>
     51void BytecodeLivenessAnalysis::computeUsesForBytecodeOffset(CodeBlock* codeBlock, OpcodeID opcodeID, Instruction* instruction, FastBitVector&, const Functor& functor)
    5552{
    56     return (*basicBlock)->leaderBytecodeOffset();
    57 }
    58 
    59 static BytecodeBasicBlock* findBasicBlockWithLeaderOffset(Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned leaderOffset)
    60 {
    61     return (*tryBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(basicBlocks, basicBlocks.size(), leaderOffset, getLeaderOffsetForBasicBlock)).get();
    62 }
    63 
    64 static bool blockContainsBytecodeOffset(BytecodeBasicBlock* block, unsigned bytecodeOffset)
    65 {
    66     unsigned leaderOffset = block->leaderBytecodeOffset();
    67     return bytecodeOffset >= leaderOffset && bytecodeOffset < leaderOffset + block->totalBytecodeLength();
    68 }
    69 
    70 static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset)
    71 {
    72 /*
    73     for (unsigned i = 0; i < basicBlocks.size(); i++) {
    74         if (blockContainsBytecodeOffset(basicBlocks[i].get(), bytecodeOffset))
    75             return basicBlocks[i].get();
    76     }
    77     return 0;
    78 */
    79     std::unique_ptr<BytecodeBasicBlock>* basicBlock = approximateBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(
    80         basicBlocks, basicBlocks.size(), bytecodeOffset, getLeaderOffsetForBasicBlock);
    81     // We found the block we were looking for.
    82     if (blockContainsBytecodeOffset((*basicBlock).get(), bytecodeOffset))
    83         return (*basicBlock).get();
    84 
    85     // Basic block is to the left of the returned block.
    86     if (bytecodeOffset < (*basicBlock)->leaderBytecodeOffset()) {
    87         ASSERT(basicBlock - 1 >= basicBlocks.data());
    88         ASSERT(blockContainsBytecodeOffset(basicBlock[-1].get(), bytecodeOffset));
    89         return basicBlock[-1].get();
    90     }
    91 
    92     // Basic block is to the right of the returned block.
    93     ASSERT(&basicBlock[1] <= &basicBlocks.last());
    94     ASSERT(blockContainsBytecodeOffset(basicBlock[1].get(), bytecodeOffset));
    95     return basicBlock[1].get();
    96 }
    97 
    98 // Simplified interface to bytecode use/def, which determines defs first and then uses, and includes
    99 // exception handlers in the uses.
    100 template<typename UseFunctor, typename DefFunctor>
    101 static void stepOverInstruction(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, const UseFunctor& use, const DefFunctor& def)
    102 {
    103     // This abstractly execute the instruction in reverse. Instructions logically first use operands and
    104     // then define operands. This logical ordering is necessary for operations that use and def the same
    105     // operand, like:
    106     //
    107     //     op_add loc1, loc1, loc2
    108     //
    109     // The use of loc1 happens before the def of loc1. That's a semantic requirement since the add
    110     // operation cannot travel forward in time to read the value that it will produce after reading that
    111     // value. Since we are executing in reverse, this means that we must do defs before uses (reverse of
    112     // uses before defs).
    113     //
    114     // Since this is a liveness analysis, this ordering ends up being particularly important: if we did
    115     // uses before defs, then the add operation above would appear to not have loc1 live, since we'd
    116     // first add it to the out set (the use), and then we'd remove it (the def).
    117    
    118     computeDefsForBytecodeOffset(
    119         codeBlock, block, bytecodeOffset,
    120         [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
    121             if (isValidRegisterForLiveness(codeBlock, operand))
    122                 def(VirtualRegister(operand).toLocal());
    123         });
    124 
    125     computeUsesForBytecodeOffset(
    126         codeBlock, block, bytecodeOffset,
    127         [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
    128             if (isValidRegisterForLiveness(codeBlock, operand))
    129                 use(VirtualRegister(operand).toLocal());
    130         });
    131 
    132     // If we have an exception handler, we want the live-in variables of the
    133     // exception handler block to be included in the live-in of this particular bytecode.
    134     if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset)) {
    135         // FIXME: This resume check should not be needed.
    136         // https://bugs.webkit.org/show_bug.cgi?id=159281
    137         Interpreter* interpreter = codeBlock->vm()->interpreter;
    138         Instruction* instructionsBegin = codeBlock->instructions().begin();
    139         Instruction* instruction = &instructionsBegin[bytecodeOffset];
    140         OpcodeID opcodeID = interpreter->getOpcodeID(instruction->u.opcode);
    141         if (opcodeID != op_resume) {
    142             BytecodeBasicBlock* handlerBlock = findBasicBlockWithLeaderOffset(basicBlocks, handler->target);
    143             ASSERT(handlerBlock);
    144             handlerBlock->in().forEachSetBit(use);
    145         }
    146     }
    147 }
    148 
    149 static void stepOverInstruction(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& out)
    150 {
    151     stepOverInstruction(
    152         codeBlock, block, basicBlocks, bytecodeOffset,
    153         [&] (unsigned bitIndex) {
    154             // This is the use functor, so we set the bit.
    155             out.set(bitIndex);
    156         },
    157         [&] (unsigned bitIndex) {
    158             // This is the def functor, so we clear the bit.
    159             out.clear(bitIndex);
    160         });
    161 }
    162 
    163 static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned targetOffset, FastBitVector& result)
    164 {
    165     ASSERT(!block->isExitBlock());
    166     ASSERT(!block->isEntryBlock());
    167 
    168     FastBitVector out = block->out();
    169 
    170     for (int i = block->bytecodeOffsets().size() - 1; i >= 0; i--) {
    171         unsigned bytecodeOffset = block->bytecodeOffsets()[i];
    172         if (targetOffset > bytecodeOffset)
    173             break;
    174        
    175         stepOverInstruction(codeBlock, block, basicBlocks, bytecodeOffset, out);
    176     }
    177 
    178     result.set(out);
    179 }
    180 
    181 static void computeLocalLivenessForBlock(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks)
    182 {
    183     if (block->isExitBlock() || block->isEntryBlock())
    184         return;
    185     computeLocalLivenessForBytecodeOffset(codeBlock, block, basicBlocks, block->leaderBytecodeOffset(), block->in());
    186 }
    187 
    188 void BytecodeLivenessAnalysis::runLivenessFixpoint()
    189 {
    190     UnlinkedCodeBlock* unlinkedCodeBlock = m_codeBlock->unlinkedCodeBlock();
    191     unsigned numberOfVariables = unlinkedCodeBlock->m_numCalleeLocals;
    192 
    193     for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
    194         BytecodeBasicBlock* block = m_basicBlocks[i].get();
    195         block->in().resize(numberOfVariables);
    196         block->out().resize(numberOfVariables);
    197     }
    198 
    199     bool changed;
    200     m_basicBlocks.last()->in().clearAll();
    201     m_basicBlocks.last()->out().clearAll();
    202     FastBitVector newOut;
    203     newOut.resize(m_basicBlocks.last()->out().numBits());
    204     do {
    205         changed = false;
    206         for (unsigned i = m_basicBlocks.size() - 1; i--;) {
    207             BytecodeBasicBlock* block = m_basicBlocks[i].get();
    208             newOut.clearAll();
    209             for (unsigned j = 0; j < block->successors().size(); j++)
    210                 newOut.merge(block->successors()[j]->in());
    211             bool outDidChange = block->out().setAndCheck(newOut);
    212             computeLocalLivenessForBlock(m_codeBlock, block, m_basicBlocks);
    213             changed |= outDidChange;
    214         }
    215     } while (changed);
     53    JSC::computeUsesForBytecodeOffset(codeBlock, opcodeID, instruction, functor);
    21654}
    21755
    21856void BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(unsigned bytecodeOffset, FastBitVector& result)
    21957{
    220     BytecodeBasicBlock* block = findBasicBlockForBytecodeOffset(m_basicBlocks, bytecodeOffset);
     58    BytecodeBasicBlock* block = m_graph.findBasicBlockForBytecodeOffset(bytecodeOffset);
    22159    ASSERT(block);
    22260    ASSERT(!block->isEntryBlock());
    22361    ASSERT(!block->isExitBlock());
    22462    result.resize(block->out().numBits());
    225     computeLocalLivenessForBytecodeOffset(m_codeBlock, block, m_basicBlocks, bytecodeOffset, result);
     63    computeLocalLivenessForBytecodeOffset(m_graph, block, bytecodeOffset, result);
    22664}
    22765
    … …  
    24583{
    24684    FastBitVector out;
     85    CodeBlock* codeBlock = m_graph.codeBlock();
    24786   
    248     result.m_map.resize(m_codeBlock->instructions().size());
     87    result.m_map.resize(codeBlock->instructions().size());
    24988   
    250     for (unsigned i = m_basicBlocks.size(); i--;) {
    251         BytecodeBasicBlock* block = m_basicBlocks[i].get();
     89    for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
    25290        if (block->isEntryBlock() || block->isExitBlock())
    25391            continue;
    … …  
    25593        out = block->out();
    25694       
    257         for (unsigned i = block->bytecodeOffsets().size(); i--;) {
    258             unsigned bytecodeOffset = block->bytecodeOffsets()[i];
    259             stepOverInstruction(m_codeBlock, block, m_basicBlocks, bytecodeOffset, out);
     95        for (unsigned i = block->offsets().size(); i--;) {
     96            unsigned bytecodeOffset = block->offsets()[i];
     97            stepOverInstruction(m_graph, bytecodeOffset, out);
    26098            result.m_map[bytecodeOffset] = out;
    26199        }
    … …  
    267105    FastBitVector out;
    268106   
    269     result.m_codeBlock = m_codeBlock;
    270     result.m_killSets = std::make_unique<BytecodeKills::KillSet[]>(m_codeBlock->instructions().size());
     107    CodeBlock* codeBlock = m_graph.codeBlock();
     108    result.m_codeBlock = codeBlock;
     109    result.m_killSets = std::make_unique<BytecodeKills::KillSet[]>(codeBlock->instructions().size());
    271110   
    272     for (unsigned i = m_basicBlocks.size(); i--;) {
    273         BytecodeBasicBlock* block = m_basicBlocks[i].get();
     111    for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
    274112        if (block->isEntryBlock() || block->isExitBlock())
    275113            continue;
    … …  
    277115        out = block->out();
    278116       
    279         for (unsigned i = block->bytecodeOffsets().size(); i--;) {
    280             unsigned bytecodeOffset = block->bytecodeOffsets()[i];
     117        for (unsigned i = block->offsets().size(); i--;) {
     118            unsigned bytecodeOffset = block->offsets()[i];
    281119            stepOverInstruction(
    282                 m_codeBlock, block, m_basicBlocks, bytecodeOffset,
     120                m_graph, bytecodeOffset, out,
    283121                [&] (unsigned index) {
    284122                    // This is for uses.
    … …  
    298136void BytecodeLivenessAnalysis::dumpResults()
    299137{
    300     dataLog("\nDumping bytecode liveness for ", *m_codeBlock, ":\n");
    301     Interpreter* interpreter = m_codeBlock->vm()->interpreter;
    302     Instruction* instructionsBegin = m_codeBlock->instructions().begin();
    303     for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
    304         BytecodeBasicBlock* block = m_basicBlocks[i].get();
    305         dataLogF("\nBytecode basic block %u: %p (offset: %u, length: %u)\n", i, block, block->leaderBytecodeOffset(), block->totalBytecodeLength());
     138    CodeBlock* codeBlock = m_graph.codeBlock();
     139    dataLog("\nDumping bytecode liveness for ", *codeBlock, ":\n");
     140    Interpreter* interpreter = codeBlock->vm()->interpreter;
     141    Instruction* instructionsBegin = codeBlock->instructions().begin();
     142    unsigned i = 0;
     143    for (BytecodeBasicBlock* block : m_graph) {
     144        dataLogF("\nBytecode basic block %u: %p (offset: %u, length: %u)\n", i++, block, block->leaderOffset(), block->totalLength());
    306145        dataLogF("Successors: ");
    307146        for (unsigned j = 0; j < block->successors().size(); j++) {
    … …  
    318157            continue;
    319158        }
    320         for (unsigned bytecodeOffset = block->leaderBytecodeOffset(); bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength();) {
     159        for (unsigned bytecodeOffset = block->leaderOffset(); bytecodeOffset < block->leaderOffset() + block->totalLength();) {
    321160            const Instruction* currentInstruction = &instructionsBegin[bytecodeOffset];
    322161
    … …  
    328167            }
    329168            dataLogF("\n");
    330             m_codeBlock->dumpBytecode(WTF::dataFile(), m_codeBlock->globalObject()->globalExec(), instructionsBegin, currentInstruction);
     169            codeBlock->dumpBytecode(WTF::dataFile(), codeBlock->globalObject()->globalExec(), instructionsBegin, currentInstruction);
    331170
    332171            OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);
    … …  
    347186void BytecodeLivenessAnalysis::compute()
    348187{
    349     computeBytecodeBasicBlocks(m_codeBlock, m_basicBlocks);
    350     ASSERT(m_basicBlocks.size());
    351     runLivenessFixpoint();
     188    runLivenessFixpoint(m_graph);
    352189
    353190    if (Options::dumpBytecodeLivenessResults())
Note: See TracChangeset for help on using the changeset viewer.