corelib_2/bigint_from_test fails on vm-linux-release-ia32-optcounter-threshold-be

[zanderso]

/cc @lrhn @crelier @alexmarkov

=== Failure summary:
FAILED: none-vm-checked release_ia32 corelib_2/bigint_from_test
Expected: Pass
Actual: RuntimeError
--- Command "vm" (took 710ms):
DART_CONFIGURATION=ReleaseIA32 out/ReleaseIA32/dart --enable_asserts --enable_type_checks --optimization-counter-threshold=5 --reify-generic-functions --limit-ints-to-64-bits --sync-async --ignore-unrecognized-flags --packages=/mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/.packages /mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/tests/corelib_2/bigint_from_test.dart
exit code:
255
stderr:
Unhandled exception:
Expect.equals(expected: <-4294967297>, actual: <-3221225473>) fails.
#0      Expect._fail (package:expect/expect.dart:566:5)
#1      Expect.equals (package:expect/expect.dart:121:7)
#2      testInt (file:///mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/tests/corelib_2/bigint_from_test.dart:61:10)
#3      main (file:///mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/tests/corelib_2/bigint_from_test.dart:14:5)
#4      _startIsolate.<anonymous closure> (dart:isolate-patch/dart:isolate/isolate_patch.dart:279)
#5      _RawReceivePortImpl._handleMessage (dart:isolate-patch/dart:isolate/isolate_patch.dart:165)
--- Re-run this test:
python tools/test.py -m release -a ia32 --checked --vm-options --optimization-counter-threshold=5 corelib_2/bigint_from_test

[alexmarkov]

The test works in default mode, and doesn't work on ia32 if '--optimization-counter-threshold=5' option is specified. This is a miscompilation in VM.

Smaller example, independent of BigInt:

import "package:expect/expect.dart";
import 'dart:typed_data';

main() {
  var multiplicandDigits = new Uint32List.fromList([0, 294967296, 0, 0]);
  var accumulatorDigits = new Uint32List.fromList([0, 4, 4, 0, 0, 0]);

  var d1 = _mulAdd(multiplicandDigits, 0, accumulatorDigits, 0, 2);

  Expect.equals(0, d1);
}

const int _digitBits = 32;
const int _digitMask = (1 << _digitBits) - 1;

const int _halfDigitBits = _digitBits >> 1;
const int _halfDigitMask = (1 << _halfDigitBits) - 1;

int _mulAdd(Uint32List multiplicandDigits, int i, Uint32List accumulatorDigits,
    int j, int n) {
  int carry = 0;
  while (--n >= 0) {
    int ml = multiplicandDigits[i] & _halfDigitMask;
    int mh = multiplicandDigits[i++] >> _halfDigitBits;
    int ph = mh * 4;
    int q1 = ((ph & _halfDigitMask) << _halfDigitBits);
    int pl = 4 * ml + q1 + accumulatorDigits[j];
    carry = (pl >> _digitBits) + (ph >> _halfDigitBits);
    accumulatorDigits[j++] = pl & _digitMask;
  }

  return carry;
}

$ out/ReleaseIA32/dart --no-background-compilation foo.dart
$ out/ReleaseIA32/dart --optimization-counter-threshold=5 --no-background-compilation foo.dart
Unhandled exception:
Expect.equals(expected: <0>, actual: <-1>) fails.
#0      Expect._fail (package:expect/expect.dart:566:5)
#1      Expect.equals (package:expect/expect.dart:124:5)
#2      main (file:///usr/local/google/home/alexmarkov/work/dart/sdk/foo.dart:14:10)
#3      _startIsolate.<anonymous closure> (dart:isolate-patch/dart:isolate/isolate_patch.dart:279)
#4      _RawReceivePortImpl._handleMessage (dart:isolate-patch/dart:isolate/isolate_patch.dart:165)

Miscompilation happens due to WidenSmiToInt32 pass in _mulAdd method. WidenSmiToInt32 pass is only used on 32-bit platforms.
This pass converts IL

    v55 <- BinarySmiOp:44(+, v51, v79 T{_Smi}) T{_Smi}
    v58 <- BinarySmiOp:46(>>, v55, v57) T{_Smi}

