Add index masking for MBoundsCheck

RESOLVED FIXED in Firefox 59

Status

()

Core
JavaScript Engine: JIT
RESOLVED FIXED
a month ago
a month ago

People

(Reporter: jandem, Assigned: jandem)

Tracking

(Blocks: 1 bug)

unspecified
mozilla59
Points:
---

Firefox Tracking Flags

(firefox59 fixed)

Details

Attachments

(1 attachment, 2 obsolete attachments)

Comment hidden (empty)
(Assignee)

Comment 1

a month ago
Created attachment 8942665 [details] [diff] [review]
Patch

Overhead is pretty bad; regresses Kraken by 20% or so but Kraken is worst-case of course... I'll do a Talos Try push.

There's an optimization to hoist bounds checks for cases like:

  for (var i = 0; i < len; i++) {
    v = arr[i];
  }

But unfortunately I don't think we can hoist/eliminate the index masking since i can go out-of-bounds on speculative paths.
Comment on attachment 8942665 [details] [diff] [review]
Patch

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

::: js/src/jit/MacroAssembler-inl.h
@@ +838,5 @@
> +void
> +MacroAssembler::maskIndexImpl(int32_t index, const T& length, Register output)
> +{
> +    // mask := ((index - length) & ~index) >> 31
> +    // output := index & mask

Shouldn't this be:

  // Propagate the sign bit of the underflow to create a full mask.
  mask := int32_t(index - length) >> 31
  // zero the result if the length is OOB.
  output := index & ~mask

another option, which is illegal from the supposed accessed values, but remove the "neg" from the critical path.

  // -1 the result if the length is OOB.
  output := index | mask
(Assignee)

Comment 3

a month ago
(In reply to Jan de Mooij [:jandem] from comment #1)
> Overhead is pretty bad; regresses Kraken by 20% or so but Kraken is
> worst-case of course...

The overhead V8 had is less (11-12% or so IIRC) so I was worried about that, but V8 is slower on Kraken these days - the actual slowdown on some subtests I checked is somewhat similar, it's just a larger fraction for us :/
(In reply to Nicolas B. Pierron [:nbp] from comment #2)
> Comment on attachment 8942665 [details] [diff] [review]
> Patch
> 
> Review of attachment 8942665 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MacroAssembler-inl.h
> @@ +838,5 @@
> > +void
> > +MacroAssembler::maskIndexImpl(int32_t index, const T& length, Register output)
> > +{
> > +    // mask := ((index - length) & ~index) >> 31
> > +    // output := index & mask
> 
> Shouldn't this be:

Sorry my previous proposal was incorrect, and I did not considered the case where the int32 sign bit is set on the index.
On the other hand, I made another proposal on IRC, which might work more efficiently on 64 bits system:

  // index is an int32_t. (by construction or computation)
  mask := ( uint64_t(index) - uint64_t(length) ) >> 32
  // mask is 0x11…11 if index < length, 0 otherwise
  output := index & mask
(Assignee)

Comment 5

a month ago
Created attachment 8942935 [details] [diff] [review]
Patch
Attachment #8942665 - Attachment is obsolete: true
Attachment #8942935 - Flags: review?(nicolas.b.pierron)
Attachment #8942935 - Flags: review?(luke)
Comment on attachment 8942935 [details] [diff] [review]
Patch

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

::: js/src/jit/IonBuilder.cpp
@@ +13255,5 @@
>      if (failedBoundsCheck_)
>          check->setNotMovable();
>  
> +    if (kind == BoundsCheckKind::IsLoad && JitOptions.spectreIndexMasking) {
> +        check = MMaskIndex::New(alloc(), check, length);

follow-up / nit: MaskedIndex instead of MaskIndex ?

Also, I was wondering if this operation has a proper name.

    index < length => index
    index >= length => 0, or any value in [0 .. length[ range.

Maybe ModClamp ?  output = clamp(index, length) % length

::: js/src/jit/MacroAssembler.cpp
@@ +3455,5 @@
> +    maskIndexImpl(index, length, output);
> +}
> +
> +void
> +MacroAssembler::maskIndex(Register index, Register length, Register output)

follow-up: Use this function for MacroAssembler::loadStringChar.

@@ +3467,5 @@
> +    // mask is 0x11…11 if index < length, 0 otherwise.
> +    move32(index, output);
> +    subPtr(length, output);
> +    rshiftPtr(Imm32(32), output);
> +    and32(index, output);

nit: MOZ_ASSERT(index != output && length != output)
Attachment #8942935 - Flags: review?(nicolas.b.pierron) → review+
(Assignee)

Comment 7

a month ago
(In reply to Nicolas B. Pierron [:nbp] from comment #6)
> > +    if (kind == BoundsCheckKind::IsLoad && JitOptions.spectreIndexMasking) {
> > +        check = MMaskIndex::New(alloc(), check, length);
> 
> follow-up / nit: MaskedIndex instead of MaskIndex ?

Hm I like using the verb and it matches the MacroAssembler maskIndex method.

> follow-up: Use this function for MacroAssembler::loadStringChar.

Yeah, the next step is to add MacroAssembler::boundsCheck() and use that everywhere, and then we can do the masking there :)

> nit: MOZ_ASSERT(index != output && length != output)

Good idea.

Comment 8

a month ago
Comment on attachment 8942935 [details] [diff] [review]
Patch

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

(Sorry for delay; failed Linux upgrade required reformat.)

::: js/src/jit/MIR.h
@@ +9517,5 @@
>      }
>      void collectRangeInfoPreTrunc() override;
>  };
>  
> +class MMaskIndex

I wonder if we should be thorough in tagging everything spectre-related with with "spectre" in the name, so, e.g., MSpectreMaskIndex.  I say that because otherwise the node name sounds like it does i&mask.

::: js/src/jit/MacroAssembler.cpp
@@ +3417,5 @@
> +void
> +MacroAssembler::maskIndexImpl(Register index, const T& length, Register output)
> +{
> +    // mask := ((index - length) & ~index) >> 31
> +    // output := index & mask

I think this comment (and below) are missing the ~ reflecting the final not32 before the rshift32Arithmetic?

@@ +3438,5 @@
> +    if (index == 0)
> +        return;
> +    sub32(length, output);
> +    and32(Imm32(~index), output);
> +    rshift32Arithmetic(Imm32(31), output);

Are you missing the not32() here?

Comment 9

a month ago
Comment on attachment 8942935 [details] [diff] [review]
Patch

(Please reflag for review if I'm wrong about comments.)
Attachment #8942935 - Flags: review?(luke)
(Assignee)

Comment 10

a month ago
(In reply to Luke Wagner [:luke] from comment #8)
> I wonder if we should be thorough in tagging everything spectre-related with
> with "spectre" in the name, so, e.g., MSpectreMaskIndex.  I say that because
> otherwise the node name sounds like it does i&mask.

OK I can do that.

> 
> ::: js/src/jit/MacroAssembler.cpp
> @@ +3417,5 @@
> > +void
> > +MacroAssembler::maskIndexImpl(Register index, const T& length, Register output)
> > +{
> > +    // mask := ((index - length) & ~index) >> 31
> > +    // output := index & mask
> 
> I think this comment (and below) are missing the ~ reflecting the final
> not32 before the rshift32Arithmetic?

The final not32 is just to restore the index register to its orginal value: ~~index === index. I'll add a comment.

> 
> @@ +3438,5 @@
> > +    if (index == 0)
> > +        return;
> > +    sub32(length, output);
> > +    and32(Imm32(~index), output);
> > +    rshift32Arithmetic(Imm32(31), output);
> 
> Are you missing the not32() here?

No, because the index is a constant, we don't need the second not32 to "restore" it.
(Assignee)

Comment 11

a month ago
Created attachment 8943517 [details] [diff] [review]
Patch

Now with s/MaskIndex/SpectreMaskIndex/ and some comments.
Attachment #8942935 - Attachment is obsolete: true
Attachment #8943517 - Flags: review?(luke)

Comment 12

a month ago
Comment on attachment 8943517 [details] [diff] [review]
Patch

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

Thanks!
Attachment #8943517 - Flags: review?(luke) → review+

Comment 13

a month ago
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/379a933da614
Add Spectre index masking for bounds-checked loads in Ion. r=luke,nbp
(Assignee)

Comment 14

a month ago
(In reply to Jan de Mooij [:jandem] from comment #7)
> > nit: MOZ_ASSERT(index != output && length != output)
> 
> Good idea.

The patch in bug 1431173 does this :)

Comment 15

a month ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/379a933da614
Status: ASSIGNED → RESOLVED
Last Resolved: a month ago
status-firefox59: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
You need to log in before you can comment on or make changes to this bug.