Subzero: Automatically infer regalloc preferences and overlap.

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 147 matching lines @@
 
 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;
+  if (IsImplicit)
+    MakeMulti = true;
   // 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.
+  assert(Node);
+  Definitions.push_back(Instr);
   const bool IsFromDef = true;
   const bool IsImplicit = false;
   markUse(Instr, Node, IsFromDef, IsImplicit);
   switch (MultiDef) {
   case MDS_Unknown:
+    assert(SingleDefNode == NULL);
     MultiDef = MDS_SingleDef;
-    SingleDefInst = Instr;
+    SingleDefNode = Node;
     break;
   case MDS_SingleDef:
-    MultiDef = MDS_MultiDef;
-    SingleDefInst = NULL;
+    assert(SingleDefNode);
+    if (Node == SingleDefNode) {
+      MultiDef = MDS_MultiDefSingleBlock;
+    } else {
+      MultiDef = MDS_MultiDefMultiBlock;
+      SingleDefNode = NULL;
+    }
     break;
-  case MDS_MultiDef:
+  case MDS_MultiDefSingleBlock:
+    assert(SingleDefNode);
+    if (Node != SingleDefNode) {
+      MultiDef = MDS_MultiDefMultiBlock;
+      SingleDefNode = NULL;
+    }
     break;
+  case MDS_MultiDefMultiBlock:
+    assert(SingleDefNode == NULL);
+    break;
+  }
+}
+
+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];
+  }
+}
+
+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];
   }
 }
 
 void VariablesMetadata::init() {
   Metadata.clear();
   Metadata.resize(Func->getNumVariables());
 
   // 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 Inst *NoInst = NULL;
     const CfgNode *EntryNode = Func->getEntryNode();
     const bool IsFromDef = false;
     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 (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);
+        }
+        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);
       }
       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);
@@ skipping 12 matching lines @@
   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)
+  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::getDefinition(const Variable *Var) const {
+const Inst *VariablesMetadata::getFirstDefinition(const Variable *Var) const {
   if (!isTracked(Var))
     return NULL; // conservative answer
   SizeT VarNum = Var->getIndex();
-  return Metadata[VarNum].getDefinition();
+  return Metadata[VarNum].getFirstDefinition();
+}
+
+const Inst *VariablesMetadata::getSingleDefinition(const Variable *Var) const {
+  if (!isTracked(Var))
+    return NULL; // conservative answer
+  SizeT VarNum = Var->getIndex();
+  return Metadata[VarNum].getSingleDefinition();
+}
+
+const InstDefList &
+VariablesMetadata::getDefinitions(const Variable *Var) const {
+  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();
   return Metadata[VarNum].getNode();
 }
 
+const InstDefList VariablesMetadata::NoDefinitions;
+
 // ======================== dump routines ======================== //
 
 void Variable::emit(const Cfg *Func) const {
   Func->getTarget()->emitVariable(this);
 }
 
 void Variable::dump(const Cfg *Func, Ostream &Str) const {
   if (Func == NULL) {
     Str << "%" << getName();
     return;
@@ skipping 56 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