Subzero: Initial O2 lowering

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
 // subclass constructors and dump routines.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 
 namespace Ice {
 
 namespace {
 
 // Using non-anonymous struct so that array_lengthof works.
 const struct InstArithmeticAttributes_ {
   const char *DisplayString;
   bool IsCommutative;
@@ skipping 39 matching lines @@
   { str }                                                                      \
   ,
     ICEINSTICMP_TABLE
 #undef X
   };
 const size_t InstIcmpAttributesSize = llvm::array_lengthof(InstIcmpAttributes);
 
 } // end of anonymous namespace
 
 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
-    : Kind(Kind), Number(Func->newInstNumber()), Deleted(false),
+    : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false),
       HasSideEffects(false), Dest(Dest), MaxSrcs(MaxSrcs), NumSrcs(0),
-      Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)) {}
+      Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {}
+
+// Assign the instruction a new number.
+void Inst::renumber(Cfg *Func) {
+  Number = isDeleted() ? -1 : Func->newInstNumber();
+}
+
+// Delete the instruction if its tentative Dead flag is still set
+// after liveness analysis.
+void Inst::deleteIfDead() {
+  if (Dead)
+    setDeleted();
+}
+
+// If Src is an Variable, it returns true if this instruction ends

[jvoung (off chromium), 2014/05/28 17:48:15]

"is a Variable"?

[Jim Stichnoth, 2014/05/29 01:39:46]

Fixed this and several other instances. :)  (This was because Ice::Variable used
to be IceVariable.)

+// Src's live range.  Otherwise, returns false.
+bool Inst::isLastUse(const Operand *TestSrc) const {
+  if (LiveRangesEnded == 0)
+    return false; // early-exit optimization
+  if (const Variable *TestVar = llvm::dyn_cast<const Variable>(TestSrc)) {
+    SizeT VarIndex = 0;

[jvoung (off chromium), 2014/05/28 17:48:15]

VarIndex unused here (just incremented)? Looks like this is handled by shifting
the Mask and testing & 1, instead of using VarIndex.

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+    SizeT Mask = LiveRangesEnded;

[JF, 2014/05/25 22:50:50]

You should use the same typedef for LiveRangesEnded.

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+    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);
+        if (Var == TestVar) {
+          // We've found where the variable is used in the instruction.
+          return Mask & 1;
+        }
+        Mask >>= 1;
+        if (Mask == 0)
+          return false; // another early-exit optimization
+      }
+    }
+  }
+  return false;
+}
 
 void Inst::updateVars(CfgNode *Node) {
   if (Dest)
     Dest->setDefinition(this, Node);
 
   SizeT VarIndex = 0;

[jvoung (off chromium), 2014/05/28 17:48:15]

VarIndex also unused here (just incremented)?

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

   for (SizeT I = 0; I < getSrcSize(); ++I) {
     Operand *Src = getSrc(I);
     SizeT NumVars = Src->getNumVars();
     for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
       Variable *Var = Src->getVar(J);
       Var->setUse(this, Node);
     }
   }
 }
 
+void Inst::liveness(LivenessMode Mode, int32_t InstNumber,
+                    llvm::BitVector &Live, Liveness *Liveness,
+                    const CfgNode *Node) {
+  if (isDeleted())
+    return;
+  if (llvm::isa<InstFakeKill>(this))
+    return;
+
+  // For lightweight liveness, do the simple calculation and return.
+  if (Mode == Liveness_LREndLightweight) {
+    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);
+        if (Var->isMultiblockLife())
+          continue;
+        SizeT Index = Var->getIndex();
+        if (Live[Index])
+          continue;
+        Live[Index] = true;
+        setLastUse(VarIndex);

[jvoung (off chromium), 2014/05/28 17:48:15]

I see... so VarIndex is an optimized, different numbering than Var->getIndex(),
limited to < 32.

I guess I'm wondering if it's worth this optimization when there are 3(?) types
of indexing, and you need to remember which index to use when.

Var->getIndex()
VarIndex
Liveness->getLiveIndex(Var)

It seems to depend on the LivenessMode:
* Live[Index] for Liveness_LREndLightweight, w/ Index being from Var->getIndex.
* Live[VarNum] where VarNum comes from Liveness->getLiveIndex(), otherwise.

Maybe a better split between the code for the different LivenessModes?

[Jim Stichnoth, 2014/05/29 01:39:46]

OK, it looks like I never properly documented VarIndex and
Inst::LiveRangesEnded.  The purpose of LiveRangesEnded is to mark which
Variables' live ranges end in this instruction.  An instruction can have an
arbitrary number of source operands (e.g. a call instruction), and each source
operand can contain 0, 1, or more Variables (x86 mem operands can have 2
registers).  I tried out several ways to deal with this, balancing time, space,
and simplicity, and this was the best mechanism I came up with (or perhaps the
least icky mechanism).

Note that VarIndex/LiveRangesEnded is a property of the instruction, whereas
Var->getIndex() and Liveness->getLiveIndex(Var) are properties of the Variable.

+      }
+    }
+    return;
+  }
+
+  std::vector<int32_t> &LiveBegin = Liveness->getLiveBegin(Node);
+  std::vector<int32_t> &LiveEnd = Liveness->getLiveEnd(Node);
+  Dead = false;
+  if (Dest) {
+    SizeT VarNum = Liveness->getLiveIndex(Dest);
+    if (Live[VarNum]) {
+      Live[VarNum] = false;
+      LiveBegin[VarNum] = InstNumber;
+    } else {
+      if (!hasSideEffects())
+        Dead = true;
+    }
+  }
+  if (Dead)
+    return;
+  // 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);
+      SizeT VarNum = Liveness->getLiveIndex(Var);
+      if (!Live[VarNum]) {
+        setLastUse(VarIndex);
+        if (!IsPhi) {
+          Live[VarNum] = true;
+          // For a variable in SSA form, its live range can end at
+          // most once in a basic block.  However, after lowering to
+          // two-address instructions, we end up with sequences like
+          // "t=b;t+=c;a=t" where t's live range begins and ends
+          // twice.  ICE only allows a variable to have a single
+          // liveness interval in a basic block (except for blocks
+          // where a variable is live-in and live-out but there is a
+          // gap in the middle, and except for the special
+          // InstFakeKill instruction that can appear multiple
+          // times in the same block).  Therefore, this lowered
+          // sequence needs to represent a single conservative live
+          // range for t.  Since the instructions are being traversed
+          // backwards, we make sure LiveEnd is only set once by
+          // setting it only when LiveEnd[VarNum]==0 (sentinel value).
+          // Note that it's OK to set LiveBegin multiple times because
+          // of the backwards traversal.
+          if (LiveEnd[VarNum] == 0) {
+            LiveEnd[VarNum] = InstNumber;
+          }
+        }
+      }
+    }
+  }
+}
+
 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
                        Variable *Dest)
     : Inst(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);
 }
 
 InstArithmetic::InstArithmetic(Cfg *Func, OpKind Op, Variable *Dest,
                                Operand *Source1, Operand *Source2)
