Subzero: Allow delaying Phi lowering until after register allocation.

src/IceInst.cpp

 //===- subzero/src/IceInst.cpp - High-level instruction 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 Inst class, primarily the various
@@ skipping 117 matching lines @@
         continue;
       SizeT Index = Var->getIndex();
       if (Live[Index])
         continue;
       Live[Index] = true;
       setLastUse(VarIndex);
     }
   }
 }
 
-void Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
+// Returns true if the instruction is tentatively retained, or false

[jvoung (off chromium), 2014/10/27 22:12:21]

nit: Might be clearer if the return value is described in terms of live vs dead,
since this is a liveness() function (vs deleted which is what a separate pass
would do with this info)

[Jim Stichnoth, 2014/10/28 01:20:14]

Tried to clarify the description (in the .h file).

+// if the instruction is tentatively deleted.
+bool Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
                     Liveness *Liveness, LiveBeginEndMap *LiveBegin,
                     LiveBeginEndMap *LiveEnd) {
   assert(!isDeleted());
   if (llvm::isa<InstFakeKill>(this))
-    return;
+    return true;
 
   Dead = false;
   if (Dest) {
     SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex());
     if (Live[VarNum]) {
       if (!isDestNonKillable()) {
         Live[VarNum] = false;
         if (LiveBegin) {
           LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
         }
       }
     } else {
       if (!hasSideEffects())
         Dead = true;
     }
   }
   if (Dead)
-    return;
+    return false;
   // Phi arguments only get added to Live in the predecessor node, but
   // we still need to update LiveRangesEnded.
   bool IsPhi = llvm::isa<InstPhi>(this);
   resetLastUses();
   SizeT VarIndex = 0;
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     Operand *Src = getSrc(I);
     SizeT NumVars = Src->getNumVars();
     for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
       const Variable *Var = Src->getVar(J);
@@ skipping 23 matching lines @@
             // added in this block, but this can't be done very
             // efficiently with LiveEnd as a vector.  Instead,
             // livenessPostprocess() verifies this after the vector
             // has been sorted.
             LiveEnd->push_back(std::make_pair(VarNum, InstNumber));
           }
         }
       }
     }
   }
+  return true;
 }
 
 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
                        Variable *Dest)
     : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) {
   // Verify AlignInBytes is 0 or a power of 2.
   assert(AlignInBytes == 0 || llvm::isPowerOf2_32(AlignInBytes));
   addSource(ByteCount);
 }
 
@@ skipping 39 matching lines @@
       TargetTrue(NULL) {}
 
 NodeList InstBr::getTerminatorEdges() const {
   NodeList OutEdges;
   OutEdges.push_back(TargetFalse);
   if (TargetTrue)
     OutEdges.push_back(TargetTrue);
   return OutEdges;
 }
 
+bool InstBr::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+  if (TargetFalse == OldNode) {
+    TargetFalse = NewNode;
+    return true;
+  } else if (TargetTrue == OldNode) {
+    TargetTrue = NewNode;
+    return true;
+  }
+  return false;

[jvoung (off chromium), 2014/10/27 22:12:21]

Should this always succeed or no (only be one terminator in block)?

[Jim Stichnoth, 2014/10/28 01:20:14]

It should fail (return false) only if something gets out of sync between the
CfgNode edges and the branch instruction.  Note that the caller,
splitIncomingEdge(), asserts that some repointing was successful.

+}
+
 InstCast::InstCast(Cfg *Func, OpKind CastKind, Variable *Dest, Operand *Source)
     : InstHighLevel(Func, Inst::Cast, 1, Dest), CastKind(CastKind) {
   addSource(Source);
 }
 
 InstExtractElement::InstExtractElement(Cfg *Func, Variable *Dest,
                                        Operand *Source1, Operand *Source2)
     : InstHighLevel(Func, Inst::ExtractElement, 2, Dest) {
   addSource(Source1);
   addSource(Source2);
@@ skipping 129 matching lines @@
 
 NodeList InstSwitch::getTerminatorEdges() const {
   NodeList OutEdges;
   OutEdges.push_back(LabelDefault);
   for (SizeT I = 0; I < NumCases; ++I) {
     OutEdges.push_back(Labels[I]);
   }
   return OutEdges;
 }
 
+bool InstSwitch::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+  if (LabelDefault == OldNode) {
+    LabelDefault = NewNode;
+    return true;
+  }
+  for (SizeT I = 0; I < NumCases; ++I) {
+    if (Labels[I] == OldNode) {
+      Labels[I] = NewNode;
+      return true;
+    }
+  }
+  return false;
+}
+
 InstUnreachable::InstUnreachable(Cfg *Func)
     : InstHighLevel(Func, Inst::Unreachable, 0, NULL) {}
 
 InstFakeDef::InstFakeDef(Cfg *Func, Variable *Dest, Variable *Src)
     : InstHighLevel(Func, Inst::FakeDef, Src ? 1 : 0, Dest) {
   assert(Dest);
   if (Src)
     addSource(Src);
 }
 
@@ skipping 328 matching lines @@
   dumpSources(Func);
 }
 
 void InstTarget::dump(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   Str << "[TARGET] ";
   Inst::dump(Func);
 }
 
 } // end of namespace Ice