897337 - Odinmonkey: support the use of a high bit mask as an alternative to bounds checking for heap safety

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Douglas Crosher [:dougc]]

The asm.js syntax currently uses bound checking on heap access to ensure code safety.  Hoisting these checks is problematic.  An alternative is to use high bit masking, for example HEAP32[a>>2&4095] and this bug aims to add basic support for this.

The masking operation is generally simpler to hoist, and explicitly hoisted masking along with compiler type propagation could eliminate many bounds checks and redundant masking.

It is suggested that this be an extension to the asm.js syntax and that code be free to mix the use of high bit masking heap access with the current style using uses bounds checks - if the compiler can not prove that an index mask makes a heap access safe then it just emits a bounds check.  Further it is suggested that code be free to mix different mask values.  It is suggested that for now at least the mask be limited to be 2^n-1.  Further if support is added for constant variable then it is suggested that these be accepted for the mask, rather than just a literal number, see bug 880204.

The asm.js syntax does not allow a heap size to be specified at compile time, and this is needed in order to be able to prove that a mask would yield safe heap access, so the asm.js spec. would need to ensure that any heap access high bit mask also defines a minimum heap size, allowing the compiler to optimize away the bounds check.

Note the compiler will often be able to combine a high bit mask with a low bit alignment mask.  This is a short, one instruction, operation on the ARM.

In relation to other technology, note that NaCl demands code use high bit masking in order to prove it is safe.  Asm.js has an opportunity to hoist or eliminate such masking.

Comment 1

[lwagner]

Glad to see you filing a bug on this!

Do you have the measurements for the speedup on ARM (it'd also be nice to see the upper bound on how much mask hoisting could speedup up ARM by just removing all the masks)?

Another important step is to have Emscripten provide an option for generating masks.

Comment 2

[Douglas Crosher [:dougc]]

Should a config preference be added to keep this disabled for now?

Comment 3

[Luke Wagner [:luke]]

IIUC, this change shouldn't cause anything to fail to validate so I don't see any need for a pref.

Comment 4

[Douglas Crosher [:dougc]]

With the decision made in bug 865516, in particular the decision to limit
the syntax that can cause a heap length restriction, asm.js code will want
to use an unshifted literal constant heap reference near the start of the
code to effectively declare the minimum heap size.  With the minimum heap
length already declared, there is no longer a need for the new syntax being
considered in this bug.

With the patch in bug 865516 alone, code can use masking to avoid a
bounds check using e.g. u8[i&m] or u32[i&m>>2] etc.  Simple type
propagation in the range analysis stage is adequate to flag the
bounds check as unnecessary given that the minimum heap length
is declared.

There are many advantages to avoiding adding new syntax.  Code using heap
masks rather than bounds checks will still be valid asm.js and will be
backwards compatible, although a little slower when run on an asm.js
compiler not capable of propagating the mask type information and using
it to avoid the bounds check.

Avoiding the need for the masking syntax to add a heap length restriction
also avoids the problem of defining syntax that masks but does not add
such a restriction.

The access can be optimized even without range analysis by handling
some common patterns while converting to MIR, in CheckArrayAccess.

If the minimum heap length restriction is not well defined when a
masking access pattern is encountered then the compiler will simply
fall back to emitting a bounds check.