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 546 matching lines @@
   Dest = Source;
   // Instead of std::sort, we could do a bucket sort with log2(alignment) as
   // the buckets, if performance is an issue.
   std::sort(Dest.begin(), Dest.end(),
             [this](const Variable *V1, const Variable *V2) {
               return typeWidthInBytesOnStack(V1->getType()) >
                      typeWidthInBytesOnStack(V2->getType());
             });
 }
 
+namespace {
+bool mightHaveStackSlot(const Variable *Var, const BitVector &IsVarReferenced) {
+  if (!IsVarReferenced[Var->getIndex()])
+    return false;
+  if (Var->hasReg())
+    return false;
+  return true;
+}
+} // end of anonymous namespace
+
 void TargetLowering::getVarStackSlotParams(
     VarList &SortedSpilledVariables, SmallBitVector &RegsUsed,
     size_t *GlobalsSize, size_t *SpillAreaSizeBytes,
     uint32_t *SpillAreaAlignmentBytes, uint32_t *LocalsSlotsAlignmentBytes,
     std::function<bool(Variable *)> TargetVarHook) {
   const VariablesMetadata *VMetadata = Func->getVMetadata();
   BitVector IsVarReferenced(Func->getNumVariables());
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst &Instr : Node->getInsts()) {
       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
+  //  - Root has no active references, or has a register
+  //
+  // When any such Var is found, rotate the LinkedTo tree by swapping
+  // 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 (!mightHaveStackSlot(Var, IsVarReferenced))
+      continue;
+    if (Variable *Root = Var->getLinkedToRoot()) {
+      assert(Root->getLinkedTo() == nullptr);
+      if (mightHaveStackSlot(Root, IsVarReferenced)) {
+        // Found a "safe" root, no need to rotate the tree.
+        continue;
+      }
+      Var->setLinkedTo(nullptr);
+      Root->setLinkedTo(Var);
+    }
+  }
+
   // 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