VM: Support phis with pair representations.

VM: Support phis with pair representations.

This enables unboxed int64 values in phis on 32-bit platforms (ia32, ARM, MIPS).

On ia32 I measured SHA256 +14%, SHA1 +6%, MD5 +2%.

BUG=
R=johnmccutchan@google.com, regis@google.com

Committed: https://github.com/dart-lang/sdk/commit/8adefa8e7969c2ade49699d40bf5b73fc57d517f

[Florian Schneider, 2015-10-01 17:05:39]

fschneider@google.com changed reviewers:
+ johnmccutchan@google.com

[Cutch, 2015-10-01 17:27:42]

Thanks for doing this!

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:814: range = GetLiveRange(vreg);
This code is the same as the first vreg code. Could this be factored into a
helper that takes the vreg?

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:847: bool is_pair_phi =
phi->HasPairRepresentation();
const bool....

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:859: LiveRange* range =
GetLiveRange(ToSecondPairVreg(vreg));
Could you rename range here, it is confusing that you introduce a new "range" in
an inner scope that shadows the outer scope.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:875:
goto_instr->parallel_move()->MoveOperandsAt(move_idx + 1);
More duplicate code- how difficult would be to factor this into a helper and
call with both vregs?

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:886: LiveRange* range =
GetLiveRange(ToSecondPairVreg(vreg));
This shadow of range confused me.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:2203: if
(!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
Factor into another helper routine?

[Florian Schneider, 2015-10-01 18:27:39]

Ptal.

Maybe it's only me - but I found the shadowing helpful when reading the code by
make sure I don't accidentally write "range" where I should use "second_range"
etc.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:814: range = GetLiveRange(vreg);
On 2015/10/01 17:27:41, Cutch wrote:
> This code is the same as the first vreg code. Could this be factored into a
> helper that takes the vreg?

It would need to take vreg, block, interfere_at_backedge, pos, move, phi as
parameters...

I'm not sure it's worth a helper yet.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:847: bool is_pair_phi =
phi->HasPairRepresentation();
On 2015/10/01 17:27:41, Cutch wrote:
> const bool....

Done.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:859: LiveRange* range =
GetLiveRange(ToSecondPairVreg(vreg));
On 2015/10/01 17:27:41, Cutch wrote:
> Could you rename range here, it is confusing that you introduce a new "range"
in
> an inner scope that shadows the outer scope.


Otoh, it prevents from accidentally using the outer range here where is would be
wrong.

I can rename it.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:875:
goto_instr->parallel_move()->MoveOperandsAt(move_idx + 1);
On 2015/10/01 17:27:41, Cutch wrote:
> More duplicate code- how difficult would be to factor this into a helper and
> call with both vregs?

Same as above... I think 2 common lines don't seem to be enough yet.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:886: LiveRange* range =
GetLiveRange(ToSecondPairVreg(vreg));
On 2015/10/01 17:27:41, Cutch wrote:
> This shadow of range confused me.

I can rename it.

https://codereview.chromium.org/1377113004/diff/1/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:2203: if
(!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
On 2015/10/01 17:27:41, Cutch wrote:
> Factor into another helper routine?

Renamed locals like above.

[Cutch, 2015-10-05 17:26:12]

Hi,

You forgot to upload patch set #2

[Florian Schneider, 2015-10-05 17:33:51]

Oops, sorry! Here you are.

[Cutch, 2015-10-05 17:36:12]

lgtm

[Florian Schneider, 2015-10-06 16:19:50]

I fixed mint SHR on MIPS and ARM, and fixed a register allocator issue where I
forgot to add the second pair half of pair-phi inputs to the live-in sets.

[Florian Schneider, 2015-10-06 16:29:48]

fschneider@google.com changed reviewers:
+ regis@google.com

[Florian Schneider, 2015-10-06 16:29:48]

+regis

I fixed mint shift-right on ia32, mips and arm.

[regis, 2015-10-06 17:37:25]

My understanding was that we will never see a constant shift amount >= 64 while
generating mint shifts.
If we do, we will try to shift by >= 32 and the assembler will assert fault.
Did you hit an assert fault? If so, we should had a regression test for it and
we should also fix the left shifts that have the same issue.
If not, some asserts would help documenting the code.

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:844: //   - fit into 32bits range;
update comment?

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_arm.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_arm.cc:6227: __ Asr(out_lo, left_hi,
Operand(31));
The fix looks good if the constant right shift amount can really be >= 64.

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_arm.cc:6242: __ Lsl(out_hi, left_lo,
Operand(shift - 32));
If the constant left shift amount can be >= 64, this needs fixing too.

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_arm.cc:6252: __ cmp(left_lo, Operand(out_hi,
ASR, shift - 32));
ditto

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:6107: __ shll(left_hi, Immediate(shift
- 32));
ditto

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:6119: __ sarl(temp2, Immediate(shift -
32));
ditto

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:6139: __ shll(left_hi, Immediate(shift
- 32));
ditto

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_mips.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_mips.cc:4952: __ sll(out_hi, left_lo, shift -
32);
ditto

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_mips.cc:4962: __ sra(TMP, out_hi, shift - 32);
ditto

[Florian Schneider, 2015-10-07 09:44:11]

I already changed the regression test to cover the right-shift case. It triggers
the assertion failure/crash with illegal instruction or invalid result depending
on the target arch.

Left shifts already work fine. I added ASSERT(shift < 64).

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:844: //   - fit into 32bits range;
On 2015/10/06 17:37:24, regis wrote:
> update comment?

Done.

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_arm.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_arm.cc:6227: __ Asr(out_lo, left_hi,
Operand(31));
On 2015/10/06 17:37:24, regis wrote:
> The fix looks good if the constant right shift amount can really be >= 64.

Yes, the regression test shows that this can be the case. The result of such an
operation is either 0 or -1, so no need to deoptimize.

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/intermediate...
runtime/vm/intermediate_language_arm.cc:6242: __ Lsl(out_hi, left_lo,
Operand(shift - 32));
On 2015/10/06 17:37:24, regis wrote:
> If the constant left shift amount can be >= 64, this needs fixing too.

For left shift the result woud be a bigint in this case.  So we insert a
deoptimize-instructions in the optimizer and won't inline the mint-code next
time. (instead call the operator from IntegerImplementation)

[regis, 2015-10-07 17:23:38]

lgtm

I had missed the update to the test.

Thanks!

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:844: //   - fit into 32bits range;
On 2015/10/07 09:44:11, Florian Schneider wrote:
> On 2015/10/06 17:37:24, regis wrote:
> > update comment?
> 
> Done.

Did not upload updated comment?

[Florian Schneider, 2015-10-08 09:39:26]

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/1377113004/diff/80001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:844: //   - fit into 32bits range;
On 2015/10/07 17:23:38, regis wrote:
> On 2015/10/07 09:44:11, Florian Schneider wrote:
> > On 2015/10/06 17:37:24, regis wrote:
> > > update comment?
> > 
> > Done.
> 
> Did not upload updated comment?

Forgot at first. Added it in patchset #8.

[Florian Schneider, 2015-10-08 09:44:01]

Committed patchset #9 (id:140001) manually as
8adefa8e7969c2ade49699d40bf5b73fc57d517f (presubmit successful).