1282618 - WASM: Implement a simple redundant bounds check elimination pass

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement, P2)

Description

[[e-mail]]

Implement a pass that eliminates redundant WasmBoundsChecks. We define a check C(addr) as redundant, if there is another check C1 for that same address that strictly dominates the current check. 

Some early experiments suggests that this occurs a non-trivial amount of times both statically and dynamically. For example, for angry bots we measured a ~30-40% reduction in the number of both static and dynamic bounds checks.

Comment 1

[[e-mail]]

Attachment: Preliminary patch for simple bce

This patch depends on any changes to Benjamin's patch.
Should be noted, that the arm64/mips part are missing here.

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8767363 [details] [diff] [review]
Preliminary patch for simple bce

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

Here is a first pass of comments; there are mostly style nits and recommendations for more idiomatic code, plus a few questions about the validity of marking some checks as redundant. So how does this perform compared to the GVN pass (which might remove a lot of similar checks by calling congruentTo and keeping only one check per equivalency class)?

::: js/src/jit/Ion.cpp
@@ +56,5 @@
>  #include "jit/shared/Lowering-shared-inl.h"
>  #include "vm/Debugger-inl.h"
>  #include "vm/ScopeObject-inl.h"
>  #include "vm/Stack-inl.h"
> +#include "jit/WasmBCE.h"

Spidermonkey has some strict rules for the ordering of includes; generally speaking, they need to be alphabetically ordered. You can check your ordering is good or wrong by using |make check-style| from your build dir and you should expect to see "TEST-PASS".

