Bug 137785 – JavaScript Control Flow Profiler

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Saam Barati]

JavaScriptCore should know which basic blocks have executed. If it knows this information, it allows the web inspector to ask it such questions and create a UI around this feature.
This also works really nicely with type profiling because it disambiguates missing type annotations for basic blocks that haven't executed.

[Saam Barati]

I'm currently emitting op_profile_control_flow when emitting a conditional jump (for the else branch), a label, and op_enter. This allows me to only change code in BytecodeGenerator (and not in NodesCodegen).

In CodeBlock during linking time, every time I see a op_profile_control_flow, I do a forward search for the next op_profile_control_flow (or op_end), and take the expression range between those two opcodes to get a range for the basic block.

It looks like this approach works well for emitting these opcodes at basic block boundaries in the bytecode, but the expression ranges for these different bytecode offsets is pretty crappy and inaccurate for the precision I need.

I'm probably going to have to take another approach in emitting this opcode or create another map for expression ranges for basic blocks.

[Saam Barati]

Created attachment 240451 [details]
work in progress

[Saam Barati]

Comment on attachment 240451 [details]
work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=240451&action=review

This patch only covers some nodes in the AST, but shows the general gist of what is going on. 
This patch just prints the ranges for basic blocks (the ones that are implemented) during CodeBlock linking time.

This raises a bigger question on how this patch should be implemented, though. 

One possible implementation is to target this code just in BytecodeGenerator and emit op_profile_control_flow after every label, jump, and at the beginning of CodeBlocks. But, implementing it in this way, and relying on CodeBlock's expressionRangeForBytecodeOffset gives inaccurate offsets. If I wanted to go down this route, it would probably require revamping the data structure that expressionRangeForBytecodeOffset pings to be more accurate.

Another approach, and the one shown in this patch, is to target specific AST nodes and to inline their offsets into the instruction stream. This requires more work in NodesCodeGen. 

I'm not yet sure which route to take.

