Bug 146099 - Control Flow Profiler should keep execution counts of basic blocks
Summary: Control Flow Profiler should keep execution counts of basic blocks
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Saam Barati
URL:
Keywords:
Depends on:
Blocks: 146115
  Show dependency treegraph
 
Reported: 2015-06-17 23:43 PDT by Saam Barati
Modified: 2015-11-20 10:53 PST (History)
15 users (show)

See Also:


Attachments
Animated GIF of the problem (1.06 MB, image/gif)
2015-06-18 00:37 PDT, Nikita Vasilyev
no flags Details
WIP (226.64 KB, patch)
2015-06-18 00:48 PDT, Nikita Vasilyev
nvasilyev: review-
nvasilyev: commit-queue-
Details | Formatted Diff | Diff
path (9.43 KB, patch)
2015-06-18 21:54 PDT, Saam Barati
no flags Details | Formatted Diff | Diff
patch (10.22 KB, patch)
2015-08-04 15:21 PDT, Saam Barati
no flags Details | Formatted Diff | Diff
Saam's patch, rebaselined with ToT (10.90 KB, patch)
2015-08-22 21:38 PDT, Nikita Vasilyev
nvasilyev: review-
nvasilyev: commit-queue-
Details | Formatted Diff | Diff
patch (19.19 KB, patch)
2015-11-04 15:52 PST, Saam Barati
no flags Details | Formatted Diff | Diff
patch (21.42 KB, patch)
2015-11-05 11:33 PST, Saam Barati
no flags Details | Formatted Diff | Diff
patch (21.23 KB, patch)
2015-11-06 12:02 PST, Saam Barati
mark.lam: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Saam Barati 2015-06-17 23:43:33 PDT
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.
Comment 1 Nikita Vasilyev 2015-06-18 00:37:05 PDT
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");
}
Comment 2 Nikita Vasilyev 2015-06-18 00:48:29 PDT
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.
Comment 3 Brian Burg 2015-06-18 09:40:54 PDT
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
Comment 4 Timothy Hatcher 2015-06-18 10:29:34 PDT
Darin advocated for call counts in a gutter at the WebKit contributors meeting when this came up.
Comment 5 Brian Burg 2015-06-18 10:31:54 PDT
[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
Comment 6 Oliver Hunt 2015-06-18 10:40:47 PDT
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
Comment 7 Oliver Hunt 2015-06-18 10:47:32 PDT
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.
Comment 8 Brian Burg 2015-06-18 10:51:59 PDT
(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.
Comment 9 Saam Barati 2015-06-18 12:02:45 PDT
(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.
Comment 10 Saam Barati 2015-06-18 12:13:43 PDT
(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.
Comment 11 Nikita Vasilyev 2015-06-18 15:50:33 PDT
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.
Comment 12 Saam Barati 2015-06-18 21:54:58 PDT
Created attachment 255171 [details]
path

This is the patch I sent Nikita.
Comment 13 Saam Barati 2015-08-04 15:21:01 PDT
Created attachment 258219 [details]
patch
Comment 14 Nikita Vasilyev 2015-08-22 21:38:56 PDT
Created attachment 259734 [details]
Saam's patch, rebaselined with ToT
Comment 15 Saam Barati 2015-11-04 15:52:45 PST
Created attachment 264823 [details]
patch
Comment 16 WebKit Commit Bot 2015-11-04 15:55:48 PST
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.
Comment 17 Saam Barati 2015-11-05 11:33:55 PST
Created attachment 264873 [details]
patch

Added saturated add for 32-bit platforms.
Comment 18 WebKit Commit Bot 2015-11-05 11:35:33 PST
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.
Comment 19 Mark Lam 2015-11-05 12:27:07 PST
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.
Comment 20 Saam Barati 2015-11-06 12:02:54 PST
Created attachment 264946 [details]
patch

fixed w.r.t Mark's comments.
Comment 21 WebKit Commit Bot 2015-11-06 12:04:58 PST
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.
Comment 22 Mark Lam 2015-11-06 12:09:16 PST
Comment on attachment 264946 [details]
patch

r=me
Comment 23 Mark Lam 2015-11-06 12:11:41 PST
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?
Comment 24 Michael Saboff 2015-11-06 13:29:05 PST
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.
Comment 25 Saam Barati 2015-11-06 19:27:50 PST
landed in:
http://trac.webkit.org/changeset/192125
Comment 26 Joseph Pecoraro 2015-11-06 19:50:42 PST
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!
Comment 27 Nikita Vasilyev 2015-11-19 17:38:55 PST
(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.
Comment 28 Timothy Hatcher 2015-11-20 10:53:19 PST
(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.