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

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the Operand class and its target-independent
@@ skipping 329 matching lines @@
 Ostream &operator<<(Ostream &Str, const LiveRange &L);
 
 // Variable represents an operand that is register-allocated or
 // stack-allocated.  If it is register-allocated, it will ultimately
 // have a non-negative RegNum field.
 class Variable : public Operand {
   Variable(const Variable &) LLVM_DELETED_FUNCTION;
   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; }
   IceString getName() const;
   void setName(IceString &NewName) {
     // Make sure that the name can only be set once.
     assert(Name.empty());
     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; }
 
   static const int32_t NoRegister = -1;
   bool hasReg() const { return getRegNum() != NoRegister; }
   int32_t getRegNum() const { return RegNum; }
   void setRegNum(int32_t NewRegNum) {
     // Regnum shouldn't be set more than once.
     assert(!hasReg() || RegNum == NewRegNum);
@@ skipping 48 matching lines @@
 
   static bool classof(const Operand *Operand) {
     OperandKind Kind = Operand->getKind();
     return Kind >= kVariable && Kind <= kVariable_Num;
   }
 
   // The destructor is public because of the asType() method.
   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;
     Vars[0] = this;
     NumVars = 1;
   }
   // Number is unique across all variables, and is used as a
   // (bit)vector index for liveness analysis.
   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).
   int32_t StackOffset;
   // RegNum is the allocated register, or NoRegister if it isn't
   // register-allocated.
   int32_t RegNum;
   // RegNumTmp is the tentative assignment during register allocation.
   int32_t RegNumTmp;
   RegWeight Weight; // Register allocation priority
@@ skipping 15 matching lines @@
   // portion.  TODO: It's wasteful to penalize all variables on all
   // targets this way; use a sparser representation.  It's also
   // wasteful for a 64-bit target.
   Variable *LoVar;
   Variable *HiVar;
   // VarsReal (and Operand::Vars) are set up such that Vars[0] ==
   // this.
   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