[wasm] Refactor the non-determinism detection in the interpreter.

[wasm] Refactor the non-determinism detection in the interpreter.

Apparently it happens quite easily that different NaNs are produced in
the interpreter than in the execution of the compiled code. This
non-determinism caused problems for the fuzzer which compares the
equality of the results of the interpreter and the compiled code.

I decided therefore to refactor the detection of non-determinism in the
interpreter. Instead of tracking whether potentially non-deterministic
NaNs were produced, I track now whether potentially non-deterministic
NaNs could have been observed. The only way the NaN non-determinism can
be observed is by observing the non-deterministic bit pattern of the
NaN. AFAICT the only way to observe the bit pattern is with a
I(32|64)_REINTERPRET_F(32|64) instruction or with a F(32|64)_STORE
followed by a load. Therefore I flag an execution as potentially
non-deterministic when either a NaN is reinterpreted to an int, or when
a NaN is stored to memory.

R=titzer@chromium.org, eholk@chromium.org
BUG=682180
Review-Url: https://codereview.chromium.org/2671803002
Cr-Commit-Position: refs/heads/master@{#42917}
Committed: https://chromium.googlesource.com/v8/v8/+/ac187c03230980c4bb8950851d8f2bbda78d3cd2

[ahaas, 2017-02-02 20:16:39]

The CQ bit was checked by ahaas@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-02 20:16:45]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-02 20:41:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-02 20:41:50]

Dry run: This issue passed the CQ dry run.

[Eric Holk, 2017-02-03 03:11:27]

lgtm

Somehow I suspect the fuzzer will still be clever enough to defeat this, but I
guess only time can tell. I can't think of a way around it right now.

https://codereview.chromium.org/2671803002/diff/1/src/wasm/wasm-interpreter.cc
File src/wasm/wasm-interpreter.cc (right):

https://codereview.chromium.org/2671803002/diff/1/src/wasm/wasm-interpreter.c...
src/wasm/wasm-interpreter.cc:1177: template <typename ctype, typename mtype>
I like the template approach way better than preprocessor macros!

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
File test/cctest/wasm/test-run-wasm-interpreter.cc (left):

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
test/cctest/wasm/test-run-wasm-interpreter.cc:384: BUILD(r,
WASM_F64_SQRT(WASM_GET_LOCAL(0)));
Wouldn't there still be some value in testing sqrt and the other ways of getting
NaN to make sure we're detecting all of it?

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
File test/cctest/wasm/test-run-wasm-interpreter.cc (right):

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
test/cctest/wasm/test-run-wasm-interpreter.cc:347: BUILD(r,
WASM_I32_REINTERPRET_F32(WASM_GET_LOCAL(0)));
Can't we still have nondeterminism if the function returns a float? Or will it
just not matter because it will still be a NaN?

[ahaas, 2017-02-03 09:06:02]

The CQ bit was checked by ahaas@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-03 09:06:13]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[ahaas, 2017-02-03 09:16:06]

PTAL. Also the copysign instructions allow you to observe the non-determinism of
NaNs.

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
File test/cctest/wasm/test-run-wasm-interpreter.cc (left):

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
test/cctest/wasm/test-run-wasm-interpreter.cc:384: BUILD(r,
WASM_F64_SQRT(WASM_GET_LOCAL(0)));
On 2017/02/03 at 03:11:26, Eric Holk wrote:
> Wouldn't there still be some value in testing sqrt and the other ways of
getting NaN to make sure we're detecting all of it?

The possible_nondeterminism flag causes us to not compare the result of the
interpreter with the result of the compiled code in the fuzzer. Therefore we
should only set the flag when it is really necessary. If you can still think of
a value which is worth more than better correctness fuzzing, then we can
definitely extend the use of the possible_nondeterminism flag again.

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
File test/cctest/wasm/test-run-wasm-interpreter.cc (right):

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
test/cctest/wasm/test-run-wasm-interpreter.cc:347: BUILD(r,
WASM_I32_REINTERPRET_F32(WASM_GET_LOCAL(0)));
On 2017/02/03 at 03:11:26, Eric Holk wrote:
> Can't we still have nondeterminism if the function returns a float? Or will it
just not matter because it will still be a NaN?

Non-determinism by itself does not hurt us as long as it does not change the
result of the function. The fuzzer can deal easily with different NaNs.

[commit-bot: I haz the power, 2017-02-03 09:30:04]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-03 09:30:06]

