Nicolas B. Pierron [:nbp] Reporter
	Description • 11 years ago

Currently SpiderMonkey lacks the mechanism to obtain branch profiling information and has no heuristic to guess the probability of each conditional jump. Basic blocks could not be removed unless IonMonkey can prove that they are not reachable. By introducing the branch profiling data IonMonkey will have the ability to aggressively filter out the infrequently used basic blocks and therefore simplify subsequent analyses like type inference and alias analysis. Nicolas Pierron, an IonMonkey developer, suggested that other optimizations such as GVN & LICM might benefit from the profiling information even if branches were not removed.

The main difference between the Unreachable Code Elimination (UCE) and our method is that UCE guarantees the removal of branches are safe, while the branches filtered out in our method might be accessed under particular circumstances. In this case our method generates a bailout and return the control back to the interpreter. The cost of bailout is not free. What is more expensive is the time spent in the slower mode of execution (baseline, interpreter). A basic block is worth to be filtered out only when the benefits we get are bigger than the cost we introduced. Thus, it is necessary to assess the impact on the analyses and optimizations implemented in IonMonkey.

The first goal of this project is to instrument the code generated by the baseline compiler to get branch profiles and then use these profiles to filter out infrequently used branches. The second goal is to analyze the benefit of such approach and the impact on other analyses and transformations.

[*] https://github.com/lazyparser/gsoc2013/blob/master/proposal.md

	Wei Wu [:wuwei UTC+8] Assignee
	Comment 1 • 11 years ago

Branch profile for octane/box2d.js.

I got these data by instrumenting the interpreter and using the command arguments below:

./js --no-ion --no-jm --no-baseline

In this configuration the interpreter can see all branches.

	Wei Wu [:wuwei UTC+8] Assignee
	Comment 4 • 11 years ago

This patch is used for collecting branch data only.

	Wei Wu [:wuwei UTC+8] Assignee
	Comment 5 • 11 years ago

Branch profiles for other octane programs can be downloaded at:
https://github.com/lazyparser/gsoc2013/tree/master/preexperiments/octane

	Nicolas B. Pierron [:nbp] Reporter
	Comment 6 • 11 years ago

(In reply to Wei Wu [:wuwei] from comment #5)
> Created attachment 764603 [details]
> Branch profile for octane/pdf.js
> 
> Branch profiles for other octane programs can be downloaded at:
> https://github.com/lazyparser/gsoc2013/tree/master/preexperiments/octane

Awesome, by running

  $ grep -v BRANCH pdfjs.js.profile | sort -R | uniq -c | sort -gk 3

I am able to see that we have a bunch of compilable branches which are either never executed, or rarely executed.  "-gk 3" sorts per regs.pc, so we have the number of hit for each instructions for the _JUMP / _NOJUMP cases.

One of the obvious cases which happens 30k in pdfjs is the execution of "assert(cond)", where surprisingly, the condition is constantly true.

Other cases might need to be investigated a bit more, like pdfjs.js:145, where the conditions are loop edges.

  while (i < data.length) {
    i += 3;
    if (i === data.length + 2) … /* 20 times */
    else if (i === data.length + 1) … /* 5 times */
    else … /* 131 000 times */
  }

One thing which is sure, is that unless this function is inlined it seems fine to bail on these conditions.  The other thing is that we can probably re-order basic blocks to make the most likely case shorter, but this might imply that we do not respect the RPO after re-ordering.

	Wei Wu [:wuwei UTC+8] Assignee
	Comment 7 • 11 years ago

Branch profiles for SunSpider benchmark can be viewed or downloaded at:

https://github.com/lazyparser/gsoc2013/tree/master/preexperiments/sunspider

	Wei Wu [:wuwei UTC+8] Assignee
	Comment 8 • 11 years ago

I've done a quick benefit analysis for branch pruning:

https://github.com/lazyparser/gsoc2013/blob/master/benefit_analysis.md

Detailed information (.csv format) can be download at:

https://github.com/lazyparser/gsoc2013/tree/master/benefit_analysis