IonMonkey GSoC proposal

[Péricles Alves]

Hello guys,

I am currently a Computer Science undergraduate student at UFMG, the same
university of Igor Rafael and Rodrigo Sol, who have done Summer of Code
projects in TraceMonkey.

I have been working in IonMonkey for the last three months writing an
optimization pass (Traditional Constant Propagation) and I have also
reported a bug about the creation of use-def chains (bug 727480).

I would like to submit the following proposal to GSoC 2012. Could you tell
me if you think it will be a feasible project?


Best regards,

Péricles Alves.

===========================================================================

---------------------------------------------------------------------------
Implementing Demand-driven Elimination of Array-Bounds Checks on IonMonkey
---------------------------------------------------------------------------

Objective
---------
The objective of this work is to implement the ABCD algorithm,
proposed in PLDI 2000 by Bodik, Gupta and Sarkar [1], on the IonMonkey
JavaScript JIT compiler. ABCD is a light-weight algorithm for
elimination of fully and partially redundant Array Bounds Checks on
Demand. The elimination of such bounds checks brings program execution
speedup by eliminating the cost of executing the bounds checks
themselves and increasing the application of various code
optimizations. Since IonMonkey is a dynamic compilation environment
and implements the SSA intermediate representation, I believe that the
ABCD algorithm suits it very well.

Background
----------
IonMonkey is the new Just-in-time Javascript compiler of the Mozilla
foundation, which will be part of the SunSpider engine. Despite being
in development, IonMonkey promises to be a strong competitor in the so
called "browser war". The compiler uses the whole-method compilation
approach and has the additional ability to perform type
specialization. Furthermore, it implements the SSA intermediate
representation, which facilitates many advanced compiler
optimizations, such as copy propagation, partial redundancy
elimination, dead-code elimination, and loop-invariant code motion.

JavaScript, as many other languages, requires bounds checking during
array access in order to guarantee the soundness of its semantics.
Bounds checks are known to make programs slower for two reasons.
Firstly, because each bound check requires one load and two compare
operations. Second, and most important, the presence of array bounds
checks drastically limits the application of code optimizations that
involve code motion. Such limitation happens because the bound cheks
break the control flow graph into smaller basic blocks; hence,
preventing code from moving across larger program regions.

The role of elimination of Array Bounds Checks on Demand
---------------------------------------------------------
To solve the above mentioned problem, many algorithms [2, 3, 4] have
been proposed in order to eliminate redundant array bounds checks.
However, these algorithms are heavyweight and are not able to
eliminate partially redundant bounds checks. Moreover, they might not
scale up to large programs, because they have been designed to work on
dense program representations, which map information to each program
point, instead of assigning this information to variables themselves.
Some of these factors greatly limits the implementation of such
algorithms in dynamic compilation environments.

The ABCD algorithm [1], on other hand, has been designed specifically
to JIT compilers.
Therefore, it relies on lightweight techniques. It is able to remove
both partially and fully redundant bounds checks. Furthermore, it
works upon a sparse representation, like the SSA form, which is
available in IonMonkey. Finally, it is demand-driven, which means that
the algorithm can focus on the most frequently executed bounds checks,
matching the time constraints of dynamic compilation environments.

The steps of the ABCD algorithm are summarized below:
1. Cheap construction of the extended SSA (e-SSA) graph.
2. Construction of a single, program-point-independent constraint
system, namely the inequality graph.
3. Demand-driven traversal of the inequality graph.
4. Bounds checks elimination.

Expected results
----------------
The authors of the ABCD algorithm implemented their approach in the
Jalapeño optimizing compiler with a set of standard optimizations
enabled. Their experimental results show that ABCD removes on average
45% of all dynamic bounds checks. Moreover, they reported 10% of
speedup in the Symantec benchmarks.

Timeline
--------
Since it is a three months project, the implementation phases will be
divided weekly as shown below:

(2 weeks) Make IonMonkey able to generate the extended SSA (e-SSA)
graph, which encodes the scope of constraints, from its available SSA
intermediate representation. We have implemented a pass to convert
code to e-SSA form in LLVM. It is very fast, taking negligible time,
and increasing program sizes by 7% on average. Basically, we have to
split the live ranges of variables used at conditionals. Given that
IonMonkey already gives us def-use chains, we can quickly rename
variables after live range splitting.

(2 weeks) Implement construction of the program-point-independent
constraint system, which is represented as a weighted directed graph.

(3 weeks) Implement the demand-driven constraint solver, which favors
performance of a single-check analysis.

(2 weeks) Implement the transformation of partially redundant checks
in fully redundant checks.

(2 weeks) Implement the elimination of lower- and upper-bounds checks.

(1 week) Test the whole implementation and write a final report.

