IonMonkey: Set range of Length MIR nodes.

RESOLVED FIXED in mozilla26

Status

()

defect
RESOLVED FIXED
7 years ago
6 years ago

People

(Reporter: nbp, Assigned: mtornwall)

Tracking

Trunk
mozilla26
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [mentor=nbp][lang=c++][ion:t])

Attachments

(1 attachment, 1 obsolete attachment)

In js/src/ion/MIR.h multiple instructions are defining the range of int values returned by the instruction.  It would be good to follow the same lead and use either range()->setLower(0) or range()->set(0, JSVAL_INT_MAX) in the appropriate MIR node constructors.
Whiteboard: [mentor=nbp][lang=c++] → [mentor=nbp][lang=c++][ion:t]
What is the expected performance win from this? Is it something that would show up on the benchmarks or a microbenchmark?
I want to work on this bug.I am well acquainted with the knowledge of c/c++.I think it this first bug would be a great opportunity for me.
(In reply to Bablu Kumar from comment #2)
> I want to work on this bug.I am well acquainted with the knowledge of
> c/c++.I think it this first bug would be a great opportunity for me.

Great, I suggest you to make a micro benchmark where for example you do some multiplication of length properties.  The fact that we infer that the length are positive numbers will give us the ability to remove the negative zero check of the multiplications.

Something like that will make the premise of a micro-benchmark:

  var foo = new Int8Array(new ArrayBuffer(10000));
  for (var i = 0; i < foo.length; i++)
    var x = foo.length; // TODO: [0, INT_MAX]
    if (x < 10000) { // beta node will restrict to [0, 9999]
      foo[i] = x * i; // will remove the negative zero check.
    }
  }

The modification you will have to do will be in js/src/ion/MIR.h and in js/src/ion/RangeAnalysis.cpp .  You can check the result of the range analysis by IonMonkey spew as detailed here[1].

If you have any questions, do hesitate to comment on Bugzilla and to ask.  You can also ask on irc.mozilla.org #ionmonkey.  We would be happy to answer any of your questions ;)

If you haven't done so, I'll recommend you to download the sources from either mercurial or git, and to start compiling the shell, as documented on [2].

[1] https://developer.mozilla.org/en-US/docs/SpiderMonkey/Hacking_Tips#Using_IonMonkey_spew_%28JS_shell%29

