Process two 32-bit digits as one 64-bit digit in bigint absAdd intrinsic on x64.

Process two 32-bit digits as one 64-bit digit in bigint absAdd and absSub
intrinsic on x64. More to follow.
Added assembler instructions and tests.

R=zra@google.com

Committed: https://code.google.com/p/dart/source/detail?r=41817

[zra, 2014-11-14 22:11:53]

zra@google.com changed reviewers:
+ zra@google.com

[zra, 2014-11-14 22:11:54]

https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64.cc
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64....
runtime/vm/intrinsifier_x64.cc:868: __ incq(RDX);  // Does not affect carry
flag.
Is it possible to put these incq's and decq's in between the instructions with
memory operands above, adjusting the offsets? I bet it won't help too much, but
it's something to try.

https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64....
runtime/vm/intrinsifier_x64.cc:894: __ incq(RDX);  // Does not affect carry
flag.
Same comment.

[regis, 2014-11-14 22:36:52]

On 2014/11/14 22:11:54, zra wrote:
>
https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64.cc
> File runtime/vm/intrinsifier_x64.cc (right):
> 
>
https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64....
> runtime/vm/intrinsifier_x64.cc:868: __ incq(RDX);  // Does not affect carry
> flag.
> Is it possible to put these incq's and decq's in between the instructions with
> memory operands above, adjusting the offsets? I bet it won't help too much,
but
> it's something to try.
> 
>
https://codereview.chromium.org/732663003/diff/1/runtime/vm/intrinsifier_x64....
> runtime/vm/intrinsifier_x64.cc:894: __ incq(RDX);  // Does not affect carry
> flag.
> Same comment.

Good idea and it makes a difference, but in the wrong direction :-)
It is about 0.5s slower doing it this way:

  __ Bind(&add64_loop);
  // Loop a_used/2 times, R9 = a_used/2, a_used > 0.
  __ movq(RAX, FieldAddress(RDI, RDX, TIMES_4, TypedData::data_offset()));
  __ incq(RDX);  // Does not affect carry flag.
  __ adcq(RAX, FieldAddress(RSI, RDX, TIMES_4, TypedData::data_offset() -
Bigint::kBytesPerDigit));
  __ incq(RDX);  // Does not affect carry flag.
  __ decq(R9);  // Does not affect carry flag.
  __ movq(FieldAddress(RBX, RDX, TIMES_4, TypedData::data_offset() -
2*Bigint::kBytesPerDigit), RAX);
  __ j(NOT_ZERO, &add64_loop, Assembler::kNearJump);

[regis, 2014-11-14 23:42:29]

regis@google.com changed reviewers:
+ iposva@chromium.org

[regis, 2014-11-14 23:42:30]

As suggested earlier, this (patch #2) works much better. The bigint Dart
implementation guarantees that an even number of 32-digits are present, allowing
64-bit processing on X64 and ARM64.

The 64-bit intrinsics do not require the additional code and remain nearly
identical to the 32-bit ones.

The speedup for Fibo on X64 is 25% instead of the 15% of the first approach
(patch #1).

I'll continue in this direction, making sure 32-bit code does not suffer. It
should not.

Thanks,
Regis

[regis, 2014-11-14 23:45:00]

regis@google.com changed reviewers:
+ iposva@google.com
- iposva@chromium.org

[regis, 2014-11-14 23:45:00]

iposva@chromium.org -> iposva@google.com

[regis, 2014-11-18 18:38:29]

This is now ready for review. It was much simpler to modify the Dart code to add
a leading zero.

I will modify absAdd and absSub on arm64 next. Later, I will try the same for
mulAdd and other intrinsics.

PTAL. Thanks.

-- Regis

[zra, 2014-11-18 19:04:46]

Please add assembler tests for the new instructions.

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:215: for (var i = _used + 1; --i >= 0; ) {  // Copy
leading zero.
So, every number has a leading zero? Even those with an even number of digits?

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:246: for (var i = used + 1; --i >= 0; ) {
Would a while loop improve readability here?

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:271: for (var i = _used; --i >= 0; ) {
Same comment

[regis, 2014-11-18 23:19:54]

PTAL

And I painfully added assembler tests :-)

Cheers,
Regis

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:215: for (var i = _used + 1; --i >= 0; ) {  // Copy
leading zero.
On 2014/11/18 19:04:45, zra wrote:
> So, every number has a leading zero? Even those with an even number of digits?

Yes, I figured that the _mulAdd intrinsic (among others) will get called on a
partial number at an odd digit index.

My plan is to change this intrinsic to return the number of processed digits (1
or 2), so it may be possible to keep processing aligned on digit pairs. But for
now, I prefer to always add a leading zero, until this works.

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:246: for (var i = used + 1; --i >= 0; ) {
On 2014/11/18 19:04:45, zra wrote:
> Would a while loop improve readability here?

Done.

https://codereview.chromium.org/732663003/diff/60001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:271: for (var i = _used; --i >= 0; ) {
On 2014/11/18 19:04:45, zra wrote:
> Same comment

Done.

[zra, 2014-11-18 23:24:39]

lgtm!

Thanks for adding the tests =)

[regis, 2014-11-19 00:12:01]

Thanks!

[regis, 2014-11-19 00:12:30]

Committed patchset #7 (id:120001) manually as r41817 (presubmit successful).