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

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Operand class and its target-independent
 // subclasses, primarily for the methods of the Variable class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
+#include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h" // dumping stack/frame pointer register
 
 namespace Ice {
 
 bool operator<(const RelocatableTuple &A, const RelocatableTuple &B) {
   if (A.Offset != B.Offset)
     return A.Offset < B.Offset;
   if (A.SuppressMangling != B.SuppressMangling)
@@ skipping 105 matching lines @@
 // calculation.
 bool LiveRange::containsValue(InstNumberT Value) const {
   for (RangeType::const_iterator I = Range.begin(), E = Range.end(); I != E;
        ++I) {
     if (I->first <= Value && Value <= I->second)
       return true;
   }
   return false;
 }
 
-void Variable::setUse(const Inst *Inst, const CfgNode *Node) {
-  if (DefNode == NULL)
-    return;
-  if (llvm::isa<InstPhi>(Inst) || Node != DefNode)
-    DefNode = NULL;
-}
-
-void Variable::setDefinition(Inst *Inst, const CfgNode *Node) {
-  if (DefInst && !DefInst->isDeleted() && DefInst != Inst) {
-    // Detect when a variable is being defined multiple times,
-    // particularly for Phi instruction lowering.  If this happens, we
-    // need to lock DefInst to NULL.
-    DefInst = NULL;
-    DefNode = NULL;
-    return;
-  }
-  if (DefNode == NULL)
-    return;
-  DefInst = Inst;
-  if (Node != DefNode)
-    DefNode = NULL;
-}
-
-void Variable::replaceDefinition(Inst *Inst, const CfgNode *Node) {
-  DefInst = NULL;
-  setDefinition(Inst, Node);
-}
-
-void Variable::setIsArg(Cfg *Func, bool IsArg) {
-  if (IsArg) {
-    IsArgument = true;
-    if (DefNode == NULL)
-      return;
-    CfgNode *Entry = Func->getEntryNode();
-    if (DefNode == Entry)
-      return;
-    DefNode = NULL;
-  } else {
-    IsArgument = false;
-  }
-}
-
 IceString Variable::getName() const {
   if (!Name.empty())
     return Name;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
 
 Variable Variable::asType(Type Ty) {
   // Note: This returns a Variable, even if the "this" object is a
   // subclass of Variable.
-  Variable V(kVariable, Ty, DefNode, Number, Name);
+  Variable V(kVariable, Ty, Number, Name);
   V.RegNum = RegNum;
   V.StackOffset = StackOffset;
   return V;
 }
 
+void VariableTracking::markUse(const Inst *Instr, const CfgNode *Node,
+                               bool IsFromDef, bool IsImplicit) {
+  // 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);
+  bool MakeMulti = false;
+  // 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 (IsImplicit)
+    MakeMulti = true;
+  if (!IsFromDef && Instr && llvm::isa<InstPhi>(Instr))
+    MakeMulti = true;
+
+  if (!MakeMulti) {
+    switch (MultiBlock) {
+    case MBS_Unknown:
+      MultiBlock = MBS_SingleBlock;
+      SingleUseNode = Node;
+      break;
+    case MBS_SingleBlock:
+      if (SingleUseNode != Node)
+        MakeMulti = true;
+      break;
+    case MBS_MultiBlock:
+      break;
+    }
+  }
+
+  if (MakeMulti) {
+    MultiBlock = MBS_MultiBlock;
+    SingleUseNode = NULL;
+  }
+}
+
+void VariableTracking::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;
+  const bool IsImplicit = false;
+  markUse(Instr, Node, IsFromDef, IsImplicit);
+  switch (MultiDef) {
+  case MDS_Unknown:
+    MultiDef = MDS_SingleDef;
+    SingleDefInst = Instr;
+    break;
+  case MDS_SingleDef:
+    MultiDef = MDS_MultiDef;
+    SingleDefInst = NULL;
+    break;
+  case MDS_MultiDef:
+    break;
+  }
+}
+
+void VariablesMetadata::init() {
+  Metadata.clear();
+  Metadata.resize(Func->getNumVariables());
+  const Inst *NoInst = NULL;
+  const CfgNode *EntryNode = Func->getEntryNode();
+  const bool IsFromDef = false;
+
+  // Mark args as being used in the entry node.
+  const VarList &ArgList = Func->getArgs();
+  for (VarList::const_iterator I = ArgList.begin(), E = ArgList.end(); I != E;

[jvoung (off chromium), 2014/09/22 21:48:03]

Hmm, actually, split64() also creates new variables and does setIsArg(), but it
doesn't add it to the list?

[Jim Stichnoth, 2014/09/22 22:25:07]

Interesting.  I guess I was over-zealous in marking these uses.  I removed the
marking of explicit args, and there was no difference in the asm generated
across all of spec2k, nor in the fully verbose output across all the lit tests.

+       ++I) {
+    const Variable *Var = *I;
+    const bool IsImplicit = false;
+    Metadata[Var->getIndex()].markUse(NoInst, EntryNode, IsFromDef, IsImplicit);
+  }
+
+  // Also mark implicit args as being used in the entry node.
+  const VarList &ImplicitArgList = Func->getImplicitArgs();
+  for (VarList::const_iterator I = ImplicitArgList.begin(),
+                               E = ImplicitArgList.end();
+       I != E; ++I) {
+    const Variable *Var = *I;
+    const bool IsImplicit = true;
+    Metadata[Var->getIndex()].markUse(NoInst, EntryNode, IsFromDef, IsImplicit);
+  }
+
+  SizeT NumNodes = Func->getNumNodes();
+  for (SizeT N = 0; N < NumNodes; ++N) {
+    CfgNode *Node = Func->getNodes()[N];
+    const InstList &Insts = Node->getInsts();
+    for (InstList::const_iterator I = Insts.begin(), E = Insts.end(); I != E;
+         ++I) {
+      if ((*I)->isDeleted())
+        continue;
+      if (Variable *Dest = (*I)->getDest()) {
+        SizeT DestNum = Dest->getIndex();
+        assert(DestNum < Metadata.size());
+        Metadata[DestNum].markDef(*I, Node);
+      }
+      for (SizeT SrcNum = 0; SrcNum < (*I)->getSrcSize(); ++SrcNum) {
+        Operand *Src = (*I)->getSrc(SrcNum);
+        SizeT NumVars = Src->getNumVars();
+        for (SizeT J = 0; J < NumVars; ++J) {
+          const Variable *Var = Src->getVar(J);
+          SizeT VarNum = Var->getIndex();
+          assert(VarNum < Metadata.size());
+          const bool IsFromDef = false;
+          const bool IsImplicit = false;
+          Metadata[VarNum].markUse(*I, Node, IsFromDef, IsImplicit);
+        }
+      }
+    }
+  }
+}
+
+bool VariablesMetadata::isMultiDef(const Variable *Var) const {
+  if (Var->getIsArg())
+    return false;
+  if (!isTracked(Var))
+    return true; // conservative answer
+  SizeT VarNum = Var->getIndex();
+  // Conservatively return true if the state is unknown.
+  return Metadata[VarNum].getMultiDef() != VariableTracking::MDS_SingleDef;
+}
+
+bool VariablesMetadata::isMultiBlock(const Variable *Var) const {
+  if (getDefinition(Var) == NULL)
+    return true;
+  SizeT VarNum = Var->getIndex();
+  // Conservatively return true if the state is unknown.
+  return Metadata[VarNum].getMultiBlock() != VariableTracking::MBS_SingleBlock;
+}
+
+const Inst *VariablesMetadata::getDefinition(const Variable *Var) const {
+  if (!isTracked(Var))
+    return NULL; // conservative answer
+  SizeT VarNum = Var->getIndex();
+  return Metadata[VarNum].getDefinition();
+}
+
+const CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const {
+  if (!isTracked(Var))
+    return NULL; // conservative answer
+  SizeT VarNum = Var->getIndex();
+  return Metadata[VarNum].getNode();
+}
+
 // ======================== dump routines ======================== //
 
 void Variable::emit(const Cfg *Func) const {
-  Func->getTarget()->emitVariable(this, Func);
+  Func->getTarget()->emitVariable(this);
 }
 
 void Variable::dump(const Cfg *Func, Ostream &Str) const {
   if (Func == NULL) {
     Str << "%" << getName();
     return;
   }
-  const CfgNode *CurrentNode = Func->getCurrentNode();
-  (void)CurrentNode; // used only in assert()
-  assert(CurrentNode == NULL || DefNode == NULL || DefNode == CurrentNode);
   if (Func->getContext()->isVerbose(IceV_RegOrigins) ||
       (!hasReg() && !Func->getTarget()->hasComputedFrame()))
     Str << "%" << getName();
   if (hasReg()) {
     if (Func->getContext()->isVerbose(IceV_RegOrigins))
       Str << ":";
     Str << Func->getTarget()->getRegName(RegNum, getType());
   } else if (Func->getTarget()->hasComputedFrame()) {
     if (Func->getContext()->isVerbose(IceV_RegOrigins))
       Str << ":";
@@ skipping 45 matching lines @@
 
 Ostream &operator<<(Ostream &Str, const RegWeight &W) {
   if (W.getWeight() == RegWeight::Inf)
     Str << "Inf";
   else
     Str << W.getWeight();
   return Str;
 }
 
 } // end of namespace Ice