Closed Bug 1131955 Opened 5 years ago Closed 5 years ago

Add collectRangeInfoPreTrunc to boundscheck

Categories

(Core :: JavaScript Engine: JIT, defect)

x86_64
Linux
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla39
Tracking Status
firefox39 --- fixed

People

(Reporter: h4writer, Assigned: h4writer)

Details

Attachments

(1 file, 1 obsolete file)

No description provided.
Attached patch Patch (obsolete) — Splinter Review
Assignee: nobody → hv1989
Attachment #8562628 - Flags: review?(sunfish)
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.
(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 ;).
(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 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?
Attachment #8562628 - Flags: review?(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.
Attached patch PatchSplinter Review
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.
Attachment #8562628 - Attachment is obsolete: true
Attachment #8564064 - Flags: review?(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.
Attachment #8564064 - Flags: review?(sunfish) → review+
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.
https://hg.mozilla.org/mozilla-central/rev/30dadfc162c3
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla39
You need to log in before you can comment on or make changes to this bug.