Subzero: Refactor tracking of Defs and block-local Variables.

src/IceOperand.h

Index: src/IceOperand.h
diff --git a/src/IceOperand.h b/src/IceOperand.h
index 7fedfd24af7b528fd62cb1a2383544cfebcbb31b..96f2a5555f61b41c0afcc6e42af01333445b9797 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -347,10 +347,10 @@ class Variable : public Operand {
   Variable &operator=(const Variable &) LLVM_DELETED_FUNCTION;
 
 public:
-  static Variable *create(Cfg *Func, Type Ty, const CfgNode *Node, SizeT Index,
+  static Variable *create(Cfg *Func, Type Ty, SizeT Index,
                           const IceString &Name) {
     return new (Func->allocate<Variable>())
-        Variable(kVariable, Ty, Node, Index, Name);
+        Variable(kVariable, Ty, Index, Name);
   }
 
   SizeT getIndex() const { return Number; }
@@ -361,24 +361,8 @@ public:
     Name = NewName;
   }
 
-  Inst *getDefinition() const { return DefInst; }
-  void setDefinition(Inst *Inst, const CfgNode *Node);
-  void replaceDefinition(Inst *Inst, const CfgNode *Node);
-
-  const CfgNode *getLocalUseNode() const { return DefNode; }
-  bool isMultiblockLife() const { return (DefNode == NULL); }
-  void setUse(const Inst *Inst, const CfgNode *Node);
-
-  // Multidef means a variable is non-SSA and has multiple defining
-  // instructions.  Currently this classification is limited to SSA
-  // lowering temporaries where the definitions are in different basic
-  // blocks, and it is not maintained during target lowering when the
-  // same temporary may be updated in consecutive instructions.
-  bool getIsMultidef() const { return IsMultidef; }
-  void setIsMultidef() { IsMultidef = true; }
-
   bool getIsArg() const { return IsArgument; }
-  void setIsArg(Cfg *Func, bool IsArg = true);
+  void setIsArg(bool Val = true) { IsArgument = Val; }
 
   int32_t getStackOffset() const { return StackOffset; }
   void setStackOffset(int32_t Offset) { StackOffset = Offset; }
@@ -447,11 +431,9 @@ public:
   virtual ~Variable() {}
 
 protected:
-  Variable(OperandKind K, Type Ty, const CfgNode *Node, SizeT Index,
-           const IceString &Name)
-      : Operand(K, Ty), Number(Index), Name(Name), DefInst(NULL), DefNode(Node),
-        IsMultidef(false), IsArgument(false), StackOffset(0),
-        RegNum(NoRegister), RegNumTmp(NoRegister), Weight(1),
+  Variable(OperandKind K, Type Ty, SizeT Index, const IceString &Name)
+      : Operand(K, Ty), Number(Index), Name(Name), IsArgument(false),
+        StackOffset(0), RegNum(NoRegister), RegNumTmp(NoRegister), Weight(1),
         RegisterPreference(NULL), AllowRegisterOverlap(false), LoVar(NULL),
         HiVar(NULL) {
     Vars = VarsReal;
@@ -463,17 +445,6 @@ protected:
   const SizeT Number;
   // Name is optional.
   IceString Name;
-  // DefInst is the instruction that produces this variable as its
-  // dest.
-  Inst *DefInst;
-  // DefNode is the node where this variable was produced, and is
-  // reset to NULL if it is used outside that node.  This is used for
-  // detecting isMultiblockLife().  TODO: Collapse this to a single
-  // bit and use a separate pass to calculate the values across the
-  // Cfg.  This saves space in the Variable, and removes the fragility
-  // of incrementally computing and maintaining the information.
-  const CfgNode *DefNode;
-  bool IsMultidef;
   bool IsArgument;
   // StackOffset is the canonical location on stack (only if
   // RegNum<0 || IsArgument).
@@ -509,6 +480,108 @@ protected:
   Variable *VarsReal[1];
 };
 
+// VariableTracking tracks the metadata for a single variable.
+class VariableTracking {
+public:
+  enum MultiDefState {
+    // TODO(stichnot): Consider using just a simple counter.
+    MDS_Unknown,
+    MDS_SingleDef,
+    MDS_MultiDef
+  };
+  enum MultiBlockState {
+    MBS_Unknown,
+    MBS_SingleBlock,
+    MBS_MultiBlock
+  };
+  VariableTracking()
+      : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(NULL),
+        SingleDefInst(NULL) {}
+  MultiDefState getMultiDef() const { return MultiDef; }
+  MultiBlockState getMultiBlock() const { return MultiBlock; }
+  const Inst *getDefinition() const { return SingleDefInst; }
+  const CfgNode *getNode() const { return SingleUseNode; }
+  void markUse(const Inst *Instr, const CfgNode *Node, bool IsFromDef) {

[jvoung (off chromium), 2014/09/22 17:07:29]

Should markUse not be inlined, since it seems like it could be rather big?

[Jim Stichnoth, 2014/09/22 21:00:46]

Done, and the same for markDef() for symmetry.

+    // TODO(stichnot): If the use occurs as a source operand in the
+    // first instruction of the block, and its definition is in this
+    // block's only predecessor, we might consider not marking this as
+    // a separate use.  This may also apply if it's the first
+    // instruction of the block that actually uses a Variable.
+    // assert(Node);

[jvoung (off chromium), 2014/09/22 17:07:29]

assert(Node); is commented out -- just remove?

There's also a check that "if (Node == NULL || ...)" below that would seem to
contradict the assert. When can Node be NULL?

[Jim Stichnoth, 2014/09/22 21:00:46]

VariablesMetadata::init() passes in Node=NULL for items on the Cfg arglist,
which then triggers these arguments to be marked as multi-block use.  Without
that, we run into liveness problems/asserts with arguments, especially with the
esp case in the presence of stacksave/stackrestore intrinsics.

That said, I changed this to add an explicit argument indicating an implicit
function arg like esp, which always gets marked as multiblock.  This way, we can
assert(Node) safely.

+    switch (MultiBlock) {
+    case MBS_Unknown:
+      MultiBlock = MBS_SingleBlock;
+      SingleUseNode = Node;
+      break;
+    case MBS_SingleBlock:
+      if (SingleUseNode != Node) {
+        MultiBlock = MBS_MultiBlock;
+        SingleUseNode = NULL;
+      }
+      break;
+    case MBS_MultiBlock:
+      break;
+    }
+    // A phi source variable conservatively needs to be marked as
+    // multi-block, even if its definition is in the same block.  This
+    // is because there can be additional control flow before
+    // branching back to this node, and the variable is live
+    // throughout those nodes.
+    if (Node == NULL || (!IsFromDef && Instr && llvm::isa<InstPhi>(Instr))) {
+      MultiBlock = MBS_MultiBlock;
+      SingleUseNode = NULL;
+    }
+  }
+  void markDef(const Inst *Instr, const CfgNode *Node) {
+    // TODO(stichnot): If the definition occurs in the last
+    // instruction of the block, consider not marking this as a
+    // separate use.  But be careful not to omit all uses of the
+    // variable if markDef() and markUse() both use this optimization.
+    const bool IsFromDef = true;
+    markUse(Instr, Node, IsFromDef);
+    switch (MultiDef) {
+    case MDS_Unknown:
+      MultiDef = MDS_SingleDef;
+      SingleDefInst = Instr;
+      break;
+    case MDS_SingleDef:
+      MultiDef = MDS_MultiDef;
+      SingleDefInst = NULL;
+      break;
+    case MDS_MultiDef:
+      break;
+    }
+  }
+
+private:
+  VariableTracking &operator=(const VariableTracking &) LLVM_DELETED_FUNCTION;
+  MultiDefState MultiDef;
+  MultiBlockState MultiBlock;
+  const CfgNode *SingleUseNode;
+  const Inst *SingleDefInst;
+};
+
+// VariablesMetadata analyzes and summarizes the metadata for the
+// complete set of Variables.
+class VariablesMetadata {
+public:
+  VariablesMetadata(const Cfg *Func) : Func(Func) {}
+  void init();
+  bool isTracked(const Variable *Var) const {
+    return Var->getIndex() < Metadata.size();
+  }
+  bool isMultiDef(const Variable *Var) const;
+  const Inst *getDefinition(const Variable *Var) const;
+  bool isMultiBlock(const Variable *Var) const;
+  const CfgNode *getLocalUseNode(const Variable *Var) const;
+
+private:
+  const Cfg *Func;
+  std::vector<VariableTracking> Metadata;
+  VariablesMetadata(const VariablesMetadata &) LLVM_DELETED_FUNCTION;
+  VariablesMetadata &operator=(const VariablesMetadata &) LLVM_DELETED_FUNCTION;
+};
+
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H