Closed Bug 897337 Opened 8 years ago Closed 8 years ago
Odinmonkey: support the use of a high bit mask as an alternative to bounds checking for heap safety
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.
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.
Should a config preference be added to keep this disabled for now?
IIUC, this change shouldn't cause anything to fail to validate so I don't see any need for a pref.
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.
Status: NEW → RESOLVED
Closed: 8 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.