@@ +1873,5 @@
>      }
>  
> +    if (mir->compilingAsmJS()) {
> +      if (!bce_simple(mir, graph, GetJitContext()->cx))
> +        return false;

You might want to have a look at our style guidelines: https://wiki.mozilla.org/JavaScript:SpiderMonkey:Coding_Style
For instance, we use 4-spaces indentation (if you use emacs or vi/vim/nvim, the modeline at the top should make it easy to refactor your code by using the editor's shortcuts to automatically fix indent).

More related to the code:
- you can add an intermediary pass in the iongraph by calling gs.spewPass here
- asserting that the graph is coherent after an optimization sounds rather safe

Also, what is your thinking behind putting this optimization here? (that is, after all of the others.) As some optimizations may have some effect on others, it could be useful to think about the implications here. It makes sense to me to put this one after GVN, as GVN can probably remove already redundant bounds checks.

@@ +1876,5 @@
> +      if (!bce_simple(mir, graph, GetJitContext()->cx))
> +        return false;
> +    }
> +
> +

nit: blank line

::: js/src/jit/WasmBCE.cpp
@@ +3,5 @@
> +using namespace js;
> +using namespace js::jit;
> +using namespace js::wasm;
> +
> +typedef js::HashMap<uint32_t, MBasicBlock*> LastCheckMT;

If you specify a SystemAllocPolicy (that might be the 4th template parameter), then I think you don't need the ctx at all in the bce_simple function.

@@ +4,5 @@
> +using namespace js::jit;
> +using namespace js::wasm;
> +
> +typedef js::HashMap<uint32_t, MBasicBlock*> LastCheckMT;
> +// The Simple Wasm Bounds Check Elimination (BCE) pass looks for bounds checks

nit: space before multi lines comment

@@ +9,5 @@
> +// on SSA values that have already been checked. (in the same block or in a
> +// dominating block). These bounds checks are redundant and thus eliminated.
> +//
> +// Note: This is safe in the presense of dynamic memory sizes as long as they can
> +// ONLY GROW. If we allow SHRINKING the heap, this pass should be RECONSIDERED.

I think shrinking the heap is allowed, so that's an interesting matter to think about.

Brain-dumping my thoughts here:
- retrigger compilation in the case where we shrink the heap; that sounds very unfortunate and bad for performance. I seem to recall that some emscripten users create a big heap and then shrink it to its optimal size.
- forbid shrinking when this pass is enabled (seems bad too).
- skip this pass if there are any grow_memory opcodes in the initial wasm graph. That would be a nice workaround, but compilation is per-function, and any function in the module can have this opcode, so this actually doesn't seem doable.
- always generate enough NOPs before a bounds check, so that we can patch at runtime the generated code and toggle the NOPs to jumps over the comparison?

@@ +15,5 @@
> +// TODO (dbounov): Are there a lot of cases where there is no single dominating check,
> +// but a set of checks that toghether dominate a redundant check?
> +//
> +// TODO (dbounov): Generalize to constant additions relative to one base
> +bool wasm::bce_simple(MIRGenerator* mir, MIRGraph& graph, ExclusiveContext *ctx) {

nit: ExclusiveContext* ctx

@@ +23,5 @@
> +      return false;
> +
> +    for (ReversePostorderIterator iter(graph.rpoBegin()); iter != graph.rpoEnd(); iter++) {
> +        MBasicBlock* block = *iter;
> +        for (MDefinitionIterator iter(block); iter;) {

Maybe can give another name to the inner "iter", to not confuse it with the outer one?

@@ +29,5 @@
> +            MDefinition *addr = nullptr;
> +            MWasmBoundsCheck *bc;
> +            LastCheckMT::Ptr checkPtr;
> +            MPhi *phi;
> +            bool phiChecked;

Most of these definitions can go under the switch case blocks directly, if you add braces there.

@@ +33,5 @@
> +            bool phiChecked;
> +
> +            switch (def->op()) {
> +              case MDefinition::Op_WasmBoundsCheck:
> +                bc = (MWasmBoundsCheck*)def;

bc = def->toWasmBoundsCheck();

@@ +38,5 @@
> +                addr = def->getOperand(0);
> +                checkPtr = checkM.lookup(addr->id());
> +
> +                if (checkPtr && checkPtr->value()->dominates(block)) {
> +                  // Address already checked. Discard current check

What if the offset is different? or the type of the memory access? (if a dominating check relates to an int8 access, then marking a dominated check for a int32 access is incorrect)

@@ +41,5 @@
> +                if (checkPtr && checkPtr->value()->dominates(block)) {
> +                  // Address already checked. Discard current check
> +                  bc->setRedundant(true);
> +                } else {
> +                  // Address not previously checked - remember current check 

nit: trailing space here

@@ +53,5 @@
> +                phiChecked = true;
> +
> +                // If all incoming values to a phi node are safe (i.e. have a
> +                // check that dominates this block) then we can consider this
> +                // phi node checked.

This won't handle phi cycles at all, right?

@@ +68,5 @@
> +                if (phiChecked) {
> +                  if (!checkM.put(def->id(), block))
> +                    return false;
> +                }
> +                   

nit: and trailing space here

::: js/src/jit/WasmBCE.h
@@ +23,5 @@
> +#include "jit/MIRGraph.h"
> +
> +using namespace js;
> +using namespace js::jit;
> +using namespace js::wasm;

We generally don't put |using namespace| in header files, since they might be propagated to all the files including this header, provoking subtle naming chaos.

@@ +28,5 @@
> +
> +namespace js {
> +namespace wasm {
> +
> +bool bce_simple(MIRGenerator* mir, MIRGraph& graph, ExclusiveContext *ctx);

nit: ExclusiveContext*

Also, let's use camelCase here and start the function's name with a capital. I'd like a more descriptive name so that readers of the call in Ion.cpp understand quickly what it does, how about EliminateBoundsChecks?

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +2317,5 @@
> +#ifndef DEBUG
> +    if (mir->isUnreachable())
> +      return;
> +#else
> +    // In debug emit all bounds check, even redundant ones.

Same comments as in CodeGenerator-x86.cpp.

::: js/src/jit/x64/CodeGenerator-x64.cpp
@@ +753,5 @@
> +CodeGeneratorX64::visitWasmBoundsCheck(LWasmBoundsCheck* ins)
> +{
> +#ifdef DEBUG
> +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> +    // BCE passes.

It'd be nice if this could be a runtime option, otherwise debug and non-debug builds will have very different behavior (and bugs related to signal handling will occur only on non-debug builds, which will be hard to debug :-))

::: js/src/jit/x86/CodeGenerator-x86.cpp
@@ +404,5 @@
>          return;
>      }
>  
> +#ifndef DEBUG
> +    if (mir->isUnreachable())

Where is isUnreachable defined? (former name for "isRedundant"?)

@@ +407,5 @@
> +#ifndef DEBUG
> +    if (mir->isUnreachable())
> +      return;
> +#else
> +    // In debug emit all bounds check, even redundant ones.

I'd remove the empty #else branch here, while keeping the comment.

@@ +417,5 @@
> +    if (mir->isUnreachable()) {
> +      // If emitting a redundant check (for fuzzing), fail hard.
> +      Label ok;
> +      masm.j(Assembler::BelowOrEqual, &ok);
> +      masm.assumeUnreachable("Unexpected redundant branch check fail"); 

nit: trailing spaces (for what it's worth, you can see them in read when doing a review of your own code in bugzilla)

Comment 3

[Luke Wagner [:luke]]

Comment on attachment 8767363 [details] [diff] [review]
Preliminary patch for simple bce

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

Looks like you're off to a good start!  Clearing review for now since bbouvier has a lot of good comments.  For subsequent iterations, you can flag bbouvier/sunfish for review.

::: js/src/jit/WasmBCE.cpp
@@ +9,5 @@
> +// on SSA values that have already been checked. (in the same block or in a
> +// dominating block). These bounds checks are redundant and thus eliminated.
> +//
> +// Note: This is safe in the presense of dynamic memory sizes as long as they can
> +// ONLY GROW. If we allow SHRINKING the heap, this pass should be RECONSIDERED.

Related question: I think this is valid so long as bounds checks are not being moved at all.  Once they can be moved, you need calls/grow_memory to prevent movement (since otherwise you could be faulting when memory is small whereas the load would've succeeded when memory was big).  But this patch isn't doing that, iiuc, so probably it'd be good to mention this.

Comment 4

[[e-mail]]

Attachment: BCE Patch post BBouvier review #1

Patch post Benjamin's first review. Most of the stylistic/nit things were fixed. Here are Benjamin's remaining comments that I have not addressed yet completely:

> validity of marking some checks as redundant. So how does this perform
> compared to the GVN pass (which might remove a lot of similar checks by
> calling congruentTo and keeping only one check per equivalency class)?
> 

I am not sure if GVN does remove any checks today. Specifically, since MWasmBoundsChecks sets flags signifying its effectful, wouldn't GVN leave it alone?

Also the shape of MWasmBoundsCheck makes it a little a-typical for GVN. Specifically its return value is not used anywhere. If we changed MWasmBonudsCheck to return a "checked" version of the address, that is later used in the load/store, than perhaps this would be closer to GVN?

Another reason to keep this separate from GVN, is that this pass will probably grow to be more complex when it becomes aware of constant offsets (not all of which are folded inside the MWasmBoundsCheck).

> 
> Also, what is your thinking behind putting this optimization here? (that is,
> after all of the others.) As some optimizations may have some effect on
> others, it could be useful to think about the implications here. It makes
> sense to me to put this one after GVN, as GVN can probably remove already
> redundant bounds checks.

I don't know enough about the other passes. I put it as the last pass by inertia. I am open to suggestions about better places to put it :)

> 
> @@ +9,5 @@
> > +// on SSA values that have already been checked. (in the same block or in a
> > +// dominating block). These bounds checks are redundant and thus eliminated.
> > +//
> > +// Note: This is safe in the presense of dynamic memory sizes as long as they can
> > +// ONLY GROW. If we allow SHRINKING the heap, this pass should be RECONSIDERED.
> 
> I think shrinking the heap is allowed, so that's an interesting matter to
> think about.
>

As far as I understood from Dan/Luke, for now shrinking is not allowed due to the problems it would cause multithreading. Or thats what I thought? 

Luke pointed out that another thing missing here is the fact that the grow operation is a "barrier" for hoisting bounds checks. (TODO: Put a reminder comment for it)


> @@ +38,5 @@
> > +                addr = def->getOperand(0);
> > +                checkPtr = checkM.lookup(addr->id());
> > +
> > +                if (checkPtr && checkPtr->value()->dominates(block)) {
> > +                  // Address already checked. Discard current check
> 
> What if the offset is different? or the type of the memory access? (if a
> dominating check relates to an int8 access, then marking a dominated check
> for a int32 access is incorrect)

This was a bug in my implementation. Please see EliminateBoundsCheck for my proposed fixed handling of this. I re-ran my benchmarks with this fix, and noted a 5% decrease in the static bounds check reduction, and 3% decrease in the dynamic bounds check reduction on angrybots.


> @@ +53,5 @@
> > +                phiChecked = true;
> > +
> > +                // If all incoming values to a phi node are safe (i.e. have a
> > +                // check that dominates this block) then we can consider this
> > +                // phi node checked.
> 
> This won't handle phi cycles at all, right?
> 

Correct. On phi cycles we are guaranteed that the incoming back edge into the phi will not be in
the safe set, since it hasn't been traversed yet (due to rpo). So no phi that in a cycle can be considered 
safe. I added a comment for this.

> ::: js/src/jit/x64/CodeGenerator-x64.cpp
> @@ +753,5 @@
> > +CodeGeneratorX64::visitWasmBoundsCheck(LWasmBoundsCheck* ins)
> > +{
> > +#ifdef DEBUG
> > +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> > +    // BCE passes.
> 
> It'd be nice if this could be a runtime option, otherwise debug and
> non-debug builds will have very different behavior (and bugs related to
> signal handling will occur only on non-debug builds, which will be hard to
> debug :-))
> 

I think Dan/Luke mentioned to do it this way, to allow all existing asmjs test to also exercise BCE. I can change it, no strong preference. Just wanted everyone to confirm.

> ::: js/src/jit/x86/CodeGenerator-x86.cpp
> @@ +404,5 @@
> >          return;
> >      }
> >  
> > +#ifndef DEBUG
> > +    if (mir->isUnreachable())
> 
> Where is isUnreachable defined? (former name for "isRedundant"?)
> 

Fixed. This is a bug just in the patch I submitted - not in the code I tested on.

Comment 5

[[e-mail]]

Actually ignore this for now. Stupid bug found :(

(In reply to dbounov from comment #4)
> Created attachment 8768489 [details] [diff] [review]
> BCE Patch post BBouvier review #1
> 
> Patch post Benjamin's first review. Most of the stylistic/nit things were
> fixed. Here are Benjamin's remaining comments that I have not addressed yet
> completely:
> 
> > validity of marking some checks as redundant. So how does this perform
> > compared to the GVN pass (which might remove a lot of similar checks by
> > calling congruentTo and keeping only one check per equivalency class)?
> > 
> 
> I am not sure if GVN does remove any checks today. Specifically, since
> MWasmBoundsChecks sets flags signifying its effectful, wouldn't GVN leave it
> alone?
> 
> Also the shape of MWasmBoundsCheck makes it a little a-typical for GVN.
> Specifically its return value is not used anywhere. If we changed
> MWasmBonudsCheck to return a "checked" version of the address, that is later
> used in the load/store, than perhaps this would be closer to GVN?
> 
> Another reason to keep this separate from GVN, is that this pass will
> probably grow to be more complex when it becomes aware of constant offsets
> (not all of which are folded inside the MWasmBoundsCheck).
> 
> > 
> > Also, what is your thinking behind putting this optimization here? (that is,
> > after all of the others.) As some optimizations may have some effect on
> > others, it could be useful to think about the implications here. It makes
> > sense to me to put this one after GVN, as GVN can probably remove already
> > redundant bounds checks.
> 
> I don't know enough about the other passes. I put it as the last pass by
> inertia. I am open to suggestions about better places to put it :)
> 
> > 
> > @@ +9,5 @@
> > > +// on SSA values that have already been checked. (in the same block or in a
> > > +// dominating block). These bounds checks are redundant and thus eliminated.
> > > +//
> > > +// Note: This is safe in the presense of dynamic memory sizes as long as they can
> > > +// ONLY GROW. If we allow SHRINKING the heap, this pass should be RECONSIDERED.
> > 
> > I think shrinking the heap is allowed, so that's an interesting matter to
> > think about.
> >
> 
> As far as I understood from Dan/Luke, for now shrinking is not allowed due
> to the problems it would cause multithreading. Or thats what I thought? 
> 
> Luke pointed out that another thing missing here is the fact that the grow
> operation is a "barrier" for hoisting bounds checks. (TODO: Put a reminder
> comment for it)
> 
> 
> > @@ +38,5 @@
> > > +                addr = def->getOperand(0);
> > > +                checkPtr = checkM.lookup(addr->id());
> > > +
> > > +                if (checkPtr && checkPtr->value()->dominates(block)) {
> > > +                  // Address already checked. Discard current check
> > 
> > What if the offset is different? or the type of the memory access? (if a
> > dominating check relates to an int8 access, then marking a dominated check
> > for a int32 access is incorrect)
> 
> This was a bug in my implementation. Please see EliminateBoundsCheck for my
> proposed fixed handling of this. I re-ran my benchmarks with this fix, and
> noted a 5% decrease in the static bounds check reduction, and 3% decrease in
> the dynamic bounds check reduction on angrybots.
> 
> 
> > @@ +53,5 @@
> > > +                phiChecked = true;
> > > +
> > > +                // If all incoming values to a phi node are safe (i.e. have a
> > > +                // check that dominates this block) then we can consider this
> > > +                // phi node checked.
> > 
> > This won't handle phi cycles at all, right?
> > 
> 
> Correct. On phi cycles we are guaranteed that the incoming back edge into
> the phi will not be in
> the safe set, since it hasn't been traversed yet (due to rpo). So no phi
> that in a cycle can be considered 
> safe. I added a comment for this.
> 
> > ::: js/src/jit/x64/CodeGenerator-x64.cpp
> > @@ +753,5 @@
> > > +CodeGeneratorX64::visitWasmBoundsCheck(LWasmBoundsCheck* ins)
> > > +{
> > > +#ifdef DEBUG
> > > +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> > > +    // BCE passes.
> > 
> > It'd be nice if this could be a runtime option, otherwise debug and
> > non-debug builds will have very different behavior (and bugs related to
> > signal handling will occur only on non-debug builds, which will be hard to
> > debug :-))
> > 
> 
> I think Dan/Luke mentioned to do it this way, to allow all existing asmjs
> test to also exercise BCE. I can change it, no strong preference. Just
> wanted everyone to confirm.
> 
> > ::: js/src/jit/x86/CodeGenerator-x86.cpp
> > @@ +404,5 @@
> > >          return;
> > >      }
> > >  
> > > +#ifndef DEBUG
> > > +    if (mir->isUnreachable())
> > 
> > Where is isUnreachable defined? (former name for "isRedundant"?)
> > 
> 
> Fixed. This is a bug just in the patch I submitted - not in the code I
> tested on.

Comment 6

[[e-mail]]

Attachment: bce patch after bbouvier's feedback

BCE Patch post BBouvier review #1

Patch post Benjamin's first review. Most of the stylistic/nit things were fixed. Here are Benjamin's remaining comments that I have not addressed yet completely:

> validity of marking some checks as redundant. So how does this perform
> compared to the GVN pass (which might remove a lot of similar checks by
> calling congruentTo and keeping only one check per equivalency class)?
> 

I am not sure if GVN removes any checks today. Specifically, since MWasmBoundsChecks sets flags signifying its effectful (setGuard), wouldn't GVN leave it alone?

Another reason to keep this separate from GVN, is that this pass will probably grow to be more complex when it becomes aware of constant offsets off of common bases (not all of which are folded inside the MWasmBoundsCheck).

Finally the shape of MWasmBoundsCheck makes it a little a-typical for GVN. Specifically its return value is not used anywhere, and its argument is used unchanged downstream from the check.

If we wanted to eliminate bounds check using GVN would it make more sense to change MWasmBoundsChecks to return a "checked" version of the address, that gets used later on? Currently MWasmBoundsChecks from the point of view of GVN look like dead instructions (their return value is not used), that are kept around because they are marked as effectful right?

> 
> Also, what is your thinking behind putting this optimization here? (that is,
> after all of the others.) As some optimizations may have some effect on
> others, it could be useful to think about the implications here. It makes
> sense to me to put this one after GVN, as GVN can probably remove already
> redundant bounds checks.

I don't know enough about the other passes. I put it as the last pass by inertia. I am open to suggestions about better places to put it :)

> 
> @@ +9,5 @@
> > +// on SSA values that have already been checked. (in the same block or in a
> > +// dominating block). These bounds checks are redundant and thus eliminated.
> > +//
> > +// Note: This is safe in the presense of dynamic memory sizes as long as they can
> > +// ONLY GROW. If we allow SHRINKING the heap, this pass should be RECONSIDERED.
> 
> I think shrinking the heap is allowed, so that's an interesting matter to
> think about.
>

As far as I understood from Dan/Luke, for now shrinking is not allowed due to the problems it would cause multithreading.I could be wrong? 

Luke pointed out that another thing missing here is the fact that the grow operation is a "barrier" for hoisting bounds checks. (TODO: Put a reminder comment for it)


> @@ +38,5 @@
> > +                addr = def->getOperand(0);
> > +                checkPtr = checkM.lookup(addr->id());
> > +
> > +                if (checkPtr && checkPtr->value()->dominates(block)) {
> > +                  // Address already checked. Discard current check
> 
> What if the offset is different? or the type of the memory access? (if a
> dominating check relates to an int8 access, then marking a dominated check
> for a int32 access is incorrect)

This was a bug in my implementation. Please see EliminateBoundsCheck for my proposed fixed handling of this. I re-ran my benchmarks with this fix, and noted a a significant decrease in the dynamic bounds check reduction on angrybots. Static # of bound checks reduction fell to 10% (from 35%) and dynamic bound check reduction fell to 9% (from 33-40%). Working on ways to fix this.


> @@ +53,5 @@
> > +                phiChecked = true;
> > +
> > +                // If all incoming values to a phi node are safe (i.e. have a
> > +                // check that dominates this block) then we can consider this
> > +                // phi node checked.
> 
> This won't handle phi cycles at all, right?
> 

Correct. On phi cycles we are guaranteed that the incoming back edge into the phi will not be in
the safe set, since it hasn't been traversed yet (due to rpo). So no phi that in a cycle can be considered 
safe. I added a comment for this.

I think phi cycles are follow up work as they are slightly more complicated.

> ::: js/src/jit/x64/CodeGenerator-x64.cpp
> @@ +753,5 @@
> > +CodeGeneratorX64::visitWasmBoundsCheck(LWasmBoundsCheck* ins)
> > +{
> > +#ifdef DEBUG
> > +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> > +    // BCE passes.
> 
> It'd be nice if this could be a runtime option, otherwise debug and
> non-debug builds will have very different behavior (and bugs related to
> signal handling will occur only on non-debug builds, which will be hard to
> debug :-))
> 

I think I did it this way, to allow all existing asmjs tests to also exercise BCE. I can change it, no strong preference. Just wanted everyone to confirm.

Comment 7

[Dan Gohman [:sunfish]]

Comment on attachment 8768585 [details] [diff] [review]
bce patch after bbouvier's feedback

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

Looks like a good first step!

::: js/src/jit/MIR.h
@@ +14316,5 @@
>      {
>          setMovable();
>          setGuard(); // Effectful: throws for OOB.
>          setResultType(MIRType::Int32);
> +        redundant_ = false;

Style nit: it's customary in this codebase to use constructor initializers for private fields, as `redundant_(false)` above.

::: js/src/jit/WasmBCE.cpp
@@ +13,5 @@
> +
> +typedef struct DefAndOffset {
> +    MDefinition *loc;
> +    uint32_t endOffset;
> +} DefAndOffsetT;

In C++, the typedef is unnecessary; we can just do "struct DefAndOffset { ... };".

@@ +40,5 @@
> +    for (ReversePostorderIterator bIter(graph.rpoBegin()); bIter != graph.rpoEnd(); bIter++) {
> +        MBasicBlock* block = *bIter;
> +        for (MDefinitionIterator dIter(block); dIter;) {
> +            MDefinition* def = *dIter++;
> +            LastCheckMT::Ptr checkPtr;

Style nit: I'd suggest declaring checkPtr at the points below where it's initialized.

@@ +58,5 @@
> +                    } else {
> +                        // Address not previously checked - remember current check
> +                        if (!checkM.put(addr->id(), (DefAndOffsetT) { def, bc->endOffset() })) {
> +                            return false;
> +                        }

Style nit: omit the braces for single-line if bodies.

@@ +89,5 @@
> +                            off = std::min(off, checkPtr->value().endOffset);
> +                        }
> +                    }
> +
> +                    MOZ_ASSERT(!phiChecked || off < UINT32_MAX);

It looks like it might be possible to trip this assert spuriously, since a wasm offfset could be as great as UINT32_MAX. A separate DebugOnly<bool> variable that records of any offsets were seen would be one way to allow this assert to be written.

Comment 8

[[e-mail]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=4a66f0937c51

Comment 9

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8768585 [details] [diff] [review]
bce patch after bbouvier's feedback

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

::: js/src/jit/x64/CodeGenerator-x64.cpp
@@ +755,5 @@
> +#ifdef DEBUG
> +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> +    // BCE passes.
> +    const MWasmBoundsCheck* mir = ins->mir();
> +    if (mir->isRedundant()) {

Sorry for insisting about this, but this creates a real testing bias if we do so on x64:
- in debug mode, OOB would be caught by this explicit check, not by signal handlers. So basically, signal handlers OOB would not be exerced in x64 debug mode.
- in release, we only rely on signal handling. If e.g. we change the code such that there's a MOZ_CRASH happening in a signal handler, then to debug it properly (that is, in DEBUG mode), we'd need to edit this function and remove all its content.

In a nutshell, signal handlers would only be tested in optimized non-debug builds, which sounds quite bad to me in terms of test coverage. In an ideal world, debug/non-debug should have the ability to exerce both modes: with signal handlers/with explicit bounds checks, so we'd have a perfect 2x2 testing matrix.

We could add a bool in the runtime to know whether to emit explicit bounds checks. An easy way would be to put it in JitRuntime and implement setters to be able to trigger it at runtime. How does that sound?

first register the option: http://searchfox.org/mozilla-central/source/js/src/jsapi.h#5555
implement setter: http://searchfox.org/mozilla-central/source/js/src/jsapi.cpp#6122
example of use in C++ code: http://searchfox.org/mozilla-central/source/js/src/asmjs/WasmStubs.cpp#487
example of use in a test case: http://searchfox.org/mozilla-central/source/js/src/jit-test/tests/wasm/basic-const.js#34

Comment 10

[[e-mail]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #9)
> Comment on attachment 8768585 [details] [diff] [review]
> bce patch after bbouvier's feedback
> 
> Review of attachment 8768585 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/x64/CodeGenerator-x64.cpp
> @@ +755,5 @@
> > +#ifdef DEBUG
> > +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> > +    // BCE passes.
> > +    const MWasmBoundsCheck* mir = ins->mir();
> > +    if (mir->isRedundant()) {
> 
> Sorry for insisting about this, but this creates a real testing bias if we
> do so on x64:
> - in debug mode, OOB would be caught by this explicit check, not by signal
> handlers. So basically, signal handlers OOB would not be exerced in x64
> debug mode.
> - in release, we only rely on signal handling. If e.g. we change the code
> such that there's a MOZ_CRASH happening in a signal handler, then to debug
> it properly (that is, in DEBUG mode), we'd need to edit this function and
> remove all its content.
> 
> In a nutshell, signal handlers would only be tested in optimized non-debug
> builds, which sounds quite bad to me in terms of test coverage. In an ideal
> world, debug/non-debug should have the ability to exerce both modes: with
> signal handlers/with explicit bounds checks, so we'd have a perfect 2x2
> testing matrix.
> 
> We could add a bool in the runtime to know whether to emit explicit bounds
> checks. An easy way would be to put it in JitRuntime and implement setters
> to be able to trigger it at runtime. How does that sound?
> 
> first register the option:
> http://searchfox.org/mozilla-central/source/js/src/jsapi.h#5555
> implement setter:
> http://searchfox.org/mozilla-central/source/js/src/jsapi.cpp#6122
> example of use in C++ code:
> http://searchfox.org/mozilla-central/source/js/src/asmjs/WasmStubs.cpp#487
> example of use in a test case:
> http://searchfox.org/mozilla-central/source/js/src/jit-test/tests/wasm/basic-
> const.js#34

Makes perfect sense. Will fix this, and Dan's comments and re-submit the patch.

Thank you!

Comment 11

[[e-mail]]

(In reply to dbounov from comment #10)
> (In reply to Benjamin Bouvier [:bbouvier] from comment #9)
> > Comment on attachment 8768585 [details] [diff] [review]
> > bce patch after bbouvier's feedback
> > 
> > Review of attachment 8768585 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > ::: js/src/jit/x64/CodeGenerator-x64.cpp
> > @@ +755,5 @@
> > > +#ifdef DEBUG
> > > +    // On X64 LWasmBoundsChecks are emitted only for fuzzing of the
> > > +    // BCE passes.
> > > +    const MWasmBoundsCheck* mir = ins->mir();
> > > +    if (mir->isRedundant()) {
> > 
> > Sorry for insisting about this, but this creates a real testing bias if we
> > do so on x64:
> > - in debug mode, OOB would be caught by this explicit check, not by signal
> > handlers. So basically, signal handlers OOB would not be exerced in x64
> > debug mode.
> > - in release, we only rely on signal handling. If e.g. we change the code
> > such that there's a MOZ_CRASH happening in a signal handler, then to debug
> > it properly (that is, in DEBUG mode), we'd need to edit this function and
> > remove all its content.
> > 
> > In a nutshell, signal handlers would only be tested in optimized non-debug
> > builds, which sounds quite bad to me in terms of test coverage. In an ideal
> > world, debug/non-debug should have the ability to exerce both modes: with
> > signal handlers/with explicit bounds checks, so we'd have a perfect 2x2
> > testing matrix.
> > 
> > We could add a bool in the runtime to know whether to emit explicit bounds
> > checks. An easy way would be to put it in JitRuntime and implement setters
> > to be able to trigger it at runtime. How does that sound?
> > 
> > first register the option:
> > http://searchfox.org/mozilla-central/source/js/src/jsapi.h#5555
> > implement setter:
> > http://searchfox.org/mozilla-central/source/js/src/jsapi.cpp#6122
> > example of use in C++ code:
> > http://searchfox.org/mozilla-central/source/js/src/asmjs/WasmStubs.cpp#487
> > example of use in a test case:
> > http://searchfox.org/mozilla-central/source/js/src/jit-test/tests/wasm/basic-
> > const.js#34
> 
> Makes perfect sense. Will fix this, and Dan's comments and re-submit the
> patch.
> 
> Thank you!

And by fix this I mean I will add the boolean value. Something like wasm.test_x64_bc?

Comment 12

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to dbounov from comment #11)
> (In reply to dbounov from comment #10)
> > Makes perfect sense. Will fix this, and Dan's comments and re-submit the
> > patch.
> > 
> > Thank you!
> 
> And by fix this I mean I will add the boolean value. Something like
> wasm.test_x64_bc?

Thank you! Let's make it unaware of the platform (ARM64 may use signal handlers in the future). How about wasm.explicit-bounds-checks? (or even the more explicit wasm.always-generate-bounds-checks)

Comment 13

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8768585 [details] [diff] [review]
bce patch after bbouvier's feedback

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

Clearing the review flag after previous discussion. A few other style nits below.

::: js/src/jit/WasmBCE.cpp
@@ +11,5 @@
> +using namespace js;
> +using namespace js::jit;
> +
> +typedef struct DefAndOffset {
> +    MDefinition *loc;

style nit here and below in a few places: the star goes just after the type's name:

MDefinition* loc;

@@ +45,5 @@
> +
> +            switch (def->op()) {
> +              case MDefinition::Op_WasmBoundsCheck:
> +                {
> +                    MWasmBoundsCheck *bc = def->toWasmBoundsCheck();;

nit: ;;

@@ +46,5 @@
> +            switch (def->op()) {
> +              case MDefinition::Op_WasmBoundsCheck:
> +                {
> +                    MWasmBoundsCheck *bc = def->toWasmBoundsCheck();;
> +                    MDefinition *addr = def->getOperand(0);

(two other instance shere)

@@ +85,5 @@
> +                        if (!(checkPtr && checkPtr->value().loc->block()->dominates(block))) {
> +                            phiChecked = false;
> +                            break;
> +                        } else {
> +                            off = std::min(off, checkPtr->value().endOffset);

uber-nit: We have mozilla::Min for this :-)

@@ +92,5 @@
> +
> +                    MOZ_ASSERT(!phiChecked || off < UINT32_MAX);
> +
> +                    if (phiChecked) {
> +                        if (!checkM.put(def->id(), (DefAndOffsetT) { def, off }))

Since we have curlies for phiChecked anyways, can you hoist the DefAndOffsetT definition just before this if, please?

Comment 14

[[e-mail]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #12)
> (In reply to dbounov from comment #11)
> > (In reply to dbounov from comment #10)
> > > Makes perfect sense. Will fix this, and Dan's comments and re-submit the
> > > patch.
> > > 
> > > Thank you!
> > 
> > And by fix this I mean I will add the boolean value. Something like
> > wasm.test_x64_bc?
> 
> Thank you! Let's make it unaware of the platform (ARM64 may use signal
> handlers in the future). How about wasm.explicit-bounds-checks? (or even the
> more explicit wasm.always-generate-bounds-checks)

Dan suggested that another way to do this would be to key this off of the usesSignalHandlersForAsmJSOOB flag for AsmJS. This way we could support two distinct modes for x64 - signal handlers and bounds checks. We can test each against the other by running an OOB test with both signal handlers and bounds checks, and asserting that we fail in the same place, with the same faulting address. How does this sound?

Thanks, sorry for the back and forth

Comment 15

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to dbounov from comment #14)
> Dan suggested that another way to do this would be to key this off of the
> usesSignalHandlersForAsmJSOOB flag for AsmJS. This way we could support two
> distinct modes for x64 - signal handlers and bounds checks. We can test each
> against the other by running an OOB test with both signal handlers and
> bounds checks, and asserting that we fail in the same place, with the same
> faulting address. How does this sound?
> 
> Thanks, sorry for the back and forth
As long as there is a dynamic runtime switch (either in the form of a JS function to call, or a test directive), works for me, thanks.

Comment 16

[[e-mail]]

Attachment: rebased_patch_with_switch.diff

Post bbouvier's 1268024 landing, I rebased my diff to his latest code. Also resolved style nits from his latest round of review, and added a Jit runtime option for enabling explicit bounds checking.

Comment 17

[[e-mail]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #13)
> Comment on attachment 8768585 [details] [diff] [review]
> bce patch after bbouvier's feedback
> 
> Review of attachment 8768585 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Clearing the review flag after previous discussion. A few other style nits
> below.
> 
> ::: js/src/jit/WasmBCE.cpp
> @@ +11,5 @@
> > +using namespace js;
> > +using namespace js::jit;
> > +
> > +typedef struct DefAndOffset {
> > +    MDefinition *loc;
> 
> style nit here and below in a few places: the star goes just after the
> type's name:
> 
> MDefinition* loc;
> 
> @@ +45,5 @@
> > +
> > +            switch (def->op()) {
> > +              case MDefinition::Op_WasmBoundsCheck:
> > +                {
> > +                    MWasmBoundsCheck *bc = def->toWasmBoundsCheck();;
> 
> nit: ;;
> 
> @@ +46,5 @@
> > +            switch (def->op()) {
> > +              case MDefinition::Op_WasmBoundsCheck:
> > +                {
> > +                    MWasmBoundsCheck *bc = def->toWasmBoundsCheck();;
> > +                    MDefinition *addr = def->getOperand(0);
> 
> (two other instance shere)
> 
> @@ +85,5 @@
> > +                        if (!(checkPtr && checkPtr->value().loc->block()->dominates(block))) {
> > +                            phiChecked = false;
> > +                            break;
> > +                        } else {
> > +                            off = std::min(off, checkPtr->value().endOffset);
> 
> uber-nit: We have mozilla::Min for this :-)
> 
> @@ +92,5 @@
> > +
> > +                    MOZ_ASSERT(!phiChecked || off < UINT32_MAX);
> > +
> > +                    if (phiChecked) {
> > +                        if (!checkM.put(def->id(), (DefAndOffsetT) { def, off }))
> 
> Since we have curlies for phiChecked anyways, can you hoist the
> DefAndOffsetT definition just before this if, please?

Should be addressed with the last patch.

Comment 18

[[e-mail]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #15)
> (In reply to dbounov from comment #14)
> > Dan suggested that another way to do this would be to key this off of the
> > usesSignalHandlersForAsmJSOOB flag for AsmJS. This way we could support two
> > distinct modes for x64 - signal handlers and bounds checks. We can test each
> > against the other by running an OOB test with both signal handlers and
> > bounds checks, and asserting that we fail in the same place, with the same
> > faulting address. How does this sound?
> > 
> > Thanks, sorry for the back and forth
> As long as there is a dynamic runtime switch (either in the form of a JS
> function to call, or a test directive), works for me, thanks.

Should be addressed with the last patch.

Comment 19

[[e-mail]]

Attachment: rebased_patch_with_switch_fixed_codegen.diff

As Dan pointed out, I forgot to actually use isRedunant in CodeGen :(. Added:

1) Don't emit redunant WASM BCs in opt
2) In debug, for x86,x64,arm emit redundant WASM BCs that fail hard for fuzzing.

Potentially important things to check:

1) Changes to Arm Codegen logic
2) The reasoning behind keeping isRedundant() separate from needsBoundsCheck()

Thanks y'all!!

Comment 20

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8770339 [details] [diff] [review]
rebased_patch_with_switch_fixed_codegen.diff

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

Thanks, getting better and better! Mostly stylistic nits below, so next round should be all good. Can you add a few test cases where you make use of setJitCompilerOptions('wasm.explicit-bounds-check', 1);?

::: js/src/jit/JitOptions.cpp
@@ +220,5 @@
>  
>      // Test whether wasm int64 / double NaN bits testing is enabled.
>      SET_DEFAULT(wasmTestMode, false);
> +
> +    // Deterimnes whether explicit bounds check will be used for OOB

nit: determines

::: js/src/jit/MIR.h
@@ +13012,2 @@
>      {
>          setMovable();

By the way, do you still observe the issue you described by email with setMovable()?

@@ +13038,5 @@
> +    void setRedundant(bool val) {
> +        redundant_ = val;
> +    }
> +  private:
> +    bool redundant_;

nit: Can you put this attribute member to the top of this class, just before the private ctor, please?

::: js/src/jit/WasmBCE.cpp
@@ +16,5 @@
> +    uint32_t endOffset;
> +};
> +
> +typedef js::HashMap<uint32_t, struct DefAndOffset, DefaultHasher<uint32_t>, SystemAllocPolicy>
> +    LastCheckMT;

I am not sure what the MT stands for, here. Maybe we could rename this to something more telling?

@@ +27,5 @@
> +// can ONLY GROW. If we allow SHRINKING the heap, this pass should be
> +// RECONSIDERED.
> +//
> +// TODO (dbounov): Are there a lot of cases where there is no single dominating
> +// check, but a set of checks that toghether dominate a redundant check?

nit: together

@@ +32,5 @@
> +//
> +// TODO (dbounov): Generalize to constant additions relative to one base
> +bool jit::EliminateBoundsChecks(MIRGenerator* mir, MIRGraph& graph) {
> +    // Map for dominating block where a given definition was checked
> +    LastCheckMT checkM;

What does the M stand for, in checkM? (map?) Could we make it a more explicit name, like alreadySeen, maybe?

@@ +43,5 @@
> +            MDefinition* def = *dIter++;
> +
> +            switch (def->op()) {
> +              case MDefinition::Op_WasmBoundsCheck:
> +                {

style nit:

switch (test) {
  case MDefinition::Blabla: { // 2 spaces (half indent) after the switch column for 'case', curly goes on the same line
    body(); // 2 spaces after the 'case' column for the body
    something();
    break;
  } // aligned with the 'case' keyword
}

What do you think of using simple ifs, instead of a switch with 2 cases? You could do

if (def->isWasmBoundsCheck()) {
    MWasmBoundsCheck* check = def->toWasmBoundsCheck();
    // etc.
    continue;
}

if (!def->isPhi())
    continue;

MPhi* phi = def->toPhi();
// etc.

@@ +54,5 @@
> +                        checkPtr->value().loc->block()->dominates(block)) {
> +                        // Address already checked. Discard current check
> +                        bc->setRedundant(true);
> +                    } else {
> +                        struct DefAndOffset defOff = { def, bc->endOffset() };

style nit: no need to put the |struct| keyword in c++

@@ +80,5 @@
> +                    for (int i = 0, nOps = phi->numOperands(); i < nOps; i++) {
> +                        MDefinition* src = phi->getOperand(i);
> +                        LastCheckMT::Ptr checkPtr = checkM.lookup(src->id());
> +
> +                        if (!(checkPtr && checkPtr->value().loc->block()->dominates(block))) {

Can you apply De Morgan's rule here, for fewer parenthesis, please?

@@ +89,5 @@
> +                        }
> +                    }
> +
> +                    if (phiChecked) {
> +                        struct DefAndOffset defOff = { def, off };

ditto (struct keyword not needed)

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +2215,5 @@
> +
> +        uint32_t cmpOffset = masm.ma_BoundsCheck(ptrPlusOffset).getOffset();
> +        masm.append(wasm::BoundsCheck(cmpOffset));
> +        masm.as_b(wasm::JumpTarget::OutOfBounds, Assembler::Above);
> +    } else {

Should this be: else if (JitOptions.wasmExplicitBoundsCheck)?

@@ +2224,5 @@
> +        Register ptr = ToRegister(ins->ptr());
> +
> +        ScratchRegisterScope ptrPlusOffset(masm);
> +        masm.move32(Imm32(endOffset), ptrPlusOffset);
> +        masm.ma_add(ptr, ptrPlusOffset, SetCC);

All of this code is duplicated between the two branches. Can you hoist it up above the |if (!mir->isRedundant())| please?

::: js/src/jit/x86-shared/CodeGenerator-x86-shared.cpp
@@ +494,5 @@
>      MOZ_ASSERT(mir->endOffset() >= 1,
>                 "need to subtract 1 to use JAE, see also AssemblerX86Shared::UpdateBoundsCheck");
> +    /*
> +     * redundant and mir->needsBoundsCheck() fullfill a very similar role. They are not yet merged
> +     * toghether since:

nit: fulfill, together

@@ +496,5 @@
> +    /*
> +     * redundant and mir->needsBoundsCheck() fullfill a very similar role. They are not yet merged
> +     * toghether since:
> +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> +     *  semantically apply (MWasmLoad/MWasmStore).

Do MWasmLoad/MWasmStore actually use them, from lowering to codegen? I don't think so.

@@ +498,5 @@
> +     * toghether since:
> +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> +     *  semantically apply (MWasmLoad/MWasmStore).
> +     *  2) it governs both Wasm and AsmJS bounds checks. Don't want to impose a sweeping change to
> +     *  AsmJS without more discussion

AsmJS bounds checks are embedded in the MIR node action (load/store). Only wasm emits MWasmBoundsChecks/

With the two arguments in mind, I think you could actually reuse needsBoundsCheck instead of "redundant". Good find! Probably we could remove the redundant flag (pun intended) in a follow-up, if you prefer.

@@ +504,5 @@
> +    if (!redundant) {
> +        uint32_t cmpOffset = masm.cmp32WithPatch(ptr, Imm32(1 - mir->endOffset())).offset();
> +        masm.j(Assembler::AboveOrEqual, wasm::JumpTarget::OutOfBounds);
> +        masm.append(wasm::BoundsCheck(cmpOffset));
> +    } else {

should this be: else if (JitOptions.wasmExplicitBoundsChecks) ?

Comment 21

[[e-mail]]

Attachment: rebased_patch_with_switch_fixed_codegen_bbouvier_rev2.diff

All comments in Benjamin's previous round that were fixed are omitted. Only copying stuff that requires more attention/discussion:

> Thanks, getting better and better! Mostly stylistic nits below, so next
> round should be all good. Can you add a few test cases where you make use of
> setJitCompilerOptions('wasm.explicit-bounds-check', 1);?

Excellent point. Working on it now. Will update my patch when I have a test ready.

> 
> ::: js/src/jit/MIR.h
> @@ +13012,2 @@
> >      {
> >          setMovable();
> 
> By the way, do you still observe the issue you described by email with
> setMovable()?
> 

TODO: Checking at the moment...

> What do you think of using simple ifs, instead of a switch with 2 cases? You
> could do
> 
> if (def->isWasmBoundsCheck()) {
>     MWasmBoundsCheck* check = def->toWasmBoundsCheck();
>     // etc.
>     continue;
> }
> 
> if (!def->isPhi())
>     continue;
> 
> MPhi* phi = def->toPhi();
> // etc.
> 

Slight preference for switch I guess?

> ::: js/src/jit/arm/CodeGenerator-arm.cpp
> @@ +2215,5 @@
> > +
> > +        uint32_t cmpOffset = masm.ma_BoundsCheck(ptrPlusOffset).getOffset();
> > +        masm.append(wasm::BoundsCheck(cmpOffset));
> > +        masm.as_b(wasm::JumpTarget::OutOfBounds, Assembler::Above);
> > +    } else {
> 
> Should this be: else if (JitOptions.wasmExplicitBoundsCheck)?
> 

I don't think so? On Arm I think the wasmExplicitBoundsCheck flag is a no-op since we always need bounds check no?

> @@ +2224,5 @@
> > +        Register ptr = ToRegister(ins->ptr());
> > +
> > +        ScratchRegisterScope ptrPlusOffset(masm);
> > +        masm.move32(Imm32(endOffset), ptrPlusOffset);
> > +        masm.ma_add(ptr, ptrPlusOffset, SetCC);
> 
> All of this code is duplicated between the two branches. Can you hoist it up
> above the |if (!mir->isRedundant())| please?
> 

I am not sure I can hoist that code, as the else branch is also in an #ifdef DEBUG block.
If it were hoisted, than on non-debug builds wouldn't the hoisted code emit spurious instructions on eliminated checks?
I can probably hoist just the first line, which doesn't cause anything to be emitted:

> > +        Register ptr = ToRegister(ins->ptr());

> @@ +496,5 @@
> > +    /*
> > +     * redundant and mir->needsBoundsCheck() fullfill a very similar role. They are not yet merged
> > +     * toghether since:
> > +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> > +     *  semantically apply (MWasmLoad/MWasmStore).
> 
> Do MWasmLoad/MWasmStore actually use them, from lowering to codegen? I don't
> think so.
> 

Response:

I don't think it does use them either. Its just strange that it exists on nodes to which it doesn't apply. I didn't
want to complicate the logic/usage of something that may change, and I didn't understand fully.

> @@ +498,5 @@
> > +     * toghether since:
> > +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> > +     *  semantically apply (MWasmLoad/MWasmStore).
> > +     *  2) it governs both Wasm and AsmJS bounds checks. Don't want to impose a sweeping change to
> > +     *  AsmJS without more discussion
> 
> AsmJS bounds checks are embedded in the MIR node action (load/store). Only
> wasm emits MWasmBoundsChecks/
> 

I am not sure thats the case:

CodeGeneratorX64::visitAsmJSCompareExchangeHeap(LAsmJSCompareExchangeHeap* ins)
{
...
    // Note that we can't use the same machinery as normal asm.js loads/stores
    // since signal-handler bounds checking is not yet implemented for atomic
    // accesses.
    maybeEmitWasmBoundsCheckBranch(mir, ptr);


> With the two arguments in mind, I think you could actually reuse
> needsBoundsCheck instead of "redundant". Good find! Probably we could remove
> the redundant flag (pun intended) in a follow-up, if you prefer.
> 

I agree, it would be nice to merge them in followup :).

> @@ +504,5 @@
> > +    if (!redundant) {
> > +        uint32_t cmpOffset = masm.cmp32WithPatch(ptr, Imm32(1 - mir->endOffset())).offset();
> > +        masm.j(Assembler::AboveOrEqual, wasm::JumpTarget::OutOfBounds);
> > +        masm.append(wasm::BoundsCheck(cmpOffset));
> > +    } else {
> 
> should this be: else if (JitOptions.wasmExplicitBoundsChecks) ?

I don't think so. TL;DR: JitOption.wasmExplicitBoundsCheck currently controls whether MWasmBoundsChecks
even get lowered to LWasmBoundsChecks on x64 (they are always lowered on x86).

Long version:

JitOptions.wasmExplicitBoundsCheck is used in WasmTypes.cpp to initialize
the forOOB field of SignalUsage. This trickles down to CompilerArgs, and furhter down finally
to MIRGenerator::usesSignalHandlersForAsmJSOOB_ which is checked here:

bool
MIRGenerator::needsBoundsCheckBranch(const MWasmMemoryAccess* access) const
{
    // A heap access needs a bounds-check branch if we're not relying on signal
    // handlers to catch errors, and if it's not proven to be within bounds.
    // We use signal-handlers on x64, but on x86 there isn't enough address
    // space for a guard region.  Also, on x64 the atomic loads and stores
    // can't (yet) use the signal handlers.
#if defined(ASMJS_MAY_USE_SIGNAL_HANDLERS_FOR_OOB)
    if (usesSignalHandlersForAsmJSOOB_ && !access->isAtomicAccess())
        return false;
#endif
    return access->needsBoundsCheck();
}

Which decides if MWasmBoundsChecks are lowered in LWasmBoundsChecks on x86:

void
LIRGeneratorX86Shared::visitWasmBoundsCheck(MWasmBoundsCheck* ins)
{
    if (!gen->needsBoundsCheckBranch(ins))
        return;

    MDefinition* index = ins->input();
    auto* lir = new(alloc()) LWasmBoundsCheck(useRegisterAtStart(index));
    add(lir, ins);
}

So JitOptions.wasmExplicitBoundsChecks controls whether bounds checks are emitted at an earlier stage?

Comment 22

[[e-mail]]

(In reply to dbounov from comment #21)
> Created attachment 8770674 [details] [diff] [review]
> rebased_patch_with_switch_fixed_codegen_bbouvier_rev2.diff
> 
> All comments in Benjamin's previous round that were fixed are omitted. Only
> copying stuff that requires more attention/discussion:
> 
> > Thanks, getting better and better! Mostly stylistic nits below, so next
> > round should be all good. Can you add a few test cases where you make use of
> > setJitCompilerOptions('wasm.explicit-bounds-check', 1);?
> 
> Excellent point. Working on it now. Will update my patch when I have a test
> ready.
> 
> > 
> > ::: js/src/jit/MIR.h
> > @@ +13012,2 @@
> > >      {
> > >          setMovable();
> > 
> > By the way, do you still observe the issue you described by email with
> > setMovable()?
> > 
> 

Yes this is still reporoducible.

> 
> > What do you think of using simple ifs, instead of a switch with 2 cases? You
> > could do
> > 
> > if (def->isWasmBoundsCheck()) {
> >     MWasmBoundsCheck* check = def->toWasmBoundsCheck();
> >     // etc.
> >     continue;
> > }
> > 
> > if (!def->isPhi())
> >     continue;
> > 
> > MPhi* phi = def->toPhi();
> > // etc.
> > 
> 
> Slight preference for switch I guess?
> 
> > ::: js/src/jit/arm/CodeGenerator-arm.cpp
> > @@ +2215,5 @@
> > > +
> > > +        uint32_t cmpOffset = masm.ma_BoundsCheck(ptrPlusOffset).getOffset();
> > > +        masm.append(wasm::BoundsCheck(cmpOffset));
> > > +        masm.as_b(wasm::JumpTarget::OutOfBounds, Assembler::Above);
> > > +    } else {
> > 
> > Should this be: else if (JitOptions.wasmExplicitBoundsCheck)?
> > 
> 
> I don't think so? On Arm I think the wasmExplicitBoundsCheck flag is a no-op
> since we always need bounds check no?
> 
> > @@ +2224,5 @@
> > > +        Register ptr = ToRegister(ins->ptr());
> > > +
> > > +        ScratchRegisterScope ptrPlusOffset(masm);
> > > +        masm.move32(Imm32(endOffset), ptrPlusOffset);
> > > +        masm.ma_add(ptr, ptrPlusOffset, SetCC);
> > 
> > All of this code is duplicated between the two branches. Can you hoist it up
> > above the |if (!mir->isRedundant())| please?
> > 
> 
> I am not sure I can hoist that code, as the else branch is also in an #ifdef
> DEBUG block.
> If it were hoisted, than on non-debug builds wouldn't the hoisted code emit
> spurious instructions on eliminated checks?
> I can probably hoist just the first line, which doesn't cause anything to be
> emitted:
> 
> > > +        Register ptr = ToRegister(ins->ptr());
> 
> > @@ +496,5 @@
> > > +    /*
> > > +     * redundant and mir->needsBoundsCheck() fullfill a very similar role. They are not yet merged
> > > +     * toghether since:
> > > +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> > > +     *  semantically apply (MWasmLoad/MWasmStore).
> > 
> > Do MWasmLoad/MWasmStore actually use them, from lowering to codegen? I don't
> > think so.
> > 
> 
> Response:
> 
> I don't think it does use them either. Its just strange that it exists on
> nodes to which it doesn't apply. I didn't
> want to complicate the logic/usage of something that may change, and I
> didn't understand fully.
> 
> > @@ +498,5 @@
> > > +     * toghether since:
> > > +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> > > +     *  semantically apply (MWasmLoad/MWasmStore).
> > > +     *  2) it governs both Wasm and AsmJS bounds checks. Don't want to impose a sweeping change to
> > > +     *  AsmJS without more discussion
> > 
> > AsmJS bounds checks are embedded in the MIR node action (load/store). Only
> > wasm emits MWasmBoundsChecks/
> > 
> 
> I am not sure thats the case:
> 
> CodeGeneratorX64::visitAsmJSCompareExchangeHeap(LAsmJSCompareExchangeHeap*
> ins)
> {
> ...
>     // Note that we can't use the same machinery as normal asm.js
> loads/stores
>     // since signal-handler bounds checking is not yet implemented for atomic
>     // accesses.
>     maybeEmitWasmBoundsCheckBranch(mir, ptr);
> 
> 
> > With the two arguments in mind, I think you could actually reuse
> > needsBoundsCheck instead of "redundant". Good find! Probably we could remove
> > the redundant flag (pun intended) in a follow-up, if you prefer.
> > 
> 
> I agree, it would be nice to merge them in followup :).
> 
> > @@ +504,5 @@
> > > +    if (!redundant) {
> > > +        uint32_t cmpOffset = masm.cmp32WithPatch(ptr, Imm32(1 - mir->endOffset())).offset();
> > > +        masm.j(Assembler::AboveOrEqual, wasm::JumpTarget::OutOfBounds);
> > > +        masm.append(wasm::BoundsCheck(cmpOffset));
> > > +    } else {
> > 
> > should this be: else if (JitOptions.wasmExplicitBoundsChecks) ?
> 
> I don't think so. TL;DR: JitOption.wasmExplicitBoundsCheck currently
> controls whether MWasmBoundsChecks
> even get lowered to LWasmBoundsChecks on x64 (they are always lowered on
> x86).
> 
> Long version:
> 
> JitOptions.wasmExplicitBoundsCheck is used in WasmTypes.cpp to initialize
> the forOOB field of SignalUsage. This trickles down to CompilerArgs, and
> furhter down finally
> to MIRGenerator::usesSignalHandlersForAsmJSOOB_ which is checked here:
> 
> bool
> MIRGenerator::needsBoundsCheckBranch(const MWasmMemoryAccess* access) const
> {
>     // A heap access needs a bounds-check branch if we're not relying on
> signal
>     // handlers to catch errors, and if it's not proven to be within bounds.
>     // We use signal-handlers on x64, but on x86 there isn't enough address
>     // space for a guard region.  Also, on x64 the atomic loads and stores
>     // can't (yet) use the signal handlers.
> #if defined(ASMJS_MAY_USE_SIGNAL_HANDLERS_FOR_OOB)
>     if (usesSignalHandlersForAsmJSOOB_ && !access->isAtomicAccess())
>         return false;
> #endif
>     return access->needsBoundsCheck();
> }
> 
> Which decides if MWasmBoundsChecks are lowered in LWasmBoundsChecks on x86:
> 
> void
> LIRGeneratorX86Shared::visitWasmBoundsCheck(MWasmBoundsCheck* ins)
> {
>     if (!gen->needsBoundsCheckBranch(ins))
>         return;
> 
>     MDefinition* index = ins->input();
>     auto* lir = new(alloc()) LWasmBoundsCheck(useRegisterAtStart(index));
>     add(lir, ins);
> }
> 
> So JitOptions.wasmExplicitBoundsChecks controls whether bounds checks are
> emitted at an earlier stage?

Comment 23

[[e-mail]]

Attachment: rebased_after_lth_with_tests.diff

Same as previous patch (all comments from previous patch applies), but also rebased to lth's latest baseline changes (the old baseline caused a test failure) and added tests:

- make sure all i32 basic-memory tests run twice, once with wasm.explicit-bounds-check set and once without
- add basic-bce.js - starting place for exercising bce specifically. Currently contains only simple straighline tests.

Comment 24

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to dbounov from comment #22)
> (In reply to dbounov from comment #21)
> > Created attachment 8770674 [details] [diff] [review]
> > rebased_patch_with_switch_fixed_codegen_bbouvier_rev2.diff
> > 
> > All comments in Benjamin's previous round that were fixed are omitted. Only
> > copying stuff that requires more attention/discussion:
> > 
> > > Thanks, getting better and better! Mostly stylistic nits below, so next
> > > round should be all good. Can you add a few test cases where you make use of
> > > setJitCompilerOptions('wasm.explicit-bounds-check', 1);?
> > 
> > Excellent point. Working on it now. Will update my patch when I have a test
> > ready.
> > 
> > > 
> > > ::: js/src/jit/MIR.h
> > > @@ +13012,2 @@
> > > >      {
> > > >          setMovable();
> > > 
> > > By the way, do you still observe the issue you described by email with
> > > setMovable()?
> > > 
> > 
> 
> Yes this is still reporoducible.
Can you make a test case out of it, please?

Comment 25

[Benjamin Bouvier [:bbouvier] (inactive)]

For what it's worth,

> So JitOptions.wasmExplicitBoundsChecks controls whether bounds checks are emitted at an earlier stage?

It's actually that MWasmBoundsCheck are not generated when useSignal.forOOB is false (see WasmIonCompile.cpp).

Comment 26

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8771140 [details] [diff] [review]
rebased_after_lth_with_tests.diff

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

Looks good to me, thanks for sticking!

::: js/src/jit-test/tests/wasm/basic-bce.js
@@ +139,5 @@
> + * Thus it is important that these tests be run on x86.
> + */
> +
> +function testOOB(mod, args) {
> +    assertErrorMessage(() => myApply(mod, args), Error, /invalid or out-of-range index/);

() => mod(...args)

and then you can remove myApply

@@ +171,5 @@
> +    testOOB(mod, [lastValidIndex, lastValidIndex + 42]);
> +
> +    mod = loadTwiceSameBasePlusConstModule(op, width, offset, align, 1);
> +
> +    testOk(mod, [lastValidIndex-1], getInt(width, lastValidIndex - 1 + offset, mem), op);

Shouldn't this be getInt(width, lastValidIndex + offset, mem), instead? I think we want to read (base + const + offset), where base := lastValidIndex - 1, const := 1, offset is variable, so we want lastValidIndex + offset at the end. Is that correct? If so, can you change the memory values so that this test would fail, if remaining unchanged?

@@ +177,5 @@
> +
> +    // Two consecutive loads from same base with different offsets
> +    mod = loadTwiceSameBasePlusConstModule(op, width, offset, align, 2);
> +
> +    testOk(mod, [lastValidIndex-2], getInt(width, lastValidIndex - 2 + offset, mem), op);

ditto

::: js/src/jit/MIR.h
@@ +13056,5 @@
>    : public MUnaryInstruction,
>      public MWasmMemoryAccess,
>      public NoTypePolicy::Data
>  {
> +    bool redundant_;

nit: please add a blank line after this

::: js/src/jit/WasmBCE.cpp
@@ +15,5 @@
> +    MDefinition* loc;
> +    uint32_t endOffset;
> +};
> +
> +typedef js::HashMap<uint32_t, struct DefAndOffset, DefaultHasher<uint32_t>, SystemAllocPolicy>

nit: no need for the struct keyword here

@@ +16,5 @@
> +    uint32_t endOffset;
> +};
> +
> +typedef js::HashMap<uint32_t, struct DefAndOffset, DefaultHasher<uint32_t>, SystemAllocPolicy>
> +    LastSeenMapT;

Still not sure what the T means here. Can we simply name this SeenMap, instead?

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +2227,5 @@
> +        masm.move32(Imm32(endOffset), ptrPlusOffset);
> +        masm.ma_add(ptr, ptrPlusOffset, SetCC);
> +
> +        // Detect unsigned overflow by checking the carry bit.
> +        masm.as_b(&ok1, Assembler::Below); // Assembler::Below <=> CarryClear <=> !CarrySet

Better to add a Assembler::CarryClear to the list of assembler conditions, imo (I've added CarrySet to the list of Assembler::Condition for that reason).

::: js/src/jit/x86-shared/CodeGenerator-x86-shared.cpp
@@ +498,5 @@
> +     * together since:
> +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> +     *  semantically apply (MWasmLoad/MWasmStore).
> +     *  2) it governs both Wasm and AsmJS bounds checks. Don't want to impose a sweeping change to
> +     *  AsmJS without more discussion

Can you open a follow-up for this, and reference it from this comment with a TODO and the bug number, please?

Comment 27

[[e-mail]]

Attachment: rebased_after_lth_and_bbouvier_rev3.diff

(In reply to Benjamin Bouvier [:bbouvier] from comment #26)
> Comment on attachment 8771140 [details] [diff] [review]
> rebased_after_lth_with_tests.diff
> 
> Review of attachment 8771140 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks good to me, thanks for sticking!
> 
Thanks for all the time and attention :)

> ::: js/src/jit-test/tests/wasm/basic-bce.js
> @@ +139,5 @@
> > + * Thus it is important that these tests be run on x86.
> > + */
> > +
> > +function testOOB(mod, args) {
> > +    assertErrorMessage(() => myApply(mod, args), Error, /invalid or out-of-range index/);
> 
> () => mod(...args)
> 
> and then you can remove myApply

Fixed

> 
> @@ +171,5 @@
> > +    testOOB(mod, [lastValidIndex, lastValidIndex + 42]);
> > +
> > +    mod = loadTwiceSameBasePlusConstModule(op, width, offset, align, 1);
> > +
> > +    testOk(mod, [lastValidIndex-1], getInt(width, lastValidIndex - 1 + offset, mem), op);
> 
> Shouldn't this be getInt(width, lastValidIndex + offset, mem), instead? I
> think we want to read (base + const + offset), where base := lastValidIndex
> - 1, const := 1, offset is variable, so we want lastValidIndex + offset at
> the end. Is that correct? If so, can you change the memory values so that
> this test would fail, if remaining unchanged?
> 

Good point... Fixed.

> @@ +177,5 @@
> > +
> > +    // Two consecutive loads from same base with different offsets
> > +    mod = loadTwiceSameBasePlusConstModule(op, width, offset, align, 2);
> > +
> > +    testOk(mod, [lastValidIndex-2], getInt(width, lastValidIndex - 2 + offset, mem), op);
> 
> ditto
> 

Fixed.

> ::: js/src/jit/MIR.h
> @@ +13056,5 @@
> >    : public MUnaryInstruction,
> >      public MWasmMemoryAccess,
> >      public NoTypePolicy::Data
> >  {
> > +    bool redundant_;
> 
> nit: please add a blank line after this
> 

Fixed.

> ::: js/src/jit/WasmBCE.cpp
> @@ +15,5 @@
> > +    MDefinition* loc;
> > +    uint32_t endOffset;
> > +};
> > +
> > +typedef js::HashMap<uint32_t, struct DefAndOffset, DefaultHasher<uint32_t>, SystemAllocPolicy>
> 
> nit: no need for the struct keyword here

Fixed.

> 
> @@ +16,5 @@
> > +    uint32_t endOffset;
> > +};
> > +
> > +typedef js::HashMap<uint32_t, struct DefAndOffset, DefaultHasher<uint32_t>, SystemAllocPolicy>
> > +    LastSeenMapT;
> 
> Still not sure what the T means here. Can we simply name this SeenMap,
> instead?
> 

The T stands for Type, do distinguish from a variable named LastSeenMap. Its just a habbit. Will rename to LastSeenMap
Fixed.

> ::: js/src/jit/arm/CodeGenerator-arm.cpp
> @@ +2227,5 @@
> > +        masm.move32(Imm32(endOffset), ptrPlusOffset);
> > +        masm.ma_add(ptr, ptrPlusOffset, SetCC);
> > +
> > +        // Detect unsigned overflow by checking the carry bit.
> > +        masm.as_b(&ok1, Assembler::Below); // Assembler::Below <=> CarryClear <=> !CarrySet
> 
> Better to add a Assembler::CarryClear to the list of assembler conditions,
> imo (I've added CarrySet to the list of Assembler::Condition for that
> reason).
> 

Fixed.

> ::: js/src/jit/x86-shared/CodeGenerator-x86-shared.cpp
> @@ +498,5 @@
> > +     * together since:
> > +     *  1) needsBoundsCheck's scope is unclear - it applies to nodes for which it doesn't
> > +     *  semantically apply (MWasmLoad/MWasmStore).
> > +     *  2) it governs both Wasm and AsmJS bounds checks. Don't want to impose a sweeping change to
> > +     *  AsmJS without more discussion
> 
> Can you open a follow-up for this, and reference it from this comment with a
> TODO and the bug number, please?

Done - 1287224 Unify MWasmBoundsCheck::redunant_ and needsBoundsCheck

Comment 28

[Dan Gohman [:sunfish]]

Comment on attachment 8771591 [details] [diff] [review]
rebased_after_lth_and_bbouvier_rev3.diff

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

Looks good!

Comment 29

[[e-mail]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/236e2d22595cac5320a74e506b6cccd002e3d6b2
Bug 1282618 - Baldr: Implement a simple redundant bounds check elimination pass r=sunfish,bbouvier

Comment 30

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/236e2d22595c