Why I am a good candidate to this project
-----------------------------------------
I am a third year Computer Science undergraduate student at the
Federal University of Minas Gerais, which is one of the top-5 Computer
Science schools in Brazil, and I work as a research assistant in the
Programming Languages Laboratory at this university. I believe I can
do well in this project because I am pretty experienced with C++ and I
have been implementing some optimizations in the IonMonkey compiler,
which is the target of this work. As an example, I have been able to:
1) Instrument the SpiderMonkey interpreter to check how many functions
are called at most once in the 100 most visited pages according to the
Alexa index. We found that 48.7% of the functions are called only
once.
2) I have implemented a form of constant propagation on IonMonkey that
assumes that the parameters of the functions will not change. This
assumption is reasonable, given that most functions are only called
once.
3) I have also implemented traditional constant propagation in IonMonkey.
4) I have found one bug in the def-use chains in IonMonkey. The bug
was reported in bugzilla, at 727480.

Finally, I am working with Igor Rafael, who has done a Summer of Code
project in 2011 in TraceMonkey, another Mozilla's JIT compiler, under
the mentorship of David Mandelin.

References
----------
[1] R. Bodik, R. Gupta and V. Sarkar. ABCD: Eliminating Array-Bounds
Checks on Demand. In Proceedings of the Conference on Programming
language design and implementation, 2000.

[2] W.H. Harrison. Compiler analysis for the value ranges of
variables. IEEE Transactions on Software Engineering, SE-
3(3):243–250, May 1977.

[3] V. Markstein, J. Cocke and P. Markstein. Optimization of range
checking. In Proceedings of a Symposium on Compiler Optimization,
pages 114–119, June 1982.

[4] N. Suzuki and K. Ishihata. Implementation of an array bound
checker. In Conference Record of the Fourth ACM Symposium on
Principles of Programming Languages, pages 132–143, Los Angeles,
California, January 17–19, 1977. ACM SIGACT-SIGPLAN.

[David Anderson]

I like the idea and I'm excited to see someone using IonMonkey already!
It sounds feasible, though you may want to perform some kind of limit
study on a benchmark to see what sort of gains you get. Kraken in
particular has many array accesses, or you could create a microbenchmark.

A few questions:

> ----------
> IonMonkey is the new Just-in-time Javascript compiler of the Mozilla
> foundation, which will be part of the SunSpider engine. Despite being
> in development, IonMonkey promises to be a strong competitor in the so

Small nit: s/SunSpider/SpiderMonkey/ I think?

> involve code motion. Such limitation happens because the bound cheks
> break the control flow graph into smaller basic blocks; hence,
> preventing code from moving across larger program regions.

Could you describe this a little more? In IonMonkey, we can hoist bounds
checks, and there are no explicit dependencies between bounds checks and
further instructions (though the check itself is never removed by DCE).

> (2 weeks) Make IonMonkey able to generate the extended SSA (e-SSA)
> graph, which encodes the scope of constraints, from its available SSA
> intermediate representation. We have implemented a pass to convert
> code to e-SSA form in LLVM. It is very fast, taking negligible time,
> and increasing program sizes by 7% on average. Basically, we have to
> split the live ranges of variables used at conditionals. Given that
> IonMonkey already gives us def-use chains, we can quickly rename
> variables after live range splitting.

What does live-range splitting mean here?

> (3 weeks) Implement the demand-driven constraint solver, which favors
> performance of a single-check analysis.

Out of curiosity, how is performance determined?

-David

> _______________________________________________
> dev-tech-js-engine-internals mailing list
> dev-tech-js-en...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-tech-js-engine-internals
>

[Dave Mandelin]

I agree with David, plus:

- I highly recommend doing the limit study, because we've found that the effect of specific optimizations can be small on benchmarks, and can be swamped by basic engineering stuff. You'll want to know how much perf you might be able to get before you start.

- I emphasize that because I reread the ABCD paper a while back while
planning IonMonkey. At the time I decided that there were probably
simpler techniques for eliminating most range checks that would have
less complexity and better compile time, so I didn't pursue it.

- As an alternative IonMonkey idea, you might want to look into inlining objects into stack frames via escape analysis. We actually don't know how much effect it would have yet, and it also interacts with GC, which is in flux, but we've been pretty curious if it would help our perf.

- Another idea is to look at a better alias analysis for IonMonkey. Currently it's using something very simple, along the lines of "a.b aliases c.d" for any a,b,c,d. Again, we don't know how much it will help yet.

Dave

[Dave Mandelin]

I agree with David, plus:

- I highly recommend doing the limit study, because we've found that the effect of specific optimizations can be small on benchmarks, and can be swamped by basic engineering stuff. You'll want to know how much perf you might be able to get before you start.

- I emphasize that because I reread the ABCD paper a while back while
planning IonMonkey. At the time I decided that there were probably
simpler techniques for eliminating most range checks that would have
less complexity and better compile time, so I didn't pursue it.

- As an alternative IonMonkey idea, you might want to look into inlining objects into stack frames via escape analysis. We actually don't know how much effect it would have yet, and it also interacts with GC, which is in flux, but we've been pretty curious if it would help our perf.

- Another idea is to look at a better alias analysis for IonMonkey. Currently it's using something very simple, along the lines of "a.b aliases c.d" for any a,b,c,d. Again, we don't know how much it will help yet.

Dave

On Wednesday, April 4, 2012 11:51:40 AM UTC-7, David Anderson wrote:

[Andrew McCreight]

