Esoteric bit operations.

Esoteric bit operations.

- bit length
- truncate to signed fixed width integer
- truncate to unsigned fixed width integer

This change is motivated by a program that spends 20-30% of its time here:
    // TODO(5828): Replace this with a bit-length method on int when available.
    int n_bitLength = this.n.toRadixString(2).length;


See Also
https://code.google.com/p/dart/issues/detail?id=5828#c3
https://code.google.com/p/dart/issues/detail?id=6486#c2
https://code.google.com/p/dart/issues/detail?id=5798#c5
https://code.google.com/p/dart/issues/detail?id=12008

R=lrn@google.com, srdjan@google.com

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

[Lasse Reichstein Nielsen, 2013-09-06 12:40:11]

LGTM

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.dart
File runtime/lib/integers.dart (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.dart...
runtime/lib/integers.dart:104: return (this & (signMask - 1)) - (this &
signMask);
Clever. I don't see a good way to document why this works, so I guess it'll just
have to be "because it works". :)

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_a...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_a...
runtime/vm/intrinsifier_arm.cc:1075: }
// Intentionally left empty
?

https://codereview.chromium.org/23645003/diff/15001/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/23645003/diff/15001/sdk/lib/core/int.dart#new...
sdk/lib/core/int.dart:147: *                                    ^           ^
If I'm correct then 
  x == x.toSigned(x.bitLength + 1)
always holds.
Is it worth mentioning? I gave me an appreciation of the behavior that wasn't
easy to get just looking at the individual operations.

Is there a relation with toUnsigned as well?

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
File tests/corelib/bit_twiddling_test.dart (right):

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:17: Expect.equals(width, (-i-1).bitLength,
'(~$i).bitLength == $width');
Why -i-1 instead of ~i here? Is it dart2js consideration?

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:72: checkU(0xff, 8, 0xff);
There is no truncating test, and not unsigned->signed test.
How about
  checkU(0xffff, 8, 0xff);
  checkU(-1, 8, 0xff);
Then I prefer to test around known pain points: 31 bit and 32 bit numbers:
  checkU(0x7fffffff, 30, 0x3fffffff);
  checkU(0x7fffffff, 31, 0x7fffffff);
  checkU(0x7fffffff, 32, 0x7fffffff);
  checkU(0x80000000, 30, 0);
  checkU(0x80000000, 31, 0);
  checkU(0x80000000, 32, 0x80000000);
  checkU(0xffffffff, 30, 0x3fffffff);
  checkU(0xffffffff, 31, 0x7fffffff);
  checkU(0xffffffff, 32, 0xffffffff);
  checkU(0x100000000, 30, 0);
  checkU(0x100000000, 31, 0);
  checkU(0x100000000, 32, 0);
  checkU(0x1ffffffff, 30, 0x3fffffff);
  checkU(0x1ffffffff, 31, 0x7fffffff);
  checkU(0x1ffffffff, 32, 0xffffffff);

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:81: checkS(0x80000000, 32, -2147483648);
Similar truncating tests for signed:
  checkS(-1, 3, -1);
  checkS(-0x101, 8, 0);
Maybe some edge cases too.

[srdjan, 2013-09-06 15:35:34]

