Use SAR for positive divident by a power-of two constant divisor.

Use SAR for divident by a power-of two constant divisor.
Committed: https://code.google.com/p/dart/source/detail?r=18075

[Florian Schneider, 2013-02-01 11:48:33]

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2035: __ cmpl(left, Immediate(0));
For checking x < 0, this sequence is 1 byte shorter:

__ testl(left, left);
__ j(NEGATIVE, &use_div, Assembler::kNearJump);

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2037: // Positive division by power of
two is an arithmetic left shift.
In the comment s/left/right/.

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2041: __ Bind(&use_div);
I think this could be improved for negative numbers: How about compiling it into
something similar to what gcc generates for integer division by a power of two:

result = left >= 0 
           ? left >> log2(right)
           : (left + (right - 1)) >> log2(right);

It can be further generalized to allow negative powers of two.

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2051: // Check the corner case of
dividing the 'MIN_SMI' with -1, in which
Since the right side is a known constant, you can avoid checking for that corner
case in all cases except when  generating (x ~/ -1).

[srdjan, 2013-02-01 22:57:54]

Improved code, handle negative arguments.

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2037: // Positive division by power of
two is an arithmetic left shift.
On 2013/02/01 11:48:33, Florian Schneider wrote:
> In the comment s/left/right/.

Done.

[Florian Schneider, 2013-02-04 13:04:02]

LGTM!

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12091100/diff/4001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:2041: __ Bind(&use_div);
On 2013/02/01 11:48:33, Florian Schneider wrote:
> I think this could be improved for negative numbers: How about compiling it
into
> something similar to what gcc generates for integer division by a power of
two:
> 
> result = left >= 0 
>            ? left >> log2(right)
>            : (left + (right - 1)) >> log2(right);
> 
> It can be further generalized to allow negative powers of two.

Yes, my mistake: of course the absolute value of right must be used in this
formula.

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2051: if (shift_count > 1) {
Redundant if-statment? shift_count will only be 1 if the rhs value is 1 or -1
here. Those cases are already handled above.

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2055: if (shift_count > 0) {
shift_count will always be > 0 here because kSmiTagSize == 1.

Maybe remove this if-statement and just ASSERT(kSmiTagSize >= 1).

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_x64.cc (right):

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_x64.cc:1908: if (shift_count > 1) {
Same comments as on ia32.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
File tests/language/div_with_power_of_two_test.dart (right):

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:11: TestValue(func, arg) :
function = func, argument = arg, result = func(arg) {}
How do you prevent func from already being optimized at this point? If
optimization_threshold changes, or just adding more test cases may break this
test.

Unfortunately I don't know a good way of generating tests like this in Dart.
Dynamic code generation would help greatly here.

So I think the only reliable way is to list all expected results as constants.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:16: divByNeg4(a) => a ~/ - 4;
Remove extra space after -

/s/- 4/-4/

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:19: 
Please add tests for the special cases:

a ~/ 0
a ~/ 1
a ~/ -1
a ~/ 2
a ~/ -2

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:21: divByNeg4_(a) => a ~/ - 4;
/s/- 4/-4/

[srdjan, 2013-02-04 19:02:33]

Thanks!

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2051: if (shift_count > 1) {
On 2013/02/04 13:04:03, Florian Schneider wrote:
> Redundant if-statment? shift_count will only be 1 if the rhs value is 1 or -1
> here. Those cases are already handled above.

Removed

https://codereview.chromium.org/12091100/diff/17001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2055: if (shift_count > 0) {
On 2013/02/04 13:04:03, Florian Schneider wrote:
> shift_count will always be > 0 here because kSmiTagSize == 1.
> 
> Maybe remove this if-statement and just ASSERT(kSmiTagSize >= 1).

Done.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
File tests/language/div_with_power_of_two_test.dart (right):

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:11: TestValue(func, arg) :
function = func, argument = arg, result = func(arg) {}
On 2013/02/04 13:04:03, Florian Schneider wrote:
> How do you prevent func from already being optimized at this point? If
> optimization_threshold changes, or just adding more test cases may break this
> test.
> 
> Unfortunately I don't know a good way of generating tests like this in Dart.
> Dynamic code generation would help greatly here.
> 
> So I think the only reliable way is to list all expected results as constants.

Added expected values as well.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:16: divByNeg4(a) => a ~/ - 4;
On 2013/02/04 13:04:03, Florian Schneider wrote:
> Remove extra space after -
> 
> /s/- 4/-4/

Done.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:19: 
On 2013/02/04 13:04:03, Florian Schneider wrote:
> Please add tests for the special cases:
> 
> a ~/ 0
> a ~/ 1
> a ~/ -1
> a ~/ 2
> a ~/ -2

Done.

https://codereview.chromium.org/12091100/diff/17001/tests/language/div_with_p...
tests/language/div_with_power_of_two_test.dart:21: divByNeg4_(a) => a ~/ - 4;
On 2013/02/04 13:04:03, Florian Schneider wrote:
> /s/- 4/-4/

Done.