Range feedback for binary integer operations.

Range feedback for arithmetic operations.

In addition to tracking input and output ranges in the IC-stubs with a Smi fastpath (SmiAdd and SmiSub, currently) this CL also introduces two IC stubs that have no fast-path by still track ranges and update the range feedback.

We are able to distinguish between the following ranges (encoding of the lattice is shown in the parens):

- u-smi  (0000)
- smi    (0001)
- uint31 (0010)
- int32  (0011)
- uint32 (0100)
- int64  (1xxx) and (x1x1)

BUG=
R=fschneider@google.com, srdjan@google.com, zra@google.com

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

[Vyacheslav Egorov (Google), 2014-12-11 03:34:34]

vegorov@google.com changed reviewers:
+ fschneider@google.com, srdjan@google.com, zra@google.com

[Vyacheslav Egorov (Google), 2014-12-11 03:35:14]

PTAL

This is ready for the review.

Feedback is just gathered, it is not used for optimizations yet.

[zra, 2014-12-11 04:29:33]

I'll take a closer look tomorrow, as well.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm.cc
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm.cc:1972: Operand(scratch1, LSL,
ICData::kBitsPerRangeFeedback * idx));
Maybe assert that (ICData::kBitsPerRangeFeedback * idx) < 32?

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm.h
File runtime/vm/assembler_arm.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm.h:714: void ComputeRange(Register result,
Should this be private?

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_arm.cc
File runtime/vm/stub_code_arm.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_arm...
runtime/vm/stub_code_arm.cc:1345: Label not_smi_or_overflow;
What is the effect of this change on unoptimized code performance?

[Vyacheslav Egorov (Google), 2014-12-11 13:06:25]

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm.cc
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm.cc:1972: Operand(scratch1, LSL,
ICData::kBitsPerRangeFeedback * idx));
On 2014/12/11 04:29:33, zra wrote:
> Maybe assert that (ICData::kBitsPerRangeFeedback * idx) < 32?

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm.h
File runtime/vm/assembler_arm.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm.h:714: void ComputeRange(Register result,
On 2014/12/11 04:29:33, zra wrote:
> Should this be private?

If I make it private I can't easily test this without allocating ICData.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_arm.cc
File runtime/vm/stub_code_arm.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_arm...
runtime/vm/stub_code_arm.cc:1345: Label not_smi_or_overflow;
On 2014/12/11 04:29:33, zra wrote:
> What is the effect of this change on unoptimized code performance?

There are no visible regression on the dart2js compilation time. 

With optimizer disabled there is ~2% regression on Richards on 32-bit platforms
(both ia32 and ARM), there is a ~8-10% regression on x64 (it's higher on x64
because Smi is not longer on the fast path).

Overall it seems acceptable given the code quality improvements that we can get
from this for arithmetic.

[Florian Schneider, 2014-12-12 12:12:40]

The resulting range feedback is different on ia32 vs x64:

On x64 smi-ness won't be tracked (since it's 63-bit).

