Subzero: Allow deeper levels of variable splitting.

src/IceOperand.h

Index: src/IceOperand.h
diff --git a/src/IceOperand.h b/src/IceOperand.h
index 29d27a205b4df42f7b9b40502f46849c04229b34..fba777050e1dd9adaaa62361962ffce3b18c2b30 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -696,7 +696,12 @@ public:
     return IgnoreLiveness || IsRematerializable;
   }
 
-  int32_t getStackOffset() const { return StackOffset; }
+  static constexpr int32_t InvalidStackOffset = -1;

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

maybe put this in the private: section?

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

Done.

+  bool hasStackOffset() const { return StackOffset != InvalidStackOffset; }
+  int32_t getStackOffset() const {
+    assert(hasStackOffset());
+    return StackOffset;
+  }
   void setStackOffset(int32_t Offset) { StackOffset = Offset; }
   /// Returns the variable's stack offset in symbolic form, to improve
   /// readability in DecorateAsm mode.
@@ -773,21 +778,17 @@ public:
   /// Return reg num of base register, if different from stack/frame register.
   virtual RegNumT getBaseRegNum() const { return RegNumT(); }
 
-  void setLinkedTo(const Variable *Var) {
-    // If B is linked to A, and we now want to link C to B, we instead link C to
-    // A so that we have one root (A) and all leaves (B, C) link directly to the
-    // root.
-    if (Var->getLinkedTo() != nullptr) {
-      Var = Var->LinkedTo;
-      assert(Var->LinkedTo == nullptr);
-    }
-    LinkedTo = Var;
-  }
-  const Variable *getLinkedTo() const {
-    // Make sure a leaf links directly to the root.
-    if (LinkedTo != nullptr)
-      assert(LinkedTo->LinkedTo == nullptr);
-    return LinkedTo;
+  /// Access the LinkedTo field.
+  void setLinkedTo(Variable *Var) { LinkedTo = Var; }
+  Variable *getLinkedTo() const { return LinkedTo; }
+  /// Follow the LinkedTo chain up to the furthest ancestor.
+  Variable *getLinkedToRoot() const {
+    Variable *Root = LinkedTo;
+    if (Root == nullptr)

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

so this is

if (Root == nullptr) return nullptr;

right? I'd spell out nullptr instead.

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

Done.

+      return Root;
+    while (Root->LinkedTo != nullptr)
+      Root = Root->LinkedTo;

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

Why not

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

return Root;

?

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

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.

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

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]

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.

+    return Root;
   }
 
   static bool classof(const Operand *Operand) {
@@ -827,13 +828,13 @@ protected:
   RegNumT RegNumTmp;
   /// StackOffset is the canonical location on stack (only if
   /// RegNum.hasNoValue() || IsArgument).
-  int32_t StackOffset = 0;
+  int32_t StackOffset = InvalidStackOffset;
   LiveRange Live;
   /// VarsReal (and Operand::Vars) are set up such that Vars[0] == this.
   Variable *VarsReal[1];
   /// This Variable may be "linked" to another Variable, such that if neither
   /// Variable gets a register, they are guaranteed to share a stack location.
-  const Variable *LinkedTo = nullptr;
+  Variable *LinkedTo = nullptr;
 };
 
 // Variable64On32 represents a 64-bit variable on a 32-bit architecture. In