Bounds computed by bit and are incorrect.

RESOLVED FIXED in Firefox 18

Status

()

Core
JavaScript Engine
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: mjrosenb, Unassigned)

Tracking

unspecified
mozilla19
All
Linux
Points:
---

Firefox Tracking Flags

(firefox18 fixed, firefox19 fixed)

Details

Attachments

(1 attachment)

(Reporter)

Description

6 years ago
Created attachment 669828 [details] [diff] [review]
/home/mrosenberg/patches/betterAnd-r0.patch

It threw an assertion stating that upper >= lower, and it looks like in general, taking the min of the two max-values is wrong.  For future things, I may switch the meaning of upper/lower for the results of bitand, since computing ranges with binary operations is non-trivial.
Attachment #669828 - Flags: review?(dvander)
Comment on attachment 669828 [details] [diff] [review]
/home/mrosenberg/patches/betterAnd-r0.patch

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

::: js/src/ion/RangeAnalysis.cpp
@@ +346,5 @@
>      // If both numbers can be negative, issues can be had.
>      if (lhs->lower_ < 0 && rhs->lower_ < 0)
>          lower = INT_MIN;
> +    int64_t upper = Max(lhs->upper_, rhs->upper_);
> +    //fprintf(stderr, "updating to: (%d, %d)\n", lower, upper);

r=me with this comment removed
Attachment #669828 - Flags: review?(dvander) → review+
This change seems unfortunate since it means you can't guarantee that "i & 3" is < 4 when i is unknown, which might be very useful for array bounds checks and stuff.

If either input to "and" is non-negative, then that input is an upper-bound for the result of "and". So if lhs->lower >= 0, lhs->upper is an upper bound, and likewise for rhs.

Also, if either input to "and" is non-negative, the output can't be negative, which is also useful to know. So if lhs->lower >= 0, you can set lower to 0, and likewise for rhs.
(Reporter)

Comment 3

6 years ago
Yeah, it is a surprisingly complex operation.  The way other engines deal with it is they have two separate mechanisms in place, one for "here be ranges" and one for "here be masks".  I may try doing that, or I may spend an hour in front of a whiteboard until I have an exact algorithm mapped out.
I bet it would even be a fun interview question :-p

Comment 4

6 years ago
https://hg.mozilla.org/mozilla-central/rev/e16d4075ad64
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla19
https://hg.mozilla.org/releases/mozilla-aurora/rev/edf686a532b7
status-firefox18: --- → fixed
status-firefox19: --- → fixed
You need to log in before you can comment on or make changes to this bug.