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 VariablesMetadata::init() {
+  Metadata.clear();
+  Metadata.resize(Func->getNumVariables());
+  // Mark args as being used in the entry node.
+  const CfgNode *Entry = Func->getEntryNode();
+  Entry = NULL;
+  for (SizeT i = 0; i < Func->getNumVariables(); ++i) {
+    const Variable *Var = Func->getVariables()[i];
+    if (Var->getIsArg()) {

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

Why not use the Func->getArgs() list, which will have fewer variables to iterate
over? It looks like lowerArguments() should keep the list in tact (new variables
which are setIsArg() should take the place in the list, and the old variables
are setIsArg(false)).

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

The only problem with using Func->getArgs() is the getPhysicalRegister() hack
where esp is marked as an arg so that it is considered live upon function entry.

A better approach (see latest patchset) is to maintain two separate lists: the
original arg list (variables that by definition are live coming in), and a list
of implicit args, which could include esp, a reserved register for a TLS
pointer, etc.

+      const Inst *NoInst = NULL;
+      const bool IsFromDef = false;
+      Metadata[Var->getIndex()].markUse(NoInst, Entry, IsFromDef);
+    }
+  }
+  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;
+          Metadata[VarNum].markUse(*I, Node, IsFromDef);
+        }
+      }
+    }
+  }
+}
+
+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