1141994 - Implement Atomics.isLockFree

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Lars T Hansen [:lth]]

The function Atomics.isLockFree() is new in the Atomics spec and must be implemented with JIT support on x86, x64, and ARM-32, for plain JS and asm.js.  The asm.js bits will also require support in the validator.

On the face of it it seems like it would be useful to sniff the input value whenever possible to generate a single constant, and not have to do any computation.  On the other hand, for a given platform the computation probably costs at most a single compare and generate-boolean; in client code the generate-boolean will likely turn into a conditional branch that was needed anyway.

(Actually the way it is specced now, with illegal input values returning false, it costs more than a single compare.  Worth looking into.)

Comment 1

[Lars T Hansen [:lth]]

Attachment: Complete implementation for interpreter, Ion, and Odin

Platform-independent implementation and test cases for JS and asm.js.

This generates a constant result when possible.  My only concern is that the constant result is generated during code generation, which is a little late since it means branches that depend on the result won't be folded, but it did not seem worth it yet to try to resolve the primitive earlier in the optimization pipeline.  Discuss.

This patch sits on top of the queue in bug 1131613, though it probably does not depend on that queue per se.

Comment 2

[Luke Wagner [:luke]]

Comment on attachment 8593874 [details] [diff] [review]
Complete implementation for interpreter, Ion, and Odin

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

I'm so sorry for having lost track of this review request.  I'll review it quickly next time.

::: js/src/asmjs/AsmJSValidate.cpp
@@ +5067,5 @@
> +    if (!CheckExpr(f, sizeArg, &sizeArgDef, &sizeArgType))
> +        return false;
> +
> +    if (!sizeArgType.isIntish())
> +        return f.failf(sizeArg, "%s is not a subtype of intish", sizeArgType.toChars());

How about instead of taking a dynamic value, we only accept IsLiteralInt() (and then only one of 1,2,4,8)?  That way we can guarantee a constant branch and DCE at validation time.  I was wondering if there was a polymorphic use case here, but the ops themselves are monomorphic (wrt memory width), so I don't see it.

Comment 3

[Lars T Hansen [:lth]]