I wonder if we should only track machine-word sizes on all platforms: It depends
on how the code using the range information looks like. (i.e. if it is also
platform-specific. Also, smi-ness for inputs is already tracked already by the
exisiting type feedback.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_ia3...
File runtime/vm/assembler_ia32.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_ia3...
runtime/vm/assembler_ia32.cc:1500: void Assembler::orl(const Address& address,
Register reg) {
Please add a test to assember cc tests.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_x64.h
File runtime/vm/assembler_x64.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_x64...
runtime/vm/assembler_x64.h:533: 
Remove extra \n.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
File runtime/vm/stub_code_ia32.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
runtime/vm/stub_code_ia32.cc:1286: __ int3();
Redundant int3?

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
runtime/vm/stub_code_ia32.cc:1443: __ int3();
Redundant int3.

[Vyacheslav Egorov (Google), 2014-12-12 14:49:14]

Comments addressed. I have changed the tracking on 64-bit platforms to track
smis correctly and not set kInt64Bit for them. We don't track the sign however
because it is not important for kUint32Range - kInt32Range distinction. 

I have fixed DecodeRangeFeedback with respect to kSignBit | kUint32Bit state
decoding - on 32-bit platforms it is kInt64Range, but on 64-bit platform it is
kSmiRange still.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_ia3...
File runtime/vm/assembler_ia32.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_ia3...
runtime/vm/assembler_ia32.cc:1500: void Assembler::orl(const Address& address,
Register reg) {
On 2014/12/12 12:12:40, Florian Schneider wrote:
> Please add a test to assember cc tests.

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_x64.h
File runtime/vm/assembler_x64.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/assembler_x64...
runtime/vm/assembler_x64.h:533: 
On 2014/12/12 12:12:40, Florian Schneider wrote:
> Remove extra \n.

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
File runtime/vm/stub_code_ia32.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
runtime/vm/stub_code_ia32.cc:1286: __ int3();
On 2014/12/12 12:12:40, Florian Schneider wrote:
> Redundant int3?

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/stub_code_ia3...
runtime/vm/stub_code_ia32.cc:1443: __ int3();
On 2014/12/12 12:12:40, Florian Schneider wrote:
> Redundant int3.

Done.

[Vyacheslav Egorov (Google), 2014-12-15 13:00:51]

friendly ping

[zra, 2014-12-15 16:01:41]

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
File runtime/vm/assembler_arm64_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm64_test.cc:3531: __ Push(LR);
If there's no call, I don't think you need to push LR.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
File runtime/vm/assembler_arm_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm_test.cc:4220: __ PushList(1 << LR);
Same comment.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_mip...
File runtime/vm/assembler_mips_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_mip...
runtime/vm/assembler_mips_test.cc:2072: __ sw(RA, Address(SP, 0 * kWordSize));
Same comment.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2906:
compiler->GenerateInstanceCall(deopt_id(),
indentation

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/object.h#newc...
runtime/vm/object.h:3812: kIssuedJSWarningBit = kDeoptReasonPos +
kDeoptReasonSize,
If we didn't need to encode so many deopt reasons, then you could put the range
feedback in state_bits_.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/stub_code_arm.cc
File runtime/vm/stub_code_arm.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/stub_code_arm...
runtime/vm/stub_code_arm.cc:1376: __ LoadTaggedClassIdMayBeSmi(R0, R0);
If you can move UpdateRangeFeedback after loading the class id here, then you
might be able to avoid loading the class id twice.

[srdjan, 2014-12-15 16:39:01]

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc#new...
runtime/vm/object.cc:11952: static Token::Kind RecognizeArithmeticOp(const
String& name) {
ASSERT(name.IsSymbol()).

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc#new...
runtime/vm/object.cc:12002: if (cid != kSmiCid && cid != kMintCid) {
Add parentheses

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.h#newc...
runtime/vm/object.h:3737: };
I think it would be more readable to say, e.g., kInt32RangeBit.

[Vyacheslav Egorov (Google), 2014-12-15 17:20:05]

Thanks for the comments. Address addressable ones.

Biggest concern now is that we increase on 64-bit architectures the size of
ICData by 2 words.

We have many bits wasted on tracking deopt reasons as pointed by Zach so we can
reclaim 12 bits from there for range information - because most of those reasons
are tracked for nothing to begin with. 

I am not sure if we want to do this right away (i.e. stop tracking reasons that
are not interesting for optimizer) or it is acceptable to do it in a separate
CL.

I would prefer separate CL.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc#new...
runtime/vm/object.cc:11952: static Token::Kind RecognizeArithmeticOp(const
String& name) {
On 2014/12/15 16:39:01, srdjan wrote:
> ASSERT(name.IsSymbol()).

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.cc#new...
runtime/vm/object.cc:12002: if (cid != kSmiCid && cid != kMintCid) {
On 2014/12/15 16:39:01, srdjan wrote:
> Add parentheses

Done.

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/735543003/diff/20001/runtime/vm/object.h#newc...
runtime/vm/object.h:3737: };
On 2014/12/15 16:39:01, srdjan wrote:
> I think it would be more readable to say, e.g., kInt32RangeBit.

Done.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
File runtime/vm/assembler_arm64_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm64_test.cc:3531: __ Push(LR);
On 2014/12/15 16:01:40, zra wrote:
> If there's no call, I don't think you need to push LR.

Done.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
File runtime/vm/assembler_arm_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_arm...
runtime/vm/assembler_arm_test.cc:4220: __ PushList(1 << LR);
On 2014/12/15 16:01:40, zra wrote:
> Same comment.

Done.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_mip...
File runtime/vm/assembler_mips_test.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/assembler_mip...
runtime/vm/assembler_mips_test.cc:2072: __ sw(RA, Address(SP, 0 * kWordSize));
On 2014/12/15 16:01:40, zra wrote:
> Same comment.

Done.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2906:
compiler->GenerateInstanceCall(deopt_id(),
On 2014/12/15 16:01:40, zra wrote:
> indentation

Done.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/object.h#newc...
runtime/vm/object.h:3812: kIssuedJSWarningBit = kDeoptReasonPos +
kDeoptReasonSize,
On 2014/12/15 16:01:41, zra wrote:
> If we didn't need to encode so many deopt reasons, then you could put the
range
> feedback in state_bits_.

We actually don't need most of the deopt reasons. They are not used anywhere -
but in printing during deopt itself. Some deopts reasons are recorded and used
in the optimizer to avoid repetitive wrong speculations... With *this* change
we'll can get rid of them, but first we will need to start using range feedback
in the optimizer - and then we can kill those deopt reasons that exist purely to
avoid repetitive deopt.

On ia32 we don't change the size, because there is a one words of padding
already.

It is true however that on 64-bit platforms we will increase ICData size by 2
words with this change, which is *quite* unfortunate. To be honest, somehow I
miscounted words when I was checking this, and now that I verified my
calculations I can see that there is no free space on x64/arm64 inside the
RawICData.

If you have any idea where to fold it into - I am open for suggestions.
Otherwise, I suggest we can do it later once we kill tracking of those deopt
reasons that are not used for anything and free up space.

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/stub_code_arm.cc
File runtime/vm/stub_code_arm.cc (right):

https://codereview.chromium.org/735543003/diff/40001/runtime/vm/stub_code_arm...
runtime/vm/stub_code_arm.cc:1376: __ LoadTaggedClassIdMayBeSmi(R0, R0);
On 2014/12/15 16:01:41, zra wrote:
> If you can move UpdateRangeFeedback after loading the class id here, then you
> might be able to avoid loading the class id twice.

I am really not sure if it is worth it, to micro-optimize this at this stage. We
are talking about speeding up either Mint case which has no fast path and
requires allocation anyway to produce result or about speeding up case when
somebody overrides arithmetic operations. Neither of this, if you ask me, looks
like a priority to me - optimizer is there to deal with this.

It is true that by re-arranding the code in various ways I can save on various
checks (e.g. repetetive smi check), but I don't think it is worth it.

After all regression on ARM on unoptimized Richards is only around ~1% (and
Richards is actually quite a bit of arithmetic ops)

[srdjan, 2014-12-15 17:26:33]

LGTM

[zra, 2014-12-15 17:32:16]

lgtm

On 2014/12/15 17:20:05, Vyacheslav Egorov (Google) wrote:
> I am not sure if we want to do this right away (i.e. stop tracking reasons
that
> are not interesting for optimizer) or it is acceptable to do it in a separate
> CL.
> 
> I would prefer separate CL.

sgtm

[Florian Schneider, 2014-12-15 17:48:46]

lgtm

[Vyacheslav Egorov (Google), 2014-12-15 18:48:43]

Committed patchset #4 (id:60001) manually as 42370 (presubmit successful).