Dry run: This issue passed the CQ dry run.

[titzer, 2017-02-03 09:48:05]

lgtm

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
File test/cctest/wasm/test-run-wasm-interpreter.cc (left):

https://codereview.chromium.org/2671803002/diff/1/test/cctest/wasm/test-run-w...
test/cctest/wasm/test-run-wasm-interpreter.cc:384: BUILD(r,
WASM_F64_SQRT(WASM_GET_LOCAL(0)));
On 2017/02/03 09:16:06, ahaas wrote:
> On 2017/02/03 at 03:11:26, Eric Holk wrote:
> > Wouldn't there still be some value in testing sqrt and the other ways of
> getting NaN to make sure we're detecting all of it?
> 
> The possible_nondeterminism flag causes us to not compare the result of the
> interpreter with the result of the compiled code in the fuzzer. Therefore we
> should only set the flag when it is really necessary. If you can still think
of
> a value which is worth more than better correctness fuzzing, then we can
> definitely extend the use of the possible_nondeterminism flag again.

I think Andreas is saying that we do actually test NaN-producing inputs, it's
just that we don't test non-deterministic programs, and programs can only be
non-deterministic if they somehow _observe_ the NaN bit pattern itself.

[ahaas, 2017-02-03 09:49:26]

The CQ bit was checked by ahaas@chromium.org

[ahaas, 2017-02-03 09:49:27]

The patchset sent to the CQ was uploaded after l-g-t-m from eholk@chromium.org
Link to the patchset: https://codereview.chromium.org/2671803002/#ps20001
(title: "Also adjust copysign")

[commit-bot: I haz the power, 2017-02-03 09:49:28]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-03 09:51:04]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1486115366898820,
"parent_rev": "994d906ec3b3479ba1b9a0ebd23c9efcbea6806f", "commit_rev":
"ac187c03230980c4bb8950851d8f2bbda78d3cd2"}

[commit-bot: I haz the power, 2017-02-03 09:51:11]

Description was changed from

==========
[wasm] Refactor the non-determinism detection in the interpreter.

Apparently it happens quite easily that different NaNs are produced in
the interpreter than in the execution of the compiled code. This
non-determinism caused problems for the fuzzer which compares the
equality of the results of the interpreter and the compiled code.

I decided therefore to refactor the detection of non-determinism in the
interpreter. Instead of tracking whether potentially non-deterministic
NaNs were produced, I track now whether potentially non-deterministic
NaNs could have been observed. The only way the NaN non-determinism can
be observed is by observing the non-deterministic bit pattern of the
NaN. AFAICT the only way to observe the bit pattern is with a
I(32|64)_REINTERPRET_F(32|64) instruction or with a F(32|64)_STORE
followed by a load. Therefore I flag an execution as potentially
non-deterministic when either a NaN is reinterpreted to an int, or when
a NaN is stored to memory.

R=titzer@chromium.org, eholk@chromium.org
BUG=682180
==========

to

==========
[wasm] Refactor the non-determinism detection in the interpreter.

Apparently it happens quite easily that different NaNs are produced in
the interpreter than in the execution of the compiled code. This
non-determinism caused problems for the fuzzer which compares the
equality of the results of the interpreter and the compiled code.

I decided therefore to refactor the detection of non-determinism in the
interpreter. Instead of tracking whether potentially non-deterministic
NaNs were produced, I track now whether potentially non-deterministic
NaNs could have been observed. The only way the NaN non-determinism can
be observed is by observing the non-deterministic bit pattern of the
NaN. AFAICT the only way to observe the bit pattern is with a
I(32|64)_REINTERPRET_F(32|64) instruction or with a F(32|64)_STORE
followed by a load. Therefore I flag an execution as potentially
non-deterministic when either a NaN is reinterpreted to an int, or when
a NaN is stored to memory.

R=titzer@chromium.org, eholk@chromium.org
BUG=682180

Review-Url: https://codereview.chromium.org/2671803002
Cr-Commit-Position: refs/heads/master@{#42917}
Committed:
https://chromium.googlesource.com/v8/v8/+/ac187c03230980c4bb8950851d8f2bbda78...
==========

[commit-bot: I haz the power, 2017-02-03 09:51:13]

Committed patchset #2 (id:20001) as
https://chromium.googlesource.com/v8/v8/+/ac187c03230980c4bb8950851d8f2bbda78...