(In reply to Luke Wagner [:luke] from comment #2)

> How about instead of taking a dynamic value, we only accept IsLiteralInt()
> (and then only one of 1,2,4,8)?  That way we can guarantee a constant branch
> and DCE at validation time.  I was wondering if there was a polymorphic use
> case here, but the ops themselves are monomorphic (wrt memory width), so I
> don't see it.

For asm.js this makes sense.  I'll put up a modification.

Comment 4

[Lars T Hansen [:lth]]

(In reply to Lars T Hansen [:lth] from comment #3)
> (In reply to Luke Wagner [:luke] from comment #2)
> 
> > How about instead of taking a dynamic value, we only accept IsLiteralInt()
> > (and then only one of 1,2,4,8)?  That way we can guarantee a constant branch
> > and DCE at validation time.  I was wondering if there was a polymorphic use
> > case here, but the ops themselves are monomorphic (wrt memory width), so I
> > don't see it.
> 
> For asm.js this makes sense.  I'll put up a modification.

Thinking a little further:

I think the restriction to 1,2,4,8 is probably wrong.  Right now there are no 8-byte atomic values, so 8 is only motivated by looking ahead to int64 or float64.  But in that case there's no reason not to accept 16 (CMPXCHG16B on x64), since if float64 atomics can be motivated then why not float32x4 or int32x4.

Consider also that the SIMD spec has sub-vector loading and storing: SIMD.float32x4.load3() and so on, which IIUC loads three elements.  There's probably no reason we would not use CMPXCHG16B to implement atomic versions of those, and discard one of the words.  In which case, a 12-byte load would be lock-free too.

IMO this primitive should accept all positive integer constants in asm.js.

Comment 5

[Luke Wagner [:luke]]

All integer constants sounds fine.

Comment 6

[Lars T Hansen [:lth]]

Attachment: Complete implementation for interpreter, Ion, and Odin, v2

Same as before except for the code in AsmJSValidate, which now requires a constant integer argument to Atomics.isLockFree, and will compute a constant result.

Comment 7

[Lars T Hansen [:lth]]

(Also updated the test case to not test the variable-argument case, after checking that that is appropriately rejected with a warning.)

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 8617854 [details] [diff] [review]
Complete implementation for interpreter, Ion, and Odin, v2

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

::: js/src/builtin/AtomicsObject.cpp
@@ +515,5 @@
> +    if (!v.isInt32()) {
> +        args.rval().setBoolean(false);
> +        return true;
> +    }
> +    switch (v.toInt32()) {

Maybe add a comment to keep this coherent with CheckAtomicsIsLockFree in AsmJSValidate.cpp?

::: js/src/jit-test/tests/asm.js/testAtomics.js
@@ +547,5 @@
> +	     ilf6: ilf6,
> +	     ilf7: ilf7,
> +	     ilf8: ilf8,
> +	     ilf9: ilf9 };
> +}

Can you assertEq(isAsmJSModule(loadModule_misc), true)?

::: js/src/jit/Lowering.cpp
@@ +4203,5 @@
> +void
> +LIRGenerator::visitAtomicIsLockFree(MAtomicIsLockFree* ins)
> +{
> +    MDefinition* value = ins->input();
> +    if (value->isConstantValue()) {

Rather than doing this optimization here, which happens after all MIR optimizations, could this folding be done during GVN so that it could contribute to branch folding and DCE (which I expect it will be used for).

Also, if we have this switch in Odin, GVN, and AtomicsObject.cpp, perhaps it'd be worth factoring out an Atomics:isLockFree(size_t) so that the switch wasn't replicated in those three places.

::: js/src/jit/MCallOptimize.cpp
@@ +3138,5 @@
>      return InliningStatus_Inlined;
>  }
>  
> +IonBuilder::InliningStatus
> +IonBuilder::inlineAtomicsIsLockFree(CallInfo& callInfo)

I'm not an Ion expert, so perhaps worth getting rs from Jan or Hannes on this bit of code.

Comment 9

[Lars T Hansen [:lth]]

Attachment: Complete implementation for interpreter, Ion, and Odin, v3

Cleaned up further, moved optimization into GVN, abstracted the isLockfree pattern into a function.  I think I addressed all comments from the previous round.

Hannes: perhaps you can examine the Ion bits here.

Comment 10

[Lars T Hansen [:lth]]

Try run for a slightly earlier version that had some include-order warnings, otherwise fine:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=38fe66400900

Comment 11

[Hannes Verschore [:h4writer]]

Comment on attachment 8623544 [details] [diff] [review]
Complete implementation for interpreter, Ion, and Odin, v3

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

Looks good. Now I have some possible improvements

1) Can't we selfhost this? Creating two JS versions functions where one gives true for input 8 and another where false for input 8. And during initialization check IsLockFree8 and install the right one? Not sure if that last is possible. Might want to discuss this with till. But it seems if that is possible, it would require less code and possibly more optimized. (E.g. range analysis can run on it, recover instruction would work by default, gvn works out of the box ...).

2) If the above is not possible. Can you look into making MIsLockFree recoverable? And address the comments raised below.

::: js/src/jit-test/tests/asm.js/testAtomics.js
@@ +563,5 @@
> +    assertEq(misc.ilf5(), 0);
> +    assertEq(misc.ilf6(), 0);
> +    assertEq(misc.ilf7(), 0);
> +    var v = misc.ilf8();
> +    assertEq(v === 0 || v === 1, true);

Isn't this a tautology?

::: js/src/jit/MIR.cpp
@@ +1200,5 @@
> +MDefinition*
> +MAtomicIsLockFree::foldsTo(TempAllocator& alloc)
> +{
> +    MDefinition* input = getOperand(0);
> +    if (!input->isConstant())

isConstantValue() (which will also give the constant for boxed constants).

@@ +1203,5 @@
> +    MDefinition* input = getOperand(0);
> +    if (!input->isConstant())
> +        return this;
> +
> +    Value val = input->toConstant()->value();

input->constantValue()

::: js/src/jit/MIR.h
@@ +12880,5 @@
> +{
> +    explicit MAtomicIsLockFree(MDefinition* value, MIRType type)
> +      : MUnaryInstruction(value)
> +    {
> +        setResultType(type);

- Hardcode the value 'type' here. No need to pass it as argument.
- add setMovable().

Comment 12

[Luke Wagner [:luke]]

Comment on attachment 8623544 [details] [diff] [review]
Complete implementation for interpreter, Ion, and Odin, v3

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

Oops, sorry for the delay.

Comment 13

[Lars T Hansen [:lth]]

(In reply to Hannes Verschore [:h4writer] from comment #11)
> Comment on attachment 8623544 [details] [diff] [review]
> Complete implementation for interpreter, Ion, and Odin, v3
> 
> Review of attachment 8623544 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks good. Now I have some possible improvements
> 
> 1) Can't we selfhost this? Creating two JS versions functions where one
> gives true for input 8 and another where false for input 8. And during
> initialization check IsLockFree8 and install the right one? Not sure if that
> last is possible. Might want to discuss this with till. But it seems if that
> is possible, it would require less code and possibly more optimized. (E.g.
> range analysis can run on it, recover instruction would work by default, gvn
> works out of the box ...).

I will not try to do this now, though I see the appeal.  The reason I do not want to do this now is that I think the isLockFree implementation will grow in complexity.  Specifically, I suspect that on ARMv6 and/or MIPS32, which do not have byte and halfword atomic instructions, it may be desirable (for simplicity) to call out to C++ and to do the operation in C++, and the C++ implementation may desire to require a spinlock to do the operation, and in that case isLockFree(1) should be false, for example.  So there may be more variants here.  Suggest we let that evolve, and reconsider later, when we know more.

> 2) If the above is not possible. Can you look into making MIsLockFree
> recoverable? And address the comments raised below.

Will do.

> ::: js/src/jit-test/tests/asm.js/testAtomics.js
> @@ +563,5 @@
> > +    assertEq(misc.ilf5(), 0);
> > +    assertEq(misc.ilf6(), 0);
> > +    assertEq(misc.ilf7(), 0);
> > +    var v = misc.ilf8();
> > +    assertEq(v === 0 || v === 1, true);
> 
> Isn't this a tautology?

No, because the value v could in principle be some other integer value, contrary to the spec.

Comment 14

[Lars T Hansen [:lth]]

Attachment: Complete implementation for interpreter, Ion, and Odin, v4

This is identical to the previous patch except that:

- I addressed the review comments
- I implemented recoverability, which needs review

Comment 15

[Hannes Verschore [:h4writer]]

Comment on attachment 8627659 [details] [diff] [review]
Complete implementation for interpreter, Ion, and Odin, v4

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

Thanks!

::: js/src/jit/MIR.h
@@ +12880,5 @@
>  };
>  
> +class MAtomicIsLockFree
> +  : public MUnaryInstruction,
> +    public IntPolicy<0>::Data

s/IntPolicy/ConvertToInt32Policy/

(This is better. IntPolicy will always bail to the baselinecompiler whenever input is not integer. The convert variant will atleast try to convert it before giving up.)

::: js/src/jit/Recover.cpp
@@ +1510,5 @@
> +
> +bool
> +RAtomicIsLockFree::recover(JSContext* cx, SnapshotIterator& iter) const
> +{
> +    RootedValue operand(cx, iter.read());

MOZ_ASSERT(value.isInt32());

Comment 16

[Lars T Hansen [:lth]]

Try run is again green:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=203a706b70f4

Comment 17

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d8522704ac66

Comment 18

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/d8522704ac66

Comment 19

[Florian Scholz (Open Web Docs)]

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Atomics/isLockFree