Another thing to keep in mind is that the original implementation in Jalapeno of the ABCD algorithm only deals with either upper or lower bounds (I forget which) and IIRC didn't worry about integer overflow. So there may be some nasty details to wrangle over if you want to get it to a landable state.

If you decide to work on this, I worked on a sort of verification of an implementation of ABCD a while ago, so I may have some residual knowledge of ABCD rattling around in my brain I can help you with.

Andrew

[Péricles Alves]

>> involve code motion. Such limitation happens because the bound cheks
>> break the control flow graph into smaller basic blocks; hence,
>> preventing code from moving across larger program regions.
>
> Could you describe this a little more? In IonMonkey, we can hoist bounds
> checks, and there are no explicit dependencies between bounds checks and
> further instructions (though the check itself is never removed by DCE).

I wrote it like this because an array bounds check is implemented as a
conditional. There are some code optimizations, such as local register
allocation
and partial redundancy elimination that suffer with a more fragmented
control flow graph. So, I think that by removing more bound checks we
may also enable further optimizations.

>
>
>> (2 weeks) Make IonMonkey able to generate the extended SSA (e-SSA)
>> graph, which encodes the scope of constraints, from its available SSA
>> intermediate representation. We have implemented a pass to convert
>> code to e-SSA form in LLVM. It is very fast, taking negligible time,
>> and increasing program sizes by 7% on average. Basically, we have to
>> split the live ranges of variables used at conditionals. Given that
>> IonMonkey already gives us def-use chains, we can quickly rename
>> variables after live range splitting.
>
>
> What does live-range splitting mean here?

It is like this: ABCD is a sparse analysis. It means that the
information that it finds must be true along the entire live range of
the variable. In this case, the information is "variable x is less
than variables {x0, x1, ..., xn}". This is called the "less-than"
lattice. But, in order to be precise, the ABCD must learn information
out of conditionals. If we have a program like:

if (x < a.length) {
...
// we know that x < a.length here
...
} else {
...
// we know that a.length <= x here
...
}
Then, we need a different version of x in the then part and in the
else part of the branch. The ABCD algorithm achieves this by splitting
the live ranges of x via copy instructions:
if (x < a.length) {
x0 = x;
// rename every use of x to x0 in the 'then' clause
...
} else {
x1 = x;
// rename every use of x in to x1 in the 'else' clause
...

}

>> (3 weeks) Implement the demand-driven constraint solver, which favors
>> performance of a single-check analysis.
>
> Out of curiosity, how is performance determined?

In the original paper, it was measured in runtime of ABCD algorithm +
runtime of benchmark.

>
> - I highly recommend doing the limit study, because we've found that the
> effect of specific optimizations can be small on benchmarks, and can be
> swamped by basic engineering stuff. You'll want to know how much perf you
> might be able to get before you start.

Right. How should a good limit study be? I mean, which kind of info
you guys think would be the most useful to get now?

> - I emphasize that because I reread the ABCD paper a while back while
> planning IonMonkey. At the time I decided that there were probably
> simpler techniques for eliminating most range checks that would have
> less complexity and better compile time, so I didn't pursue it.

I see. Yes, many optimizations that are designed for JITs wound up not
being used because they take too long to run. But, according to the
original authors, ABCD has been specifically designed to run fast.
Maybe an initial implementation could be useful to you guys, so that
either you would have something that is worth improving (as it has the
potential to deliver good results), or you could decide that a lighter
algorithm is necessary to be used in a JIT compiler. If you have ideas
of how to make ABCD even faster, I would be very happy to give them a
try.

> - As an alternative IonMonkey idea, you might want to look into inlining
> objects into stack frames via escape analysis. We actually don't know how
> much effect it would have yet, and it also interacts with GC, which is in
> flux, but we've been pretty curious if it would help our perf.
>
> - Another idea is to look at a better alias analysis for IonMonkey.
> Currently it's using something very simple, along the lines of "a.b
aliases
> c.d" for any a,b,c,d. Again, we don't know how much it will help yet.

Actually, the Summer of Code rules allow me to write more than one
proposal. If you guys prefer, I can write a new document. Or I could
put some effort in getting the limit study ready before the deadline
(Friday). What do you think should be better?


Regards,

2012/4/4 Andrew McCreight <amccr...@mozilla.com>

> Another thing to keep in mind is that the original implementation in
> Jalapeno of the ABCD algorithm only deals with either upper or lower bounds
> (I forget which) and IIRC didn't worry about integer overflow. So there
> may be some nasty details to wrangle over if you want to get it to a
> landable state.
>
> If you decide to work on this, I worked on a sort of verification of an
> implementation of ABCD a while ago, so I may have some residual knowledge
> of ABCD rattling around in my brain I can help you with.
>
> Andrew
>
> ----- Original Message -----

--
Péricles <http://dcc.ufmg.br/%7Epericlesrafael>

[Gervase Markham]

On 04/04/12 17:33, Péricles Alves wrote:
> I would like to submit the following proposal to GSoC 2012. Could you tell
> me if you think it will be a feasible project?

If in doubt, submit! You have 1 day, 2 hours left at time of writing.
You can always tweak the proposal later, but if you don't have an entry
in the system, that's it - no late entrants.

Gerv