[2] https://developer.mozilla.org/en-US/docs/SpiderMonkey/Build_Documentation
This bug has been inactive for over 4 months. I'd like to work on this. Am I free to try to solve it?
(In reply to Tom Fitzhenry from comment #4)
> This bug has been inactive for over 4 months. I'd like to work on this. Am I
> free to try to solve it?

Yes, I will assign you the bug.

This bug should be easy, it consists of adding a few function in js/src/ion/RangeAnalysis.cpp to compute the range of the MIR instructions (defined in js/src/ion/MIR.h) of the Length properties.  These functions should set a Range to [0, INT32_MAX], because the type inference guarantee that we return an Int32 for these MIR instructions in (IonBuilder::jsop_length_fastPath, in js/src/ion/IonBuilder.cpp)
Assignee: general → persona
Tom, are you still working on this bug? If not, I'd like to take it.
Hi Martin,

My priorities have changed, and I'm no longer able to work on this. Feel free to take it.

Hints:
    * the compute range method mentioned above is MDefinition::computeRange() (and its subclasses)
    * the example test in https://bugzilla.mozilla.org/show_bug.cgi?id=801921#c3 is not useful. This is because the length property of typed arrays are statically inferable. e.g. in the example foo.length will always return 10000. The compiler, being smart, will replace `foo.length` with `10000`. The constant 10000 has a trivial range of [10000, 10000], and so the proposed change to restrict its range to [0, INT_MAX] isn't an improvement, since [10000,10000] is contained in [0, INT_MAX]
    * for other instructions that have length properties (e.g. MArrayLength), setting a range of [0,INT_MAX] is indeed an improvement over what I think its current range is: [-INF,INF]

When I added this range information, however, I wasn't able to demonstrate a performance increase, which is where I got stuck. :)

Have fun!
Assignee: persona → general
(In reply to Tom Fitzhenry from comment #7)
Thanks a lot for those useful pointers!

> When I added this range information, however, I wasn't able to demonstrate a
> performance increase, which is where I got stuck. :)

Interesting. Do you by any chance have a patch that you could attach so
the work you've already done doesn't have to be duplicated?

Nicolas: In light of this new information, is the bug still relevant?
If so, can I take it on? I expect I will need some mentoring as I'm
new to IonMonkey.
Also worth noting here is that the example in comment 3 may be made more interesting once the main patch for bug 910807 lands [0]. It's pretty close, but I'm considering waiting until something like bug 909528 is done, because I'm not completely comfortable with rectifyExponent() as it currently stands.

[0] https://bug910807.bugzilla.mozilla.org/attachment.cgi?id=798173
It turns out I was wrong in comment 9; this testcase doesn't need the bug 910807 patch for the x < 10000 beta node to work.

Also, while Tom above said "The compiler, being smart, will replace `foo.length` with `10000`.", I don't actually see this happening. This may be worth some investigation, if it's indeed a valid optimization.

So it looks like the testcase in comment 3 is interesting, and this does seem like a good introductory project.
(In reply to Martin Törnwall [:mtornwall] from comment #8)
> (In reply to Tom Fitzhenry from comment #7)
> Thanks a lot for those useful pointers!
> 
> > When I added this range information, however, I wasn't able to demonstrate a
> > performance increase, which is where I got stuck. :)
> 
> Nicolas: In light of this new information, is the bug still relevant?
> If so, can I take it on? I expect I will need some mentoring as I'm
> new to IonMonkey.

A wrong type information is something which can leak into a fast path.  So having the right range information is still interesting, and as sunfish pointed: « this does seem like a good introductory project ».
Assignee: general → martin
You mentioned changing some MIR node constructors. It seems to me that the easiest way of setting the ranges is to simply override the |computeRange| function and setting |Range(0, JSVAL_INT_MAX)| from there. Is there any particular reason to avoid this?
(In reply to Dan Gohman [:sunfish] from comment #10)
> Also, while Tom above said "The compiler, being smart, will replace
> `foo.length` with `10000`.", I don't actually see this happening. This may
> be worth some investigation, if it's indeed a valid optimization.

It's valid and not valid.  Array buffers have fixed length, roughly -- except that a buffer can be neutered, setting its length to zero.  That affects any views of that buffer, of course.  Whether you guard on the buffer not being neutered (in which case you can't inline 10000), or change the neutering code path to trigger recompilation of any affected scripts (in which case you can), is of course an implementation choice.  But it does make things more complicated than just inlining a constant length, in some cases.  (Comment 3 isn't such a more-complicated case, as far as I can tell, tho -- it's constrained enough that I don't think you can escape into a neutering attempt.  The compiler might not always be smart enough to figure that out, in general, tho.)
(In reply to Martin Törnwall [:mtornwall] from comment #12)
> You mentioned changing some MIR node constructors. It seems to me that the
> easiest way of setting the ranges is to simply override the |computeRange|
> function and setting |Range(0, JSVAL_INT_MAX)| from there. Is there any
> particular reason to avoid this?

This is the way to go.  There is no reason to avoid this.
Posted patch length-ranges.patch (obsolete) — Splinter Review
Am I headed in the right direction here?
Comment on attachment 802358 [details] [diff] [review]
length-ranges.patch

Review of attachment 802358 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +1180,5 @@
> +MTypedArrayLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));
> +}
> +

I believe the actual upper limit on the length of an array is INT_MAX/2.  Someone more familiar with this stuff should correct me if I'm wrong.
For MStringLength you can use JSString::MAX_LENGTH.
(In reply to Marty Rosenberg [:mjrosenb] from comment #16)
> I believe the actual upper limit on the length of an array is INT_MAX/2. 
> Someone more familiar with this stuff should correct me if I'm wrong.

The array length is apparently limited at UINT32_MAX:

js> var a = new Array(0xffffffff);   // ok
js> var a = new Array(0xffffffff+1); // RangeError: invalid array length
Comment on attachment 802358 [details] [diff] [review]
length-ranges.patch

Review of attachment 802358 [details] [diff] [review]:
-----------------------------------------------------------------

Good, now let me give you a little tour of the engine with more internal details …

Also you should configure your mercurial to produce diff with enough context, see [0].

[0] https://developer.mozilla.org/ja/docs/Mercurial_FAQ#How_can_I_generate_a_patch_for_somebody_else_to_check-in_for_me.3F

::: js/src/jit/RangeAnalysis.cpp
@@ +1172,5 @@
>  
> +void
> +MArrayLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));

