Hoist bounds checks for strided array indices

NEW

Status

()

Core
JavaScript Engine: JIT
P5
normal
a year ago
a year ago

People

(Reporter: Sander Mathijs van Veen, Assigned: Sander Mathijs van Veen)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Assignee)

Description

a year ago
Created attachment 8789362 [details] [diff] [review]
hoist-bounds-checks-for-constant-step-and-shift-right-zero.patch

I've a work-in-progress patch (split in two parts) that hoist the bounds check for strided array indices. In the Bullet test case, points are represented using a vector of four doubles (x,y,z,w). Iterating over these doubles requires a fixed stride, and the computed index hinders hoisting the bounds checks.

The small test case extracted from Cheerp's Bullet test case:

(function(){
do {
    var Mpoints = 8;
    var LnumPoints = 1000;
    var Lpoints = new Float64Array(4 * LnumPoints + Mpoints);
    var tmp2=-1.0E+30;
    var idx=-1;
    var i=0;
    while(1){
        var tmp9=i<<2;
        var tmp10=+(Lpoints[(Mpoints>>0)+tmp9>>0]);
        var tmp11=+(Lpoints[(Mpoints>>0)+(tmp9+1>>0)>>0]);
        var tmp12=+(Lpoints[(Mpoints>>0)+(tmp9+2>>0)>>0]);
        var tmp13=tmp10+tmp11+tmp12;
        if(tmp13>tmp2){
            tmp2=tmp13;
            idx=i;
        }
        i=i+1>>0;
        if(!(i>>0<LnumPoints>>0)){
            break;
        }
    }
} while(!inIon());
})();

(Note that the 'w' component is not used, hence thread instead of four loads.)

I've attached the first part of the patch. This part allows hoisting bounds checks of array indices that increase with a constant step and have a shift right zero. For example:

      for (var i = 0; i < 10; i++) {
          tmp10=+(Lpoints[i>>0]);
      }

I've added a utility function that returns true when a node is a shift right zero (no-op that is used as a type hint in javascript). This patch does also allow hoisting bounds checks for array accesses that have a loop step that's larger than one.
(Assignee)

Updated

a year ago
Assignee: nobody → sandervv
I will try to find proper time to review all the consequences of adding Rsh as part of LinearSum, as Rsh is not a linear operation, it wraps-around its inputs to the int32 range.

This technically imply that we would have to be careful that bounds of the operands are always within the wrap-around range, to ensure that such binary operations are no-ops.
(Assignee)

Comment 2

a year ago
Can you take another look at the shift right zero utility function and/or the whole patch?
Flags: needinfo?(nicolas.b.pierron)
Priority: -- → P5
(In reply to Nicolas B. Pierron [:nbp] from comment #1)
> I will try to find proper time to review all the consequences of adding Rsh
> as part of LinearSum, as Rsh is not a linear operation, it wraps-around its
> inputs to the int32 range.
> 
> This technically imply that we would have to be careful that bounds of the
> operands are always within the wrap-around range, to ensure that such binary
> operations are no-ops.

Sorry for the delay, but I think that history proved me right to have such concerns.
Have a look at Bug 1319242, and rebase this patch accordingly.
Flags: needinfo?(nicolas.b.pierron)
Comment on attachment 8789362 [details] [diff] [review]
hoist-bounds-checks-for-constant-step-and-shift-right-zero.patch

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

::: js/src/jit/IonAnalysis.cpp
@@ +3046,5 @@
>          return SimpleLinearSum(nullptr, ins->toConstant()->toInt32());
>  
> +    // Shift right with zero does not change the sum.
> +    if (IsRightShiftZero(ins))
> +        return ExtractLinearSum(ins->getOperand(0));

I disargree a right shift by zero does change the sum as this is a bitwise instruction, as this means that operations before it are in the Modulo 2³² space, while its uses are in an Infinite integer space.  Have a look at the test case from attachment 8813303 [details] [diff] [review].

When the truncated input overflow in the Modulo 2³² space, we wrap it around, and moving it out-side the Modulo 2³² space changes the result.  This should not affect asm.js-like code as all operations are truncated by default, but this could cause differential behaviour on ordinary JS code.
You need to log in before you can comment on or make changes to this bug.