to

    v55 <- BinaryInt32Op:44(+, v51, v79 T{_Smi})
    v58 <- BinarySmiOp:46(>>, v55, v57) T{_Smi}

Later, result of BinaryInt32Op is boxed:

    v55 <- BinaryInt32Op:44(+, v51, v109 T{_Smi})
    v115 <- BoxInt32(v55)
    v58 <- BinarySmiOp:46(>>, v115, v57) T{_Smi}

The problem is that there is a missing CheckSmi for v115.
In this particular example after widening BinaryInt32Op produced result which fits into int32, but does not fit into smi and BoxInt32 created a Mint box. Then, BinarySmiOp used address of the box without checking if it is a smi.

/cc @mraleph

[mraleph]

I suspect the problem is at this line:

    Definition* boxed = BoxInstr::Create(from, use->CopyWithType());

we probably have stale type on the use.

No, disregard this: we do clear type.

[alexmarkov]

Types on uses of BinaryInt32Op are cleared in WidenSmiToInt32 (v115 doesn't have a type in flow graph snippet above). Also, I don't see anything wrong with BoxInt32 - it works as expected.

I think the problem is a missing CheckSmi for pre-existing BinarySmiOp which now uses BinaryInt32Op/BoxInt32 after widening. It looks like we don't insert CheckSmi when selecting representations or during widening - only when specializing calls and in inliner.

@mraleph, can you clarify your point?

[mraleph]

Yes, my first thought was wrong.

I think your analysis is correct - optimization does not account for the fact that widening alters the range of the operation, which means that it potentially "invalidates" the code that uses the value.

So widening needs to be safe with respect to uses.

I think we should just disable this optimization for now and work on replacing it with a proper solution.

[aam]

The test "magically" started to pass since https://ci.chromium.org/buildbot/client.dart/vm-linux-release-ia32-optcounter-threshold-be/10024.

=== Failure summary:
FAILED: none-vm-checked release_ia32 corelib_2/bigint_from_test
Expected: RuntimeError
Actual: Pass
--- Command "vm" (took 792ms):
DART_CONFIGURATION=ReleaseIA32 out/ReleaseIA32/dart --enable_asserts --enable_type_checks --optimization-counter-threshold=5 --reify-generic-functions --limit-ints-to-64-bits --sync-async --ignore-unrecognized-flags --packages=/mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/.packages /mnt/data/b/build/slave/vm-linux-release-ia32-optcounter-threshold-be/build/sdk/tests/corelib_2/bigint_from_test.dart
exit code:
0
--- Re-run this test:
python tools/test.py -m release -a ia32 --checked --builder-tag optimization_counter_threshold --vm-options --optimization-counter-threshold=5 corelib_2/bigint_from_test
===
=== 1 test failed
===
--- Total time: 29:28 ---

Any ideas why?

It passes on my local machine too.

[alexmarkov]

CL to disable widening: https://dart-review.googlesource.com/c/sdk/+/47661
With this optimization disabled, several benchmarks regressed on ia32:

RSA-custom-bigint -18.89%
CryptoDecrypt -28.09%
CryptoEncrypt -22.44%

/cc @mraleph

[mraleph]

I am not surprised that some things regressed - we did implement it for a reason.

I think it is worth investing in reimplementation of this optimization, but I would like us to do it as part of a cohesive strategy for optimizing integer arithmetic - right now we have a patch work of different things.

[alexmarkov]

@aam, the original reproduction relied on BigInt code which was changed in f2806ab. I'm not able to reproduce the problem using corelib_2/bigint_from_test test after that change. So I think we can update the status file to make bot green again.

The problem with incorrect optimization is still there, and it can be reproduced with regression test which I extracted from BigInt code (see https://dart-review.googlesource.com/c/sdk/+/47661). So this issue is still open.

[crelier]

@alexmarkov, f2806ab reenabled intrinsics, probably bypassing the Dart code that is improperly optimized. You could try to pass the flag --no-intrinsify to see if the issue reappears.