@@ skipping 79 matching lines @@
 // improved if it becomes a problem.
 Operand *InstPhi::getOperandForTarget(CfgNode *Target) const {
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     if (Labels[I] == Target)
       return getSrc(I);
   }
   llvm_unreachable("Phi target not found");
   return NULL;
 }
 
+// Updates liveness for a particular operand based on the given
+// predecessor edge.  Doesn't mark the operand as live if the Phi
+// instruction is dead or deleted.
+void InstPhi::livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target,
+                                 Liveness *Liveness) {
+  if (isDeleted() || Dead)
+    return;
+  for (SizeT I = 0; I < getSrcSize(); ++I) {
+    if (Labels[I] == Target) {
+      if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) {
+        SizeT SrcIndex = Liveness->getLiveIndex(Var);
+        if (!Live[SrcIndex]) {
+          setLastUse(I);
+          Live[SrcIndex] = true;
+        }
+      }
+      return;
+    }
+  }
+  llvm_unreachable("Phi operand not found for specified target node");
+}
+
 // Change "a=phi(...)" to "a_phi=phi(...)" and return a new
 // instruction "a=a_phi".
 Inst *InstPhi::lower(Cfg *Func, CfgNode *Node) {
   Variable *Dest = getDest();
   assert(Dest);
   IceString PhiName = Dest->getName() + "_phi";
   Variable *NewSrc = Func->makeVariable(Dest->getType(), Node, PhiName);
   this->Dest = NewSrc;
   InstAssign *NewInst = InstAssign::create(Func, Dest, NewSrc);
   // Set Dest and NewSrc to have affinity with each other, as a hint
@@ skipping 93 matching lines @@
     if (Number < 0)
       snprintf(buf, llvm::array_lengthof(buf), "[XXX]");
     else
       snprintf(buf, llvm::array_lengthof(buf), "[%3d]", Number);
     Str << buf;
   }
   Str << "  ";
   if (isDeleted())
     Str << "  //";
   dump(Func);
+  dumpExtras(Func);
   Str << "\n";
 }
 
 void Inst::emit(const Cfg * /*Func*/) const {
   llvm_unreachable("emit() called on a non-lowered instruction");
 }
 
 void Inst::dump(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   dumpDest(Func);
   Str << " =~ ";
   dumpSources(Func);
 }
 
+void Inst::dumpExtras(const Cfg *Func) const {
+  Ostream &Str = Func->getContext()->getStrDump();
+  bool First = true;
+  // Print "LIVEEND={a,b,c}" for all source operands whose live ranges
+  // are known to end at this instruction.
+  if (Func->getContext()->isVerbose(IceV_Liveness)) {
+    SizeT VarIndex = 0;

[jvoung (off chromium), 2014/05/28 17:48:15]

VarIndex unused?

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+    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);
+        if (isLastUse(Var)) {
+          if (First)
+            Str << " // LIVEEND={";
+          else
+            Str << ",";
+          Var->dump(Func);
+          First = false;
+        }
+      }
+    }
+    if (!First)
+      Str << "}";
+  }
+}
+
 void Inst::dumpSources(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     if (I > 0)
       Str << ", ";
     getSrc(I)->dump(Func);
   }
 }
 
 void Inst::emitSources(const Cfg *Func) const {
@@ skipping 214 matching lines @@
   Str << "kill.pseudo ";
   dumpSources(Func);
 }
 
 void InstTarget::dump(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   Str << "[TARGET] ";
   Inst::dump(Func);
 }
 
+void InstTarget::dumpExtras(const Cfg *Func) const { Inst::dumpExtras(Func); }
+
 } // end of namespace Ice