Bug 146099 – Control Flow Profiler should keep execution counts of basic blocks

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Saam Barati]

This will prevent us from optimizing op_profile_control_flow compilation in the baseline and DFG because we will no
longer be able to change op_profile_control_flow into a no-op if the basic block executed. This will definitely slow down the control flow profiler a bit.

But, having execution counts for basic blocks will allow the inspector to do some badass stuff. So we should do it.

[Nikita Vasilyev]

Created attachment 255092 [details]
Animated GIF of the problem

I found a bug, see the attached animated GIF. After reloading a web page, executionCount values become very high.


Reduction:

click.html:
<button onclick="click()">click me</button>
<script src="click.js"></script>

click.js:
function click() {
    console.log("Clicked");
}

[Nikita Vasilyev]

Created attachment 255094 [details]
WIP

Here Saam's WIP patch and my Web Inspector WIP code execution heat map that is shown on the animated GIF above.

[Brian Burg]

Cool stuff! Some comments on the UI, which may be a different bug:

I have been sketching this exact UI for several years as a design exercise, and have convinced myself that mass highlights on top of source code are not the way to go for heat maps. They reduce readability of code, and waste a lot of visual attention to convey fairly little information. (Faded text for unexecuted code has the same effect on readability, but are more subtle and hide the code that's probably least relevant during debugging.) They work fine for things like diff viewers that only have 1-2 levels of intensity, but not for continuous or 5+ step color schemes. Most people can't distinguish small color differences, forcing more distracting colors.

I'm a much bigger fan of small widgets in gutters (left side) or floating rules (similar to inline error messages) that don't impact the line height of code.  Color is a somewhat low fidelity visual encoding, so combining it with a high fidelity encoding (position or length) would be good. Using a redundant visual encoding within a small space will probably convey the same high level information (this code is hot, simmering, or cold).

It is worth thinking about the use case for the visualization as well, since this determines what can be safely ignored or hidden behind an interaction. If there are 3 function calls on one line, the user might want further disambiguation to see which calls were fast or slow. Having timing data as well as counts would enable a lot of cool use cases. Only showing counts is tricky, because it can be misleading.

If the goal is to get a sense of hot code blocks, how much fidelity is required? I think the compilation tiers are reasonable, if arbitrary, bins for 'hotness' of code. That means a really simple, 5-step color encoding can be added to

[Timothy Hatcher]

Darin advocated for call counts in a gutter at the WebKit contributors meeting when this came up.

[Brian Burg]

[cont.]

a 5-step color encoding could be added to the foreground or background of the line number, or added next to the line numbers in a second gutter. A similar encoding is used by VS for showing local changes, but I would advocate a linear color scheme rather than using stoplight colors.

http://stackoverflow.com/questions/2823327/green-bars-in-visual-studio-2010

[Oliver Hunt]

The best profiler I have ever used was Shark, and its UI was based on line highlight. I have never found purely gutter or purely scrollbar feedback remotely easy to use.

If you want to place the information in the scrollbar you necessarily lose precision on any real file size. For both gutter and scrollbar feedback the visual target size is dramatically reduced.
Here is a query that produces many pictures of shark (and the evolution of shark, followed by the death of shark :( ): https://www.google.com/search?q=shark+profiler+mac&biw=1171&bih=797&source=lnms&tbm=isch&sa=X&ei=VQGDVe2HJ4KpogSGgYG4Ag&ved=0CAcQ_AUoAg

[Oliver Hunt]

Looked quickly at the patch, and I realize this is an actual bug, + an essentially unrelated ui change.

I'd make the codegen fix separate from the ui change so we don't get a real bug fix blocked on a ui niceness bug.

[Brian Burg]

(In reply to comment #7)
> Looked quickly at the patch, and I realize this is an actual bug, + an
> essentially unrelated ui change.
> 
> I'd make the codegen fix separate from the ui change so we don't get a real
> bug fix blocked on a ui niceness bug.

Yeah, definitely. We'll need to experiment. I made a separate bug for the UI concerns.

[Saam Barati]

(In reply to comment #7)
> Looked quickly at the patch, and I realize this is an actual bug, + an
> essentially unrelated ui change.
> 
> I'd make the codegen fix separate from the ui change so we don't get a real
> bug fix blocked on a ui niceness bug.

Right. Let's keep this bug for the JSC change with JSC tests. 
I sent Nikita a JSC diff via email that I think he posted here but when I
start working on this more I will make changes so that they're only
in JSC.

[Saam Barati]

(In reply to comment #3)
> Cool stuff! Some comments on the UI, which may be a different bug:
> 
> I have been sketching this exact UI for several years as a design exercise,
> and have convinced myself that mass highlights on top of source code are not
> the way to go for heat maps. They reduce readability of code, and waste a
> lot of visual attention to convey fairly little information. (Faded text for
> unexecuted code has the same effect on readability, but are more subtle and
> hide the code that's probably least relevant during debugging.) They work
> fine for things like diff viewers that only have 1-2 levels of intensity,
> but not for continuous or 5+ step color schemes. Most people can't
> distinguish small color differences, forcing more distracting colors.
> 
> I'm a much bigger fan of small widgets in gutters (left side) or floating
> rules (similar to inline error messages) that don't impact the line height
> of code.  Color is a somewhat low fidelity visual encoding, so combining it
> with a high fidelity encoding (position or length) would be good. Using a
> redundant visual encoding within a small space will probably convey the same
> high level information (this code is hot, simmering, or cold).
> 
> It is worth thinking about the use case for the visualization as well, since
> this determines what can be safely ignored or hidden behind an interaction.
> If there are 3 function calls on one line, the user might want further
> disambiguation to see which calls were fast or slow. Having timing data as
> well as counts would enable a lot of cool use cases. Only showing counts is
> tricky, because it can be misleading.
> 
> If the goal is to get a sense of hot code blocks, how much fidelity is
> required? I think the compilation tiers are reasonable, if arbitrary, bins
> for 'hotness' of code. That means a really simple, 5-step color encoding can
> be added to
I agree that JIT tiers are a good proxy for hotness. And at some point some
kind of visual hook for this information would be nice. Even if the details
are abstracted away to the user. I think tier up info alone is not good enough though. 
There is some JS code that JSC won't compile past the baseline JIT and so there
may be hot code that the JIT tier up status poorly indicates. 

I also completely agree that execution counts aren't good enough alone. 
I think time spent doing something is arguably more important. 

I also think execution counts have a separate nicety, especially because
they're at the basic block level and not the function level, and that is comparing
branching frequency.

[Nikita Vasilyev]

Let’s continue UI discussion in https://bugs.webkit.org/show_bug.cgi?id=146115.

(In reply to comment #7)
> Looked quickly at the patch, and I realize this is an actual bug, + an
> essentially unrelated ui change.
> 
> I'd make the codegen fix separate from the ui change so we don't get a real
> bug fix blocked on a ui niceness bug.

First of all, sorry about the confusion.

Saam sent me a JSC patch and while I was working on the UI for this I found a bug in the patch — bizarre execution counts after page reload. I cheated a patch with Saam’s original changes and my UI changes to demonstrate the problem.

[Saam Barati]

Created attachment 255171 [details]
path

This is the patch I sent Nikita.

[Saam Barati]

Created attachment 258219 [details]
patch

[Nikita Vasilyev]

Created attachment 259734 [details]
Saam's patch, rebaselined with ToT

[Saam Barati]

Created attachment 264823 [details]
patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/runtime/ControlFlowProfiler.h:103:  The parameter name "vm" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 1 in 14 files


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

[Saam Barati]

Created attachment 264873 [details]
patch

Added saturated add for 32-bit platforms.

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/runtime/ControlFlowProfiler.h:102:  One space before end of line comments  [whitespace/comments] [5]
Total errors found: 1 in 14 files


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

[Mark Lam]

Comment on attachment 264873 [details]
patch

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

> Source/JavaScriptCore/llint/LowLevelInterpreter32_64.asm:2421
> +    loadpFromInstruction(1, t0)
> +    loadi BasicBlockLocation::m_executionCount[t0], t1
> +    bilt t1, 0, .done
> +    addi 1, t1
> +    storei t1, BasicBlockLocation::m_executionCount[t0]
> +.done:

This is inconsistent with the implementation of BasicBlockLocation::emitExecuteCode() below.  Here, you allow the count to reach 0x8000000.  In BasicBlockLocation::emitExecuteCode() below, you only allow it to reach 0x7fffffff.  I'm not sure it really matters, but is there a reason that warrants this?

> Source/JavaScriptCore/runtime/BasicBlockLocation.cpp:89
> +void BasicBlockLocation::emitExecuteCode(CCallHelpers& jit, MacroAssembler::RegisterID t1, MacroAssembler::RegisterID t2) const

I recommend that you name the 2 registers as scratch1 and scratch2 so that it is clear that these are not inputs.

> Source/JavaScriptCore/runtime/BasicBlockLocation.cpp:97
> +    jit.load32(&m_executionCount, t1);
> +    jit.add32(CCallHelpers::TrustedImm32(1), t1);
> +    jit.move(t1, t2);
> +    jit.urshift32(CCallHelpers::TrustedImm32(31), t2); // Is the last bit 1 or 0. Most of the time it's zero and our sub does nothing. If it's 1, then we revert to the previous number which is where we will stay.
> +    jit.sub32(t2, t1);
> +    jit.store32(t1, bitwise_cast<void*>(&m_executionCount));

If I understand you correctly, I think you're trying to do an increment of the counter iff it is not going to overflow, right?  If so, I think you can express this more straightforwardly as:

jit.load32(&m_executionCount, scratch);
CCallHelpers::Jump done = jit.branchAdd32(CCallHelpers::Overflow, scratch, CCallHelpers::Imm32(1), scratch);
jit.store(scratch, bitwise_cast<void*>(&m_executionCount));
done.link(&jit);

That is unless you're trying to avoid a test and branch.  Are you?

> Source/JavaScriptCore/runtime/BasicBlockLocation.h:59
> +    void emitExecuteCode(CCallHelpers&, MacroAssembler::RegisterID, MacroAssembler::RegisterID) const;

I recommend that you name the 2 registers as scratch1 and scratch2 so that it is clear that these are not inputs.

[Saam Barati]

Created attachment 264946 [details]
patch

fixed w.r.t Mark's comments.

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/runtime/ControlFlowProfiler.h:102:  One space before end of line comments  [whitespace/comments] [5]
Total errors found: 1 in 14 files


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

[Mark Lam]

Comment on attachment 264946 [details]
patch

r=me

[Mark Lam]

Comment on attachment 264946 [details]
patch

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

> Source/JavaScriptCore/tests/controlFlowProfiler/execution-count.js:69
> +    print(basicBlockExecutionCount(testMax, "j++"));

Should we remove this?

[Michael Saboff]

Comment on attachment 264946 [details]
patch

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

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4816
> +        GPRTemporary scratch1(this);

I don't think this scratch is needed any more.

[Saam Barati]

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

[Joseph Pecoraro]

Comment on attachment 264946 [details]
patch

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

> Source/JavaScriptCore/inspector/protocol/Runtime.json:192
> +                { "name": "hasExecuted", "type": "boolean", "description": "Indicates if the basic block has executed before." },
> +                { "name": "executionCount", "type": "integer", "description": "Indicates how many times the basic block has executed." }

Seems we can replace hasExecuted with executionCount at a later time since it can be derived. Cool stuff!

[Nikita Vasilyev]

(In reply to comment #26)
> Comment on attachment 264946 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=264946&action=review
> 
> > Source/JavaScriptCore/inspector/protocol/Runtime.json:192
> > +                { "name": "hasExecuted", "type": "boolean", "description": "Indicates if the basic block has executed before." },
> > +                { "name": "executionCount", "type": "integer", "description": "Indicates how many times the basic block has executed." }
> 
> Seems we can replace hasExecuted with executionCount at a later time since
> it can be derived. Cool stuff!

Yes, that's the plan. hasExecuted will stay for a while for backward compatibility.

[Timothy Hatcher]

(In reply to comment #27)
> (In reply to comment #26)
> > Comment on attachment 264946 [details]
> > patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=264946&action=review
> > 
> > > Source/JavaScriptCore/inspector/protocol/Runtime.json:192
> > > +                { "name": "hasExecuted", "type": "boolean", "description": "Indicates if the basic block has executed before." },
> > > +                { "name": "executionCount", "type": "integer", "description": "Indicates how many times the basic block has executed." }
> > 
> > Seems we can replace hasExecuted with executionCount at a later time since
> > it can be derived. Cool stuff!
> 
> Yes, that's the plan. hasExecuted will stay for a while for backward
> compatibility.

It does not need to stay i the backend. The front-end will need to support both hasExecuted and executionCount to work with iOS 9 and future iOS releases. But on Mac we always ship the new Inspector with the matching backend.

Anyway, we can drop hasExecuted and just use executionCount > 1.