1131955 - Add collectRangeInfoPreTrunc to boundscheck

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: Patch

Comment 2

[Douglas Crosher [:dougc]]

This looks good to have. Fwiw the patch in bug 870743 folds away unnecessary bounds checks and removes them from the MIR.

Might it be better to just optimize this away in the MIR, rather than at lower to LIR?

Does having a bounds check in the MIR block code movement of the dependent access, even if it is proven to be within bounds?

I suspect the pipeline might need to be re-organised to allow range analysis before GVN as there are probably type dependant optimizations, such as removing bounds checks, that could usefully be done before GVN. It might also be usefully to run GVN multiple times.

Comment 3

[Hannes Verschore [:h4writer]]

(In reply to Douglas Crosher [:dougc] from comment #2)
> I suspect the pipeline might need to be re-organised to allow range analysis
> before GVN as there are probably type dependant optimizations, such as
> removing bounds checks, that could usefully be done before GVN. It might
> also be usefully to run GVN multiple times.

Just drive by before going into bed. So I haven't looked at the linked bug too closely. But fyi GVN runs also after range analysis. So it runs already multiple times ;).

Comment 4

[Douglas Crosher [:dougc]]

(In reply to Hannes Verschore [:h4writer] from comment #3)
> (In reply to Douglas Crosher [:dougc] from comment #2)
> > I suspect the pipeline might need to be re-organised to allow range analysis
> > before GVN as there are probably type dependant optimizations, such as
> > removing bounds checks, that could usefully be done before GVN. It might
> > also be usefully to run GVN multiple times.
> 
> Just drive by before going into bed. So I haven't looked at the linked bug
> too closely. But fyi GVN runs also after range analysis. So it runs already
> multiple times ;).

Thank you for the pointer, that is very helpful. I am exploring doing array access index offset dehoisting just after range analysis too and was worried it was too late and would miss GVN, but if there is another GVN pass then this makes it a very good point to place such transforms.

Comment 5

[Dan Gohman [:sunfish]]

Comment on attachment 8562628 [details] [diff] [review]
Patch

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

I agree with Douglas that there's more that we can do in this area. That said, this patch looks good for now, as it's simple and looks like it'll be effective, and it's just doing the same thing that we're already doing for MBoundsCheckLower.

There are a few things to fix up below though; let's do another review once those are fixed.

::: js/src/jit/RangeAnalysis.cpp
@@ +3175,5 @@
> +MBoundsCheck::collectRangeInfoPreTrunc()
> +{
> +    Range indexRange(index());
> +    Range lengthRange(length());
> +    if (!indexRange.hasInt32LowerBound() && !indexRange.hasInt32UpperBound())

|| instead of &&

@@ +3177,5 @@
> +    Range indexRange(index());
> +    Range lengthRange(length());
> +    if (!indexRange.hasInt32LowerBound() && !indexRange.hasInt32UpperBound())
> +        return;
> +    if (!lengthRange.hasInt32LowerBound() && !lengthRange.hasInt32UpperBound())

We don't need to check lengthRange.hasInt32UpperBound(), since all we care about here is the least possible value of the length.

@@ +3179,5 @@
> +    if (!indexRange.hasInt32LowerBound() && !indexRange.hasInt32UpperBound())
> +        return;
> +    if (!lengthRange.hasInt32LowerBound() && !lengthRange.hasInt32UpperBound())
> +        return;
> +    if (indexRange.lower() + minimum() >= 0 && indexRange.upper() + maximum() < lengthRange.lower())

There is an integer overflow hazard here. For example, if indexRange.upper() + maximum() overflows, it could produce a negative value which would erroneously satisfy < lengthRange.lower(). Can you add code to check for integer overflow here, or possibly fix this by using unsigned comparisons?

Comment 6

[Dan Gohman [:sunfish]]

(In reply to Douglas Crosher [:dougc] from comment #4)
> Thank you for the pointer, that is very helpful. I am exploring doing array
> access index offset dehoisting just after range analysis too and was worried
> it was too late and would miss GVN, but if there is another GVN pass then
> this makes it a very good point to place such transforms.

Note that that second GVN pass is currently only run when range analysis simplifies a branch; see RangeAnalysis::prepareForUCE for details ("UCE" and "RemoveDeadCode" are anachronisms here, as these functions are now performed by the GVN pass). However, that's just based on the assumption that there's presently no need to run it otherwise.

Comment 7

[Hannes Verschore [:h4writer]]

Attachment: Patch

Oh yeah. I neglected the int overflow. Now I think using unsigned didn't solve all issues and/or let it sometimes not optimize if it was possible. Also to keep the code easy readable and fix all issues at once, I used int64 arithmetic.

Comment 8

[Dan Gohman [:sunfish]]

Comment on attachment 8564064 [details] [diff] [review]
Patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ +3174,5 @@
> +    Range lengthRange(length());
> +    if (!indexRange.hasInt32LowerBound() || !indexRange.hasInt32UpperBound())
> +        return;
> +    if (!lengthRange.hasInt32LowerBound())
> +         return;

Style nit: 4-space indentation.

Also, is it possible for lengthRange to ever be NaN? I know I said it's not necessary to check the upper bound, but checking for || lengthRange.canBeNaN() might still be needed here.

Comment 9

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8564064 [details] [diff] [review]
Patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ +3183,5 @@
> +    int64_t min = minimum();
> +    int64_t max = maximum();
> +
> +    if (indexLower + min >= 0 && indexUpper + max < lengthLower)
> +        fallible_ = false;

Another way would be to remove the Guard flag and let DCE remove this instruction before the lowering.

Comment 10

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/30dadfc162c3

Comment 11

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/30dadfc162c3