Subzero: Allow deeper levels of variable splitting.

Subzero: Allow deeper levels of variable splitting.

This fixes some existing problems with the Variable::LinkedTo splitting/linking mechanism.  The problem was that if B is linked to A, and B needs a stack slot, but A doesn't get a stack slot, B's stack offset would never get initialized.  This could happen if A ends up with no explicit references in the code, or A's live range gets truncated such that it actually has a register while B doesn't.

It gets even more complicated if you have a link chain like A<--B<--C<--D etc. where some of them have stack slots (which should ultimately all be the same slot) and some don't.

The solution here is that if B is linked to the root A, and B has a stack slot but A doesn't, we can do a tree rotation so that B is the new root and A links to B.

In addition, we initialize Variable::StackOffset to an invalid value and always make sure a value used is valid.  Earlier attempts at extending the variable splitting would sometimes silently fail because the default StackOffset value of 0 ended up being used.

BUG= none
R=jpp@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=fe62f0a229a7b2bc910eb8b7cb83d2534ed39343

[Jim Stichnoth, 2016-07-02 19:12:52]

Description was changed from

==========
Subzero: Allow deeper levels of variable splitting.

BUG= none
==========

to

==========
Subzero: Allow deeper levels of variable splitting.

This fixes some existing problems with the Variable::LinkedTo splitting/linking
mechanism.  The problem was that if B is linked to A, and B needs a stack slot,
but A doesn't get a stack slot, B's stack offset would never get initialized. 
This could happen if A ends up with no explicit references in the code, or A's
live range gets truncated such that it actually has a register while B doesn't.

It gets even more complicated if you have a link chain like A<--B<--C<--D etc.
where some of them have stack slots (which should ultimately all be the same
slot) and some don't.

The solution here is that if B is linked to the root A, and B has a stack slot
but A doesn't, we can do a tree rotation so that B is the new root and A links
to B.

In addition, we initialize Variable::StackOffset to an invalid value and always
make sure a value used is valid.  Earlier attempts at extending the variable
splitting would sometimes silently fail because the default StackOffset value of
0 ended up being used.

BUG= none
==========

[Jim Stichnoth, 2016-07-02 19:13:12]

stichnot@chromium.org changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com, manasijm@google.com

[John, 2016-07-06 16:07:39]

https://codereview.chromium.org/2116213002/diff/20001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1101: if (Dest->getStackOffset() == SrcVar->getStackOffset()) {
I would do:

if (Dest.StackOffset != Src.StackOffset)
  return false;

return true;

up to you

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:699: static constexpr int32_t InvalidStackOffset = -1;
maybe put this in the private: section?

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:787: if (Root == nullptr)
so this is

if (Root == nullptr) return nullptr;

right? I'd spell out nullptr instead.

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:790: Root = Root->LinkedTo;
Why not

if (Root->LinkedTo != nullptr) {
  return Root->getLinkedToRoot();
}

return Root;

?

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:589: //  - Var's furthest ancestor through LinkedTo:
Root
Instead of Root, did you mean Ancestor?

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:596: if (!IsVarReferenced[Var->getIndex()])
It took me a while to understand what this is doing. Yes, I know the comments
says exactly what this is supposed to do, but comments aren't checked by the
compiler -- and they might rot.

It would be clearer (to me) if you created a helper function:

def MightBeSpilled(Var):
  return false if Var is not referenced, else
  return false if Var has a register, else
  return true

and then this loop is changed to use the helper function:

if (!MightBeSpilled(Var))
  continune;
if (auto *Ancestor = Var->getLinkedToRoot()) {
  if (MightBeSpilled(Ancestor)) {
    // No need to rotate the tree.
    continue;
  }
  Var->setLinkedTo(nullptr); // break the cycle before it happens!
  Ancestor->setLinkedTo(Var);
}

Now, looking at this (hopefully) equivalent implementation, I wonder...

Imagine the following linked to chain:

A --- linked to ---> B --- linked to ---> C

If A is spilled, what forces C to be spilled?

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:600: Variable *Ancestor = Var->getLinkedToRoot();
auto?

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:951: } else if (Offset) {
I prefer

if (Offset != 0),

but up to you.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:1209: const Variable *Linked =
Var->getLinkedToRoot();
Consider renaming Linked to Root (yes, this is optional)

[manasijm, 2016-07-06 18:02:06]

FYI This seems to produce identical or nearly identical code on most of spec
(with vs without calling Variable::setLinkedTo) with the float constant cse
functionality that motivated this.

[Jim Stichnoth, 2016-07-08 10:37:55]

https://codereview.chromium.org/2116213002/diff/20001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1101: if (Dest->getStackOffset() == SrcVar->getStackOffset()) {
On 2016/07/06 16:07:39, John wrote:
> I would do:
> 
> if (Dest.StackOffset != Src.StackOffset)
>   return false;
> 
> return true;
> 
> up to you
> 

Done.

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:699: static constexpr int32_t InvalidStackOffset = -1;
On 2016/07/06 16:07:39, John wrote:
> maybe put this in the private: section?

Done.

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:787: if (Root == nullptr)
On 2016/07/06 16:07:39, John wrote:
> so this is
> 
> if (Root == nullptr) return nullptr;
> 
> right? I'd spell out nullptr instead.

Done.

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:790: Root = Root->LinkedTo;
On 2016/07/06 16:07:39, John wrote:
> Why not
> 
> if (Root->LinkedTo != nullptr) {
>   return Root->getLinkedToRoot();
> }
> 
> return Root;
> 
> ?

Because of stack overflow.

I always think twice before using recursion in a compiler, especially when the
level of recursion can be made arbitrarily deep depending on the program being
compiled.

In the usage model this CL is preparing for, the length of the LinkedTo chain
will be the number of uses of the original Variable in a basic block.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:589: //  - Var's furthest ancestor through LinkedTo:
Root
On 2016/07/06 16:07:39, John wrote:
> Instead of Root, did you mean Ancestor?

After patchset #1, I meant to change "ancestor" and "top" to "root", but it
looks like I missed the ancestors below.  Changed them.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:596: if (!IsVarReferenced[Var->getIndex()])
On 2016/07/06 16:07:39, John wrote:
> It took me a while to understand what this is doing. Yes, I know the comments
> says exactly what this is supposed to do, but comments aren't checked by the
> compiler -- and they might rot.
> 
> It would be clearer (to me) if you created a helper function:
> 
> def MightBeSpilled(Var):
>   return false if Var is not referenced, else
>   return false if Var has a register, else
>   return true
> 
> and then this loop is changed to use the helper function:
> 
> if (!MightBeSpilled(Var))
>   continune;
> if (auto *Ancestor = Var->getLinkedToRoot()) {
>   if (MightBeSpilled(Ancestor)) {
>     // No need to rotate the tree.
>     continue;
>   }
>   Var->setLinkedTo(nullptr); // break the cycle before it happens!
>   Ancestor->setLinkedTo(Var);
> }
> 

Nice, done.

> Now, looking at this (hopefully) equivalent implementation, I wonder...
> 
> Imagine the following linked to chain:
> 
> A --- linked to ---> B --- linked to ---> C
> 
> If A is spilled, what forces C to be spilled?

The only thing that could *force* spilling of A, B, or C would be to
setMustNotHaveReg().  But if that is done, and/or one of these doesn't get
naturally register-allocated, then we guarantee a shared stack slot for them.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLowering.c...
src/IceTargetLowering.cpp:600: Variable *Ancestor = Var->getLinkedToRoot();
On 2016/07/06 16:07:39, John wrote:
> auto?

hmm, I think it wouldn't be obvious that getLinkedToRoot denotes a Variable, so
I'd prefer to make it explicit here.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:951: } else if (Offset) {
On 2016/07/06 16:07:39, John wrote:
> I prefer
> 
> if (Offset != 0),
> 
> but up to you.

Done.

https://codereview.chromium.org/2116213002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:1209: const Variable *Linked =
Var->getLinkedToRoot();
On 2016/07/06 16:07:39, John wrote:
> Consider renaming Linked to Root (yes, this is optional)

Done.

[John, 2016-07-08 15:09:05]

lgtm

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:790: Root = Root->LinkedTo;
On 2016/07/08 10:37:54, stichnot wrote:
> On 2016/07/06 16:07:39, John wrote:
> > Why not
> > 
> > if (Root->LinkedTo != nullptr) {
> >   return Root->getLinkedToRoot();
> > }
> > 
> > return Root;
> > 
> > ?
> 
> Because of stack overflow.
> 
> I always think twice before using recursion in a compiler, especially when the
> level of recursion can be made arbitrarily deep depending on the program being
> compiled.
> 
> In the usage model this CL is preparing for, the length of the LinkedTo chain
> will be the number of uses of the original Variable in a basic block.

This function requires minimal stack space, so even with a chain of 1M linked
variables I doubt stack overflow would be a problem.

This is also a tail call, and I would expect compilers to optimize trivially
optimize it.

More importantly, are there any reasons why this while is needed? Instead of
having tree

A -> B -> C

why not having

A ---+--> C
B ---|

instead? Just curious...

[Jim Stichnoth, 2016-07-10 11:44:43]

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2116213002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:790: Root = Root->LinkedTo;
On 2016/07/08 15:09:05, John wrote:
> On 2016/07/08 10:37:54, stichnot wrote:
> > On 2016/07/06 16:07:39, John wrote:
> > > Why not
> > > 
> > > if (Root->LinkedTo != nullptr) {
> > >   return Root->getLinkedToRoot();
> > > }
> > > 
> > > return Root;
> > > 
> > > ?
> > 
> > Because of stack overflow.
> > 
> > I always think twice before using recursion in a compiler, especially when
the
> > level of recursion can be made arbitrarily deep depending on the program
being
> > compiled.
> > 
> > In the usage model this CL is preparing for, the length of the LinkedTo
chain
> > will be the number of uses of the original Variable in a basic block.
> 
> This function requires minimal stack space, so even with a chain of 1M linked
> variables I doubt stack overflow would be a problem.
> 
> This is also a tail call, and I would expect compilers to optimize trivially
> optimize it.
> 
> More importantly, are there any reasons why this while is needed? Instead of
> having tree
> 
> A -> B -> C
> 
> why not having
> 
> A ---+--> C
> B ---|
> 
> instead? Just curious...

I think maybe what you're suggesting is to pre-compute LinkedToRoot at
setLinkedTo() time?  The problem would be that if you re-parent the existing
root, you would have to track down all variables pointing to that root and
re-parent them as well.

[Jim Stichnoth, 2016-07-10 12:13:21]

Description was changed from

==========
Subzero: Allow deeper levels of variable splitting.

This fixes some existing problems with the Variable::LinkedTo splitting/linking
mechanism.  The problem was that if B is linked to A, and B needs a stack slot,
but A doesn't get a stack slot, B's stack offset would never get initialized. 
This could happen if A ends up with no explicit references in the code, or A's
live range gets truncated such that it actually has a register while B doesn't.

It gets even more complicated if you have a link chain like A<--B<--C<--D etc.
where some of them have stack slots (which should ultimately all be the same
slot) and some don't.

The solution here is that if B is linked to the root A, and B has a stack slot
but A doesn't, we can do a tree rotation so that B is the new root and A links
to B.

In addition, we initialize Variable::StackOffset to an invalid value and always
make sure a value used is valid.  Earlier attempts at extending the variable
splitting would sometimes silently fail because the default StackOffset value of
0 ended up being used.

BUG= none
==========

to

==========
Subzero: Allow deeper levels of variable splitting.

This fixes some existing problems with the Variable::LinkedTo splitting/linking
mechanism.  The problem was that if B is linked to A, and B needs a stack slot,
but A doesn't get a stack slot, B's stack offset would never get initialized. 
This could happen if A ends up with no explicit references in the code, or A's
live range gets truncated such that it actually has a register while B doesn't.

It gets even more complicated if you have a link chain like A<--B<--C<--D etc.
where some of them have stack slots (which should ultimately all be the same
slot) and some don't.

The solution here is that if B is linked to the root A, and B has a stack slot
but A doesn't, we can do a tree rotation so that B is the new root and A links
to B.

In addition, we initialize Variable::StackOffset to an invalid value and always
make sure a value used is valid.  Earlier attempts at extending the variable
splitting would sometimes silently fail because the default StackOffset value of
0 ended up being used.

BUG= none
R=jpp@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[Jim Stichnoth, 2016-07-10 12:13:23]

Committed patchset #3 (id:40001) manually as
fe62f0a229a7b2bc910eb8b7cb83d2534ed39343 (presubmit successful).