Subzero: Allow deeper levels of variable splitting.

src/IceOperand.h

 //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 678 matching lines @@
   bool getIsArg() const { return IsArgument; }
   virtual void setIsArg(bool Val = true) { IsArgument = Val; }
   bool getIsImplicitArg() const { return IsImplicitArgument; }
   void setIsImplicitArg(bool Val = true) { IsImplicitArgument = Val; }
 
   void setIgnoreLiveness() { IgnoreLiveness = true; }
   bool getIgnoreLiveness() const {
     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.
   std::string getSymbolicStackOffset() const {
     if (!BuildDefs::dump())
       return "";
     return ".L$lv$" + getName();
   }
 
   bool hasReg() const { return getRegNum().hasValue(); }
@@ skipping 56 matching lines @@
   /// instead of copying the existing assignment.
   const Variable *asType(const Cfg *Func, Type Ty, RegNumT NewRegNum) const;
 
   void emit(const Cfg *Func) const override;
   using Operand::dump;
   void dump(const Cfg *Func, Ostream &Str) const override;
 
   /// 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) {
     OperandKind Kind = Operand->getKind();
     return Kind >= kVariable && Kind <= kVariable_Max;
   }
 
   SizeT hashValue() const override { return std::hash<SizeT>()(getIndex()); }
 
 protected:
@@ skipping 19 matching lines @@
   // pointer), and StackOffset is the known offset from that register.
   bool IsRematerializable = false;
   RegRequirement RegRequirement = RR_MayHaveRegister;
   RegClass RegisterClass;
   /// RegNum is the allocated register, (as long as RegNum.hasValue() is true).
   RegNumT RegNum;
   /// RegNumTmp is the tentative assignment during register allocation.
   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
 // this situation the variable must be split into a low and a high word.
 class Variable64On32 : public Variable {
   Variable64On32() = delete;
   Variable64On32(const Variable64On32 &) = delete;
   Variable64On32 &operator=(const Variable64On32 &) = delete;
 
 public:
@@ skipping 196 matching lines @@
     return Operand->getKind() == kVariableBoolean;
   }
 
 private:
   Variable *BoolSource = nullptr;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H