Subzero: Speed up VariablesMetadata initialization.

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
@@ skipping 167 matching lines @@
 
 Variable Variable::asType(Type Ty) {
   // Note: This returns a Variable, even if the "this" object is a
   // subclass of Variable.
   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) {
+void VariableTracking::markUse(MetadataKind TrackingKind, const Inst *Instr,
+                               const CfgNode *Node, bool IsFromDef,
+                               bool IsImplicit) {
+  (void)TrackingKind;
   if (MultiBlock == MBS_MultiBlock)
     return;
   // 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;
   if (IsImplicit)
@@ skipping 20 matching lines @@
       break;
     }
   }
 
   if (MakeMulti) {
     MultiBlock = MBS_MultiBlock;
     SingleUseNode = NULL;
   }
 }
 
-void VariableTracking::markDef(const Inst *Instr, const CfgNode *Node) {
+void VariableTracking::markDef(MetadataKind TrackingKind, 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.
   assert(Node);
   // Verify that instructions are added in increasing order.
-  assert(Definitions.empty() ||
-         Instr->getNumber() >= Definitions.back()->getNumber());
-  Definitions.push_back(Instr);
+  if (TrackingKind == VMK_All) {
+    assert(Definitions.empty() ||
+           Instr->getNumber() >= Definitions.back()->getNumber());
+  }
   const bool IsFromDef = true;
   const bool IsImplicit = false;
-  markUse(Instr, Node, IsFromDef, IsImplicit);
+  markUse(TrackingKind, Instr, Node, IsFromDef, IsImplicit);
+  if (TrackingKind == VMK_Uses)
+    return;
+  if (FirstDefinition == NULL)

[jvoung (off chromium), 2014/10/15 17:44:54]

Looks like this could be put under "if (TrackingKind == VMK_All)" as well, since
VariablesMetadata::getFirstDefinition asserts that it is VMK_All.

Maybe the assert above w.r.t. instructions in the Definitions list can also be
under the same "if () {}"?

[Jim Stichnoth, 2014/10/15 21:29:43]

Renamed the field to FirstOrSingleDefinition to clarify.  Also changed the
assert in VariablesMetadata::getSingleDefinition() to be the same as
getFirstDefinition(), i.e. less restrictive.

+    FirstDefinition = Instr;
+  if (TrackingKind == VMK_All)
+    Definitions.push_back(Instr);
   switch (MultiDef) {
   case MDS_Unknown:
     assert(SingleDefNode == NULL);
     MultiDef = MDS_SingleDef;
     SingleDefNode = Node;
     break;
   case MDS_SingleDef:
     assert(SingleDefNode);
     if (Node == SingleDefNode) {
       MultiDef = MDS_MultiDefSingleBlock;
@@ skipping 15 matching lines @@
   }
 }
 
 const Inst *VariableTracking::getFirstDefinition() const {
   switch (MultiDef) {
   case MDS_Unknown:
   case MDS_MultiDefMultiBlock:
     return NULL;
   case MDS_SingleDef:
   case MDS_MultiDefSingleBlock:
-    assert(!Definitions.empty());
-    return Definitions[0];
+    assert(FirstDefinition);
+    return FirstDefinition;
   }
 }
 
 const Inst *VariableTracking::getSingleDefinition() const {
   switch (MultiDef) {
   case MDS_Unknown:
   case MDS_MultiDefMultiBlock:
   case MDS_MultiDefSingleBlock:
     return NULL;
   case MDS_SingleDef:
-    assert(!Definitions.empty());
-    return Definitions[0];
+    assert(FirstDefinition);
+    return FirstDefinition;
   }
 }
 
-void VariablesMetadata::init() {
+void VariablesMetadata::init(MetadataKind TrackingKind) {
   TimerMarker T(TimerStack::TT_vmetadata, Func);
+  Kind = TrackingKind;
   Metadata.clear();
   Metadata.resize(Func->getNumVariables());
 
   // Mark implicit args as being used in the entry node.
   for (Variable *Var : Func->getImplicitArgs()) {
     const Inst *NoInst = NULL;
     const CfgNode *EntryNode = Func->getEntryNode();
     const bool IsFromDef = false;
     const bool IsImplicit = true;
-    Metadata[Var->getIndex()].markUse(NoInst, EntryNode, IsFromDef, IsImplicit);
+    Metadata[Var->getIndex()]
+        .markUse(Kind, NoInst, EntryNode, IsFromDef, IsImplicit);
   }
 
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst *I : Node->getInsts()) {
       if (I->isDeleted())
         continue;
       if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(I)) {
         // A FakeKill instruction indicates certain Variables (usually
         // physical scratch registers) are redefined, so we register
         // them as defs.
         for (SizeT SrcNum = 0; SrcNum < I->getSrcSize(); ++SrcNum) {
           Variable *Var = llvm::cast<Variable>(I->getSrc(SrcNum));
           SizeT VarNum = Var->getIndex();
           assert(VarNum < Metadata.size());
-          Metadata[VarNum].markDef(Kill, Node);
+          Metadata[VarNum].markDef(Kind, Kill, Node);
         }
         continue; // no point in executing the rest
       }
       if (Variable *Dest = I->getDest()) {
         SizeT DestNum = Dest->getIndex();
         assert(DestNum < Metadata.size());
-        Metadata[DestNum].markDef(I, Node);
+        Metadata[DestNum].markDef(Kind, 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);
+          Metadata[VarNum].markUse(Kind, I, Node, IsFromDef, IsImplicit);
         }
       }
     }
   }
 }
 
 bool VariablesMetadata::isMultiDef(const Variable *Var) const {
+  assert(Kind != VMK_Uses);
   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 (Var->getIsArg())
     return true;
   if (!isTracked(Var))
     return true; // conservative answer
   SizeT VarNum = Var->getIndex();
   // Conservatively return true if the state is unknown.
   return Metadata[VarNum].getMultiBlock() != VariableTracking::MBS_SingleBlock;
 }
 
 const Inst *VariablesMetadata::getFirstDefinition(const Variable *Var) const {
+  assert(Kind == VMK_All);
   if (!isTracked(Var))
     return NULL; // conservative answer
   SizeT VarNum = Var->getIndex();
   return Metadata[VarNum].getFirstDefinition();
 }
 
 const Inst *VariablesMetadata::getSingleDefinition(const Variable *Var) const {
+  assert(Kind != VMK_Uses);
   if (!isTracked(Var))
     return NULL; // conservative answer
   SizeT VarNum = Var->getIndex();
   return Metadata[VarNum].getSingleDefinition();
 }
 
 const InstDefList &
 VariablesMetadata::getDefinitions(const Variable *Var) const {
+  assert(Kind == VMK_All);
   if (!isTracked(Var))
     return NoDefinitions;
   SizeT VarNum = Var->getIndex();
   return Metadata[VarNum].getDefinitions();
 }
 
 const CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const {
   if (!isTracked(Var))
     return NULL; // conservative answer
   SizeT VarNum = Var->getIndex();
@@ skipping 72 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