Subzero: Allow deeper levels of variable splitting.

src/IceTargetLowering.cpp

Index: src/IceTargetLowering.cpp
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 207a76cbb0c1e060059bc7daed228c334a9ff6fb..6362533ec928ed7645aba7459c964db536b7152a 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -583,6 +583,30 @@ void TargetLowering::getVarStackSlotParams(
     }
   }
 
+  // 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