Closed Bug 1301379 Opened 8 years ago Closed 1 month ago

Hoist bounds checks for strided array indices

Categories

(Core :: JavaScript Engine: JIT, defect, P5)

defect

Tracking

()

RESOLVED INCOMPLETE

People

(Reporter: sandervv, Unassigned)

Details

Attachments

(1 file)

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: 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.
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.
Assignee: sandervv → nobody
Severity: normal → S3
Status: NEW → RESOLVED
Closed: 1 month ago
Resolution: --- → INCOMPLETE
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: