[turbofan] Spill rsi and rdi in their existing locations.

[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two
unnecessary stack slots.

This change addresses this issue.

We present these parameters (context and function) to the register
allocator as an UnallocatedOperand having a "secondary storage". The
secondary storage is then associated to the live range as its
spill operand. We capture the definition of the live range so that we can
then commit the spill (in this case, eliminate) through a variation of the
mechanics of the CommitAssignment phase.

The register allocator validator also needed update to understand
UnallocatedOperands with a secondary storage.

The change renames the SpillAtDefinitionList and related APIs to better
capture their intent - the old names suggested spills happened upon
calling. In reality, potential spill locations were thus recorded, and later
committed (or not, in certain cases) after register allocation.

BUG=v8:4548
LOG=n

Committed: https://crrev.com/20f3a0778299c0fd0c6e7ce955a14d800973c152
Cr-Commit-Position: refs/heads/master@{#31988}

[Mircea Trofin, 2015-11-10 23:25:15]

Patchset #3 (id:40001) has been deleted

[Mircea Trofin, 2015-11-11 05:20:36]

Patchset #4 (id:80001) has been deleted

[Jarin, 2015-11-11 09:02:21]

On 2015/11/11 05:20:36, Mircea Trofin wrote:
> Patchset #4 (id:80001) has been deleted

Nice, it is almost what I expected. However, I hoped we would use the
SpillOperand machinery rather than introducing the pre-assigned slot. Could not
we use it? It seemed to me that the SpillOperand machinery for pre-assigned
fixed stack slots does almost what we want. As an added bonus, spill-operands
are not subject to the SpillRange-combining madness.

[Mircea Trofin, 2015-11-12 03:23:04]

Description was changed from

==========
spill rsi and rdi in their existing locations

BUG=
==========

to

==========
We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
==========

[Mircea Trofin, 2015-11-12 03:23:04]

mtrofin@chromium.org changed reviewers:
+ bmeurer@chromium.org, jarin@chromium.org

[Benedikt Meurer, 2015-11-12 04:31:46]

Description was changed from

==========
We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
==========

to

==========
[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
==========

[Benedikt Meurer, 2015-11-12 04:33:26]

Description was changed from

==========
[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
==========

to

==========
[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
LOG=n
==========

[Jarin, 2015-11-12 12:08:33]

I am not sure about this solution; I think I liked your  original version
better. At least the hijacking the two-output Nop seems to be very hacky.

The elidible_def stuff also looks unnatural, but I can believe that something
like that might be necessary (I realize your original patch did not solve this
problem).

Thoughts?

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/instructi...
File src/compiler/instruction-selector.cc (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/instructi...
src/compiler/instruction-selector.cc:1090: InstructionOperand prespilled =
g.DefineAsLocation(
I am mildly surprised that it is possible to define the same node twice. Could
you add a comment here explaining why we do that?

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/linkage.cc
File src/compiler/linkage.cc (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/linkage.c...
src/compiler/linkage.cc:575: // return false;
Remove comment.

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
src/compiler/register-allocator.cc:1630: first->arch_opcode() ==
ArchOpcode::kArchNop && first->OutputCount() == 2;
This looks really brittle because we do not even check that both outputs define
the same vreg. Even then I would not like it because there might be legitimate
reasons for having two operands to ArchNop that have nothing to do with
pre-spilling (and we do not really want to special-case for specific opcodes
here).

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
src/compiler/register-allocator.cc:1664: // delete it.
To be honest, this MarkElidableDef business seems to be quite hacky.

I do not really understand why this is not a problem when we have a normal
fixed-register policy. Would not we then move to the spill slot twice? (Once
with the move on line 1650 and once on line 1677.)

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
src/compiler/register-allocator.h:597: void MarkElidableDef(MoveOperands* move)
{
elidable -> elidible (here and elsewhere)

[Mircea Trofin, 2015-11-12 18:01:35]

I was also a bit unsure about some aspects of this design. In particular,
if ArchNop is used more generally than I thought (see my comment as
response to yours), I'm backing off this design and going back to the 
old one.

I do think we need some concept of "this range is pre-spilled, so don't
spill at definition", but I think I can do it around the spill at definition
list 
and committing spill operands (also see my comments). The only 
remaining thorn is the verifier, I suppose I'll have to teach it about dual 
slot operands.

Thanks!

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/instructi...
File src/compiler/instruction-selector.cc (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/instructi...
src/compiler/instruction-selector.cc:1090: InstructionOperand prespilled =
g.DefineAsLocation(
On 2015/11/12 12:08:33, Jarin wrote:
> I am mildly surprised that it is possible to define the same node twice. Could
> you add a comment here explaining why we do that?

Will do - if we keep this design.

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
src/compiler/register-allocator.cc:1630: first->arch_opcode() ==
ArchOpcode::kArchNop && first->OutputCount() == 2;
On 2015/11/12 12:08:33, Jarin wrote:
> This looks really brittle because we do not even check that both outputs
define
> the same vreg. Even then I would not like it because there might be legitimate
> reasons for having two operands to ArchNop that have nothing to do with
> pre-spilling (and we do not really want to special-case for specific opcodes
> here).

I see. I thought we used ArchNop just for introducing parameters. If that's not
the case, and we don't want to add another opcode (I'd also be weary of doing
that), then we're back to needing the tying info within the operand, which
basically removes most of the reasons for doing this design here, and favors the
previous one.

https://codereview.chromium.org/1426943010/diff/180001/src/compiler/register-...
src/compiler/register-allocator.cc:1664: // delete it.
On 2015/11/12 12:08:33, Jarin wrote:
> To be honest, this MarkElidableDef business seems to be quite hacky.
> 
> I do not really understand why this is not a problem when we have a normal
> fixed-register policy. Would not we then move to the spill slot twice? (Once
> with the move on line 1650 and once on line 1677.)
> 

Here's what happens with a vanilla fixed register: the first move says initially
"v_x = [register]" (line 1650). Line 1677 only schedules a move.
OperandAssigner::CommitAssignment will take care of that. See the call to
TopLevelLiveRange::CommitSpillsAtDefinition from CommitAssignment. First, if
there is no spill operand, there won't be a move to a stack slot, so the move
inserted at line 1650 will either be to the same register, so that will be
elided later (==redundant), or to some other register, so not redundant.

If there are spills, and if the first segment of the live range chain (so the
top level leftover) is spilled, then CommitSpillsAtDefinition won't insert
another move (see the logic around "might_be_duplicated" in
CommitSpillsAtDefinition), and the move resulting from operand assignment
becomes the spill. If the top level isn't spilled, then the move at line 1650 is
to a register (see the paragraph above, same reasoning applies here). So we need
to spill at definition, which will happen in CommitSpillsAtDefinition because,
even if might_be_duplicated, we won't find the matching move.

In our case, we still need the move at line 1650 to define the virtual register.
After that, though, we need to somehow not spill at definition no matter what. 

Now that I think about it, maybe a better concept for the live range would be
"IsPreSpilled". Then, we could still schedule the spill at definition, but then
the logic would be to elide the move in CommitSpillsAtDefinition, instead of
adding a move (so "commit" means in this case "elided").

[Mircea Trofin, 2015-11-12 21:45:14]

Patchset #10 (id:220001) has been deleted

[Mircea Trofin, 2015-11-12 21:45:26]

Patchset #9 (id:200001) has been deleted

[Mircea Trofin, 2015-11-12 23:04:25]

Description was changed from

==========
[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We model the 2 parameters (context and function) as a pair of 
operands - the stack one and the register one. When constructing 
live ranges, we set the stack operand as the live range's spill operand. 
Additionally, we remember the move defining the virtual register (== the
live range). We need the move to keep live ranges canonical throughout
the register allocation pipeline. We remember the move to erase it: if the 
range starts spilled (as it often does), when committing the operand 
assignment, the move will become the redundant spill.

The current patch is a variation of the earlier version of the patch, by 
using a pair of operands rather than a new kind of operand. This was in 
order to make the verifier happy, but it also ended up making the 
change simpler.

BUG= v8:4548
LOG=n
==========

to

==========
[turbofan] Spill rsi and rdi in their existing locations.

We push the context and the js function onto the stack as part of the 
frame construction. The register allocator is presented with virtual
registers for the above as defined from their corresponding registers. It 
then goes on to spilling them somewhere else on the stack.

This means each function spends two redundant spills and two 
unnecessary stack slots.

This change addresses this issue. 

We present these parameters (context and function) to the register
allocator as an UnallocatedOperand having a "secondary storage". The 
secondary storage is then associated to the live range as its  
spill operand. We capture the definition of the live range so that we can
then commit the spill (in this case, eliminate) through a variation of the 
mechanics of the CommitAssignment phase.

The register allocator validator also needed update to understand 
UnallocatedOperands with a secondary storage.

The change renames the SpillAtDefinitionList and related APIs to better
capture their intent - the old names suggested spills happened upon 
calling. In reality, potential spill locations were thus recorded, and later
committed (or not, in certain cases) after register allocation.

BUG= v8:4548
LOG=n
==========

[Jarin, 2015-11-13 15:54:39]

Thanks for the explanation.

lgtm.

https://codereview.chromium.org/1426943010/diff/210011/src/compiler/register-...
File src/compiler/register-allocator-verifier.h (right):

https://codereview.chromium.org/1426943010/diff/210011/src/compiler/register-...
src/compiler/register-allocator-verifier.h:40: kDualLocation
I am wondering whether we should not be more specific here and just say
kRegisterAndSlot.

[Mircea Trofin, 2015-11-13 16:07:18]

https://codereview.chromium.org/1426943010/diff/210011/src/compiler/register-...
File src/compiler/register-allocator-verifier.h (right):

https://codereview.chromium.org/1426943010/diff/210011/src/compiler/register-...
src/compiler/register-allocator-verifier.h:40: kDualLocation
On 2015/11/13 15:54:39, Jarin wrote:
> I am wondering whether we should not be more specific here and just say
> kRegisterAndSlot.

I like that. I'll update.

[Mircea Trofin, 2015-11-13 16:07:29]

The CQ bit was checked by mtrofin@chromium.org

[Mircea Trofin, 2015-11-13 16:07:30]

The patchset sent to the CQ was uploaded after l-g-t-m from jarin@chromium.org
Link to the patchset: https://codereview.chromium.org/1426943010/#ps250001
(title: " ")

[commit-bot: I haz the power, 2015-11-13 16:07:42]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1426943010/250001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1426943010/250001

[commit-bot: I haz the power, 2015-11-13 16:34:27]

Committed patchset #10 (id:250001)

[commit-bot: I haz the power, 2015-11-14 23:21:42]

Patchset 10 (id:??) landed as
https://crrev.com/20f3a0778299c0fd0c6e7ce955a14d800973c152
Cr-Commit-Position: refs/heads/master@{#31988}