You can use UINT32_MAX, but be aware that when we do that we "currently" need to make this followed by a call to extendUInt32ToInt32Min().

So for Arrays, this will not provide any new information until we come with a MIRType_UInt32.  We have the same problem with the >>> (unsigned right shift), and with typed arrays.

@@ +1178,5 @@
> +
> +void
> +MTypedArrayLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));

For typed array, the limit is indeed UINT32_MAX >> 1 (i-e INT32_MAX, or JSVAL_INT_MAX)

@@ +1184,5 @@
> +
> +void
> +MStringLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));

As Jan mentioned, here we should use JSString::MAX_LENGTH because a string cannot go above this value which is smaller than JSVAL_INT_MAX, as we pack the length attribute with 4 flags which are used to distinguish different kind of encoding, see [1].

[1] http://dxr.mozilla.org/mozilla-central/source/js/src/vm/String.h#l133

@@ +1190,5 @@
> +
> +void
> +MArgumentsLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));

As IonMonkey is using the C stack, we have a cap on the number of actual argument (actual argument is the effective list of argument given to a function when it is called, and which can be recovered with this function).

The cap is used to prevent people from doing stack overflow by calling a function with too many arguments, see [2].

[2] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/Ion.cpp#l1689

@@ +1196,5 @@
> +
> +void
> +MInitializedLength::computeRange()
> +{
> +    setRange(new Range(0, JSVAL_INT_MAX));

This is identical to MArrayLength.
Attachment #802358 - Flags: feedback+
(In reply to Nicolas B. Pierron [:nbp] from comment #19) 
> @@ +1190,5 @@
> > +
> > +void
> > +MArgumentsLength::computeRange()
> > +{
> > +    setRange(new Range(0, JSVAL_INT_MAX));
> 
> As IonMonkey is using the C stack, we have a cap on the number of actual
> argument (actual argument is the effective list of argument given to a
> function when it is called, and which can be recovered with this function).

|TooManyArguments| compares with |SNAPSHOT_MAX_NARGS|; can I rely on that as a conservative upper bound for the MArgumentsLength range?
(In reply to Martin Törnwall [:mtornwall] from comment #20)
> (In reply to Nicolas B. Pierron [:nbp] from comment #19) 
> > @@ +1190,5 @@
> > > +
> > > +void
> > > +MArgumentsLength::computeRange()
> > > +{
> > > +    setRange(new Range(0, JSVAL_INT_MAX));
> > 
> > As IonMonkey is using the C stack, we have a cap on the number of actual
> > argument (actual argument is the effective list of argument given to a
> > function when it is called, and which can be recovered with this function).
> 
> |TooManyArguments| compares with |SNAPSHOT_MAX_NARGS|; can I rely on that as
> a conservative upper bound for the MArgumentsLength range?

Yes, and add a comment next to it that this is conservative compared to what TooManyArguments reports.
I went ahead and set array/initialized lengths to UINT32_MAX, including the extension to int32 min. In doing so I also opted to use INT32_MAX instead of JSVAL_INT_MAX for other lengths as it seemed better for consistency.

Hopefully I managed to set up Mercurial correctly this time. :)
Attachment #802358 - Attachment is obsolete: true
Attachment #803564 - Flags: review?(nicolas.b.pierron)
Comment on attachment 803564 [details] [diff] [review]
length-ranges.patch

Review of attachment 803564 [details] [diff] [review]:
-----------------------------------------------------------------

Nice work. :)

I will commit it for you.
Attachment #803564 - Flags: review?(nicolas.b.pierron) → review+
The following link [1] is where your patch is visible inside mozilla-inbound, which is the tree where we usualy push ("land") the patches.  Then this will move to mozilla-central, and if there is no issue, this will move into beta, aurora and release where your changes would be available to all Firefox users ;)

You can follow the status of your changes on tbpl [2], which is our continuous integration system.

Congratulation!

[1] https://hg.mozilla.org/integration/mozilla-inbound/rev/e1cf000a73c8
[2] https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=e1cf000a73c8
https://hg.mozilla.org/mozilla-central/rev/e1cf000a73c8
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla26
You need to log in before you can comment on or make changes to this bug.