> Source/JavaScriptCore/bytecode/CodeBlock.cpp:2119
> +    {

It seems like I have to walk through the instruction stream here, because doing a forward walk in the above loop doesn't work because all the instructions aren't loaded into the InstructionReader's buffer.

Is this the correct way to go about this?

> Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp:1170
> +void BytecodeGenerator::emitProfileControlFlow(int offset)

This second argument being just an int is temporary. It will probably switch into a pointer of some kind.

> Source/JavaScriptCore/parser/NodeConstructors.h:47
> +        , m_endOffset(location.endOffset)

This does not work as expected.

[Saam Barati]

Here is some output byte code for the following JS program:

var i = 10;
var j = 0;
while (i--) { 
    j++; 
    if (j == 7) { 
        j++; 
        continue; 
        j++;
    } else 
        print(20); 
}

Basic Block Range: [0:34] 
Basic Block Range: [35:63] 
Basic Block Range: [64:96] 
Basic Block Range: [97:132] 
Basic Block Range: [133:137] 
Basic Block Range: [138:35] 
Basic Block Range: [36:146] 
<global>#C709NF:[0x7f8209f0d690->0x11259fc70, %sNoneGlobal, 234]: 234 m_instructions; 1872 bytes; 1 parameter(s); 10 callee register(s); 0 variable(s)
[   0] enter             
[   1] mov               loc0, Undefined(@k0)
[   4] profile_control_flow 0
[   6] resolve_scope     loc1, i(@id0), 1<ThrowIfNotFound|GlobalVar>, 0
[  12] put_to_scope      loc1, i(@id0), Int32: 10(@k1), 65537<DoNotThrowIfNotFound|GlobalVar>, <structure>, 165718712
[  19] resolve_scope     loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, 0
[  25] put_to_scope      loc1, j(@id1), Int32: 0(@k2), 65537<DoNotThrowIfNotFound|GlobalVar>, <structure>, 165718720
[  32] resolve_scope     loc1, i(@id0), 1<ThrowIfNotFound|GlobalVar>, 0
[  38] get_from_scope    loc2, loc1, i(@id0), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718712
[  46] to_number         loc3, loc2
[  49] dec               loc2
[  51] put_to_scope      loc1, i(@id0), loc2, 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718712
[  58] jfalse            loc3, 172(->230)
[  61] loop_hint         
[  62] profile_control_flow 35
[  64] resolve_scope     loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, 0
[  70] get_from_scope    loc2, loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[  78] to_number         loc0, loc2
[  81] inc               loc2
[  83] put_to_scope      loc1, j(@id1), loc2, 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[  90] resolve_scope     loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, 0
[  96] get_from_scope    loc2, loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[ 104] eq                loc2, loc2, Int32: 7(@k3)
[ 108] jfalse            loc2, 63(->171)
[ 111] profile_control_flow 64
[ 113] resolve_scope     loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, 0
[ 119] get_from_scope    loc2, loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[ 127] to_number         loc0, loc2
[ 130] inc               loc2
[ 132] put_to_scope      loc1, j(@id1), loc2, 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[ 139] jmp               62(->201)
[ 141] profile_control_flow 97
[ 143] resolve_scope     loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, 0
[ 149] get_from_scope    loc2, loc1, j(@id1), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[ 157] to_number         loc0, loc2
[ 160] inc               loc2
[ 162] put_to_scope      loc1, j(@id1), loc2, 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718720
[ 169] jmp               30(->199)
[ 171] profile_control_flow 133
[ 173] resolve_scope     loc3, print(@id2), 0<ThrowIfNotFound|GlobalProperty>, 0
[ 179] get_from_scope    loc1, loc3, print(@id2), 0<ThrowIfNotFound|GlobalProperty>, <structure>, 138
[ 187] mov               loc2, Int32: 20(@k4)
[ 190] call              loc0, loc1, 2, 10 status(Could Take Slow Path)    Original; predicting None
[ 199] profile_control_flow 138
[ 201] resolve_scope     loc1, i(@id0), 1<ThrowIfNotFound|GlobalVar>, 0
[ 207] get_from_scope    loc2, loc1, i(@id0), 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718712
[ 215] to_number         loc3, loc2
[ 218] dec               loc2
[ 220] put_to_scope      loc1, i(@id0), loc2, 1<ThrowIfNotFound|GlobalVar>, <structure>, 165718712
[ 227] jtrue             loc3, -166(->61)
[ 230] profile_control_flow 36
[ 232] end               loc0

Identifiers:
  id0 = i
  id1 = j
  id2 = print

Constants:
   k0 = Undefined
   k1 = Int32: 10
   k2 = Int32: 0
   k3 = Int32: 7
   k4 = Int32: 20

As you can see at instruction offset 230, the end of the while loop is getting the wrong offset from the endOffset() function I've implemented. I think this most likely has to do with passing the wrong offsets into Node constructors during parsing.

[Saam Barati]

Created attachment 240776 [details]
work in progress

Here is another work in progress with a bit more coverage of different expressions/statements.
This patch also adds a new data structure that will be embedded in the instruction stream.

There are still a few problems:
- Some end offsets are still incorrect.
- Some Basic Block ranges will overlap because if one function is defined inside another, 
  the basic block range of the inner function will be subsumed by a basic block range of the
  outer function. I will probably need a way to, after code generation, analyze basic block
  ranges and modify them based on function declarations. Ideally, I'd want an op_profile_control_flow
  both before and after the inner function, but inner function definitions aren't defined inside the byte code
  stream, they exist as properties on CodeBlock. I think analyzing a code block and taking note
  of inner function declarations/expression, I can dynamically adjust basic block ranges based 
  on the inner function ranges.

[Saam Barati]

Created attachment 241219 [details]
work in progress

This patch does the following:
- Improves the given ranges for basic blocks.
- The control flow profiler now covers almost all expressions/statements inside JavaScript.
- Creates an interface that the WebInspector can use.
- Enables op_profile_control_flow in the baseline JIT.
- Makes the FunctionHasExecuted cache be on all the time (which will in the future be placed under a guard to only be enabled if the typeProfiler and the control flow profiler are both enabled).

What still needs to be done:
start/end offsets of different AST nodes still aren't perfect. It might be better to just have calls to context.setEndOffset in more functions inside the parser instead of trying to generalize it inside parseStatement/parseExpression.

[Saam Barati]

Created attachment 242063 [details]
work in progress

This is much closer to the final patch.

The code more or less has no impact on performance when the control flow profiler is disabled (I still want to run more perf tests).

There is one main thing that I still need to get sorted out about how this op code will screw up basic blocks inside the DFG and inside Bytecode Basic Block. I think this screws things up because there might be an op_profile_control_flow as the last op code in a CodeBlock (because it's emitted after op_ret), and before, I think only terminal nodes are expected as the last opcode. Need to specifically diagnose why this messes things up and how to fix it inside the DFG. (Currently, when running the tests with the control flow profiler enabled, a binary search through from: 
opcode offset => basic block
fails an assertion.

[Saam Barati]

Created attachment 242338 [details]
patch

[WebKit Commit Bot]

Attachment 242338 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2165:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/ControlFlowProfiler.h:35:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:928:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:938:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:948:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:957:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 6 in 46 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Created attachment 242340 [details]
patch

fix include order from above patch

[WebKit Commit Bot]

Attachment 242340 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2165:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:928:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:938:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:948:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:957:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 5 in 46 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Joseph Pecoraro]

Comment on attachment 242340 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=242340&action=review

> Source/JavaScriptCore/runtime/BasicBlockLocation.cpp:16
> + * 1.  Redistributions of source code must retain the above copyright
> + *     notice, this list of conditions and the following disclaimer.
> + * 2.  Redistributions in binary form must reproduce the above copyright
> + *     notice, this list of conditions and the following disclaimer in the
> + *     documentation and/or other materials provided with the distribution.
> + * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
> + *     its contributors may be used to endorse or promote products derived
> + *     from this software without specific prior written permission.

This (and all other new files) uses an outdated license, this should be a 2 clause. See Source/JavaScriptCore/API/JSValue.h for an example.

[Michael Saboff]

Comment on attachment 242340 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=242340&action=review

Getting close.  Looks like you have some build errors.  Could you also provide performance numbers with control flow profiling off?

> Source/JavaScriptCore/bytecode/CodeBlock.cpp:2180
> +        unsigned i = 0;
> +        while (i < instructionCount) {
> +            OpcodeID op = vm()->interpreter->getOpcodeID(instructions[i].u.opcode);
> +            if (op != op_profile_control_flow) {
> +                i += opcodeLength(op);
> +                continue;
> +            }
> +
> +            // Do a forward scan to find the next op_profile_control_flow. Because op_profile_control_flow 
> +            // is emitted at the beginning of every basic block, finding the next op_profile_control_flow
> +            // will give us the range of a single basic block.
> +            unsigned j = i;
> +            do {
> +                j += opcodeLength(op); 
> +                if (j >= instructionCount)
> +                    break;
> +                op = vm()->interpreter->getOpcodeID(instructions[j].u.opcode);
> +            } while (op != op_profile_control_flow);
> +            
> +            int startOffset = instructions[i + 1].u.operand;
> +            int endOffset = j >= instructionCount ? m_sourceOffset + m_ownerExecutable->source().length() - 1 : instructions[j + 1].u.operand;
> +            BasicBlockLocation* basicBlockLocation = vm()->controlFlowProfiler()->getBasicBlockLocation(m_ownerExecutable->sourceID(), startOffset, endOffset);
> +
> +            // Find all functions that are enclosed within the range: [startOffset, endOffset]
> +            // and insert these functions' start/end offsets as gaps in the current BasicBlockLocation.
> +            // This is necessary because in the original source text of a JavaScript program, 
> +            // function literals form new basic blocks boundaries, but they aren't represented 
> +            // inside the CodeBlock's instruction stream.
> +            auto insertFunctionGaps = [basicBlockLocation, startOffset, endOffset] (const WriteBarrier<FunctionExecutable>& functionExecutable) {
> +                const UnlinkedFunctionExecutable* executable = functionExecutable->unlinkedExecutable();
> +                int functionStart = executable->typeProfilingStartOffset();
> +                int functionEnd = executable->typeProfilingEndOffset();
> +                if (functionStart >= startOffset && functionEnd <= endOffset)
> +                    basicBlockLocation->insertGap(functionStart, functionEnd);
> +            };
> +
> +            for (const WriteBarrier<FunctionExecutable>& executable : m_functionDecls)
> +                insertFunctionGaps(executable);
> +            for (const WriteBarrier<FunctionExecutable>& executable : m_functionExprs)
> +                insertFunctionGaps(executable);
> +
> +            instructions[i + 1].u.basicBlockLocation = basicBlockLocation;
> +
> +            i = j;

Use more descriptive variable names instead of i & j.  Theses are more than loop indices.

[Saam Barati]

Will run benchmarks now.

(I edited a raw diff to post this patch so I think I probably messed something up during editing that's causing the builds to fail. I also need to add some stuff for windows/etc builds).

[Saam Barati]

Created attachment 242444 [details]
performance tests

[Geoffrey Garen]

Comment on attachment 242340 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=242340&action=review

> Source/JavaScriptCore/bytecode/CodeBlock.cpp:2145
> +            // Do a forward scan to find the next op_profile_control_flow. Because op_profile_control_flow 

It's kind of a bummer that we insert these opcodes and then later do a scan to find where we inserted them. Is it possible to record these boundaries as we emit code -- maybe make it the control flow nodes' jobs to record these boundaries?

[Saam Barati]

(In reply to comment #16)
> Comment on attachment 242340 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=242340&action=review
> 
> > Source/JavaScriptCore/bytecode/CodeBlock.cpp:2145
> > +            // Do a forward scan to find the next op_profile_control_flow. Because op_profile_control_flow 
> 
> It's kind of a bummer that we insert these opcodes and then later do a scan
> to find where we inserted them. Is it possible to record these boundaries as
> we emit code -- maybe make it the control flow nodes' jobs to record these
> boundaries?

I agree, this is pretty crappy.
I suppose we can store a vector of byte code offsets on the unlinked code block.
I'll give it a shot.

[Saam Barati]

Created attachment 242531 [details]
patch

Should build.

[Saam Barati]

Created attachment 242541 [details]
patch

Apparently not...
Let's give this one a go.

[WebKit Commit Bot]

Attachment 242541 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2159:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:926:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:936:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:946:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:955:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 5 in 47 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

I updated the copyright statements locally, I will include it in the next patch.

[Saam Barati]

Created attachment 242545 [details]
patch

Let's try this again...

[WebKit Commit Bot]

Attachment 242545 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2159:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:926:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:936:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:946:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:955:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 5 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Created attachment 242560 [details]
patch

Attempt to fix windows build failure.

[WebKit Commit Bot]

Attachment 242560 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2159:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:926:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:936:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:946:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:955:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 5 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Created attachment 242578 [details]
patch

try to fix windows build again

[WebKit Commit Bot]

Attachment 242578 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/bytecode/CodeBlock.cpp:2159:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:926:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:936:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:946:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/runtime/VM.cpp:955:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 5 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Comment on attachment 242578 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=242578&action=review

LGTM with comments.

> Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:2341
> +        generator.emitReturn(returnRegister.get());

You could return the constant Undefined here to make it clear that you're not actually returning anything real.  I believe that op_ret can take a constant operand.

> Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:2613
> +        // FIXME: To the JS programmer, running the normal path is the same basic block as running the uncaught exception path.

I like it when FIXME's reference bugs.  Can you file a bug for this?

[Saam Barati]

landed in:
http://trac.webkit.org/changeset/176836