LGTM with comments

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc
File runtime/lib/integers.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc#n...
runtime/lib/integers.cc:38: static int bitLength(uint64_t value) {
s/bitLength/BitLength/  (Dart vs C++ style)

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc#n...
runtime/lib/integers.cc:42: if (value >= (static_cast<uint64_t>(1) << 32)) {
You can use Utils::IsUint(32, value), also for the rest of the code you may use
some of the helper methods in runtime/platforms/utils.h

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/assembler_ia32.h
File runtime/vm/assembler_ia32.h (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/assembler_ia32...
runtime/vm/assembler_ia32.h:598: void bsrl(Register dst, Register src);
Please also add tests to assembler_xxx_test.cc

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_a...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_a...
runtime/vm/intrinsifier_arm.cc:1074: void Intrinsifier::Smi_bitLength(Assembler*
assembler) {
Add a TODO?

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_i...
File runtime/vm/intrinsifier_ia32.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_i...
runtime/vm/intrinsifier_ia32.cc:1090: void
Intrinsifier::Smi_bitLength(Assembler* assembler) {
How does optimized code compare, is intrinsified method needed at all?

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_m...
File runtime/vm/intrinsifier_mips.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_m...
runtime/vm/intrinsifier_mips.cc:1096: void
Intrinsifier::Smi_bitLength(Assembler* assembler) {
ditto as for ARM

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_x...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_x...
runtime/vm/intrinsifier_x64.cc:1007: void Intrinsifier::Smi_bitLength(Assembler*
assembler) {
ditto

[sra1, 2013-09-06 22:11:57]

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc
File runtime/lib/integers.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc#n...
runtime/lib/integers.cc:38: static int bitLength(uint64_t value) {
On 2013/09/06 15:35:34, srdjan wrote:
> s/bitLength/BitLength/  (Dart vs C++ style)

Done.

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.cc#n...
runtime/lib/integers.cc:42: if (value >= (static_cast<uint64_t>(1) << 32)) {
On 2013/09/06 15:35:34, srdjan wrote:
> You can use Utils::IsUint(32, value), also for the rest of the code you may
use
> some of the helper methods in runtime/platforms/utils.h

Done.

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.dart
File runtime/lib/integers.dart (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/lib/integers.dart...
runtime/lib/integers.dart:104: return (this & (signMask - 1)) - (this &
signMask);
On 2013/09/06 12:40:11, Lasse Reichstein Nielsen wrote:
> Clever. I don't see a good way to document why this works, so I guess it'll
just
> have to be "because it works". :)

I'll give it a shot.

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/assembler_ia32.h
File runtime/vm/assembler_ia32.h (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/assembler_ia32...
runtime/vm/assembler_ia32.h:598: void bsrl(Register dst, Register src);
On 2013/09/06 15:35:34, srdjan wrote:
> Please also add tests to assembler_xxx_test.cc

Done.

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_i...
File runtime/vm/intrinsifier_ia32.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_i...
runtime/vm/intrinsifier_ia32.cc:1090: void
Intrinsifier::Smi_bitLength(Assembler* assembler) {
On 2013/09/06 15:35:34, srdjan wrote:
> How does optimized code compare, is intrinsified method needed at all?

It appears to be worthwhile.
The release build is 6x faster than an instrinsifier that always falls through.
It is also about 1.8x faster than implementing _Smi.bitLength as a sequence of
bit operations and tests in Dart.

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_m...
File runtime/vm/intrinsifier_mips.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_m...
runtime/vm/intrinsifier_mips.cc:1096: void
Intrinsifier::Smi_bitLength(Assembler* assembler) {
On 2013/09/06 15:35:34, srdjan wrote:
> ditto as for ARM

Done.

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_x...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/23645003/diff/15001/runtime/vm/intrinsifier_x...
runtime/vm/intrinsifier_x64.cc:1007: void Intrinsifier::Smi_bitLength(Assembler*
assembler) {
On 2013/09/06 15:35:34, srdjan wrote:
> ditto

Done.

https://codereview.chromium.org/23645003/diff/15001/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/23645003/diff/15001/sdk/lib/core/int.dart#new...
sdk/lib/core/int.dart:147: *                                    ^           ^
On 2013/09/06 12:40:11, Lasse Reichstein Nielsen wrote:
> If I'm correct then 
>   x == x.toSigned(x.bitLength + 1)
> always holds.
> Is it worth mentioning? I gave me an appreciation of the behavior that wasn't
> easy to get just looking at the individual operations.
> 
> Is there a relation with toUnsigned as well?

I added this relation to the documentation.

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
File tests/corelib/bit_twiddling_test.dart (right):

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:17: Expect.equals(width, (-i-1).bitLength,
'(~$i).bitLength == $width');
On 2013/09/06 12:40:11, Lasse Reichstein Nielsen wrote:
> Why -i-1 instead of ~i here? Is it dart2js consideration?

Yes, added comment.

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:72: checkU(0xff, 8, 0xff);
On 2013/09/06 12:40:11, Lasse Reichstein Nielsen wrote:
> There is no truncating test, and not unsigned->signed test.
> How about
>   checkU(0xffff, 8, 0xff);
>   checkU(-1, 8, 0xff);
> Then I prefer to test around known pain points: 31 bit and 32 bit numbers:
>   checkU(0x7fffffff, 30, 0x3fffffff);
>   checkU(0x7fffffff, 31, 0x7fffffff);
>   checkU(0x7fffffff, 32, 0x7fffffff);
>   checkU(0x80000000, 30, 0);
>   checkU(0x80000000, 31, 0);
>   checkU(0x80000000, 32, 0x80000000);
>   checkU(0xffffffff, 30, 0x3fffffff);
>   checkU(0xffffffff, 31, 0x7fffffff);
>   checkU(0xffffffff, 32, 0xffffffff);
>   checkU(0x100000000, 30, 0);
>   checkU(0x100000000, 31, 0);
>   checkU(0x100000000, 32, 0);
>   checkU(0x1ffffffff, 30, 0x3fffffff);
>   checkU(0x1ffffffff, 31, 0x7fffffff);
>   checkU(0x1ffffffff, 32, 0xffffffff);
>   

Done.

https://codereview.chromium.org/23645003/diff/15001/tests/corelib/bit_twiddli...
tests/corelib/bit_twiddling_test.dart:81: checkS(0x80000000, 32, -2147483648);
On 2013/09/06 12:40:11, Lasse Reichstein Nielsen wrote:
> Similar truncating tests for signed:
>   checkS(-1, 3, -1);
>   checkS(-0x101, 8, 0);
> Maybe some edge cases too.

Done.

[sra1, 2013-09-06 22:22:33]

Committed patchset #2 manually as r27269 (presubmit successful).