Subzero: Allow deeper levels of variable splitting.

src/IceTargetLowering.cpp

 //===- subzero/src/IceTargetLowering.cpp - Basic lowering implementation --===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 565 matching lines @@
       if (Instr.isDeleted())
         continue;
       if (const Variable *Var = Instr.getDest())
         IsVarReferenced[Var->getIndex()] = true;
       FOREACH_VAR_IN_INST(Var, Instr) {
         IsVarReferenced[Var->getIndex()] = true;
       }
     }
   }
 
+  // Find each variable Var where:
+  //  - Var is actively referenced
+  //  - Var does not have a register
+  //  - Var's furthest ancestor through LinkedTo: Root

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

Instead of Root, did you mean Ancestor?

[Jim Stichnoth, 2016/07/08 10:37:54]

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

+  //  - Root has no active references, or has a register
+  //
+  // When any such Var is found, swap Var->LinkedTo and Root->LinkedTo.  This
+  // ensures that when Var needs a stack slot, either its LinkedTo field is
+  // nullptr, or Var->getLinkedToRoot() returns a variable with a stack slot.
+  for (Variable *Var : Func->getVariables()) {
+    if (!IsVarReferenced[Var->getIndex()])

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

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?

[Jim Stichnoth, 2016/07/08 10:37:54]

Nice, done.
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.

+      continue;
+    if (Var->hasReg())
+      continue;
+    Variable *Ancestor = Var->getLinkedToRoot();

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

auto?

[Jim Stichnoth, 2016/07/08 10:37:54]

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

+    if (Ancestor == nullptr)
+      continue;
+    assert(Ancestor->getLinkedTo() == nullptr);
+    if (!Ancestor->hasReg() && IsVarReferenced[Ancestor->getIndex()])
+      continue;
+    Ancestor->setLinkedTo(Var);
+    Var->setLinkedTo(nullptr);
+  }
+
   // If SimpleCoalescing is false, each variable without a register gets its
   // own unique stack slot, which leads to large stack frames. If
   // SimpleCoalescing is true, then each "global" variable without a register
   // gets its own slot, but "local" variable slots are reused across basic
   // blocks. E.g., if A and B are local to block 1 and C is local to block 2,
   // then C may share a slot with A or B.
   //
   // We cannot coalesce stack slots if this function calls a "returns twice"
   // function. In that case, basic blocks may be revisited, and variables local
   // to those basic blocks are actually live until after the called function
@@ skipping 307 matching lines @@
   case TARGET_LOWERING_CLASS_FOR(X):                                           \
     return ::X::createTargetHeaderLowering(Ctx);
 #include "SZTargets.def"
 #undef SUBZERO_TARGET
   }
 }
 
 TargetHeaderLowering::~TargetHeaderLowering() = default;
 
 } // end of namespace Ice