Initial skeleton of Subzero.

src/IceInst.cpp

Index: src/IceInst.cpp
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..3f5fd82305fb30f01282b19d9985d160353f1233
--- /dev/null
+++ b/src/IceInst.cpp
@@ -0,0 +1,585 @@
+//===- 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 IceInst class, primarily the various
+// subclass constructors and dump routines.
+//
+//===----------------------------------------------------------------------===//
+
+#include "IceCfg.h"
+#include "IceCfgNode.h"
+#include "IceInst.h"
+#include "IceOperand.h"
+
+IceInst::IceInst(IceCfg *Cfg, InstKind Kind, uint32_t MaxSrcs,
+                 IceVariable *Dest)
+    : Kind(Kind), Deleted(false), HasSideEffects(false), Dest(Dest),
+      MaxSrcs(MaxSrcs), NumSrcs(0) {
+  Number = Cfg->newInstNumber();
+  Srcs = Cfg->allocateArrayOf<IceOperand *>(MaxSrcs);

[JF, 2014/04/16 01:27:32]

Move to the initialization list.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+}
+
+void IceInst::updateVars(IceCfgNode *Node) {
+  if (Dest)
+    Dest->setDefinition(this, Node);
+  for (uint32_t I = 0; I < getSrcSize(); ++I) {
+    getSrc(I)->setUse(this, Node);
+  }
+}
+
+IceInstAlloca::IceInstAlloca(IceCfg *Cfg, IceOperand *ByteCount, uint32_t Align,
+                             IceVariable *Dest)
+    : IceInst(Cfg, IceInst::Alloca, 1, Dest), Align(Align) {
+  addSource(ByteCount);
+}
+
+IceInstArithmetic::IceInstArithmetic(IceCfg *Cfg, OpKind Op, IceVariable *Dest,
+                                     IceOperand *Source1, IceOperand *Source2)
+    : IceInst(Cfg, IceInst::Arithmetic, 2, Dest), Op(Op) {
+  addSource(Source1);
+  addSource(Source2);
+}
+
+bool IceInstArithmetic::isCommutative() const {
+  switch (getOp()) {
+  case Add:
+  case Fadd:
+  case Mul:
+  case Fmul:

[JF, 2014/04/16 01:27:32]

Fadd and Fmul aren't commutative.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.  I was sad to learn this.

[Jim Stichnoth, 2015/09/25 17:23:09]

LLVM disagrees... see Instruction::isCommutative() in
llvm/lib/IR/Instruction.cpp

+  case And:
+  case Or:
+  case Xor:
+    return true;
+  default:

[JF, 2014/04/16 01:27:32]

It would be better to list everything so that if you add a new type of
arithmetic operation the compiler sees that you don't handle all cases and gives
you a warning.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.  And converted to x-macros.

+    return false;
+  }
+}
+
+IceInstAssign::IceInstAssign(IceCfg *Cfg, IceVariable *Dest, IceOperand *Source)
+    : IceInst(Cfg, IceInst::Assign, 1, Dest) {
+  addSource(Source);
+}
+
+// If TargetTrue==TargetFalse, we turn it into an unconditional
+// branch.  This ensures that, along with the 'switch' instruction
+// semantics, there is at most one edge from one node to another.
+IceInstBr::IceInstBr(IceCfg *Cfg, IceOperand *Source, IceCfgNode *TargetTrue,
+                     IceCfgNode *TargetFalse)
+    : IceInst(Cfg, IceInst::Br, 1, NULL), TargetFalse(TargetFalse),
+      TargetTrue(TargetTrue) {
+  if (TargetTrue == TargetFalse) {
+    TargetTrue = NULL; // turn into unconditional version
+  } else {
+    addSource(Source);

[JF, 2014/04/16 01:27:32]

It doesn't look like you have an invariant on True==False w.r.t. Source's value.
What happens if a users does getSrc(0) on an unconditional branch?

Would it be cleaner if conditional and unconditional were separate instructions?

[Jim Stichnoth, 2014/04/21 20:26:40]

You crash, of course. :)  Here and in all other instructions, the user is
supposed to make sure their src/dest accesses are valid.  For the branch
instruction, that means testing for !isUnconditional() before accessing the
source operand.  I think the right thing to do here is to add a getCondition()
accessor that at a minimum gives a slightly more informative assert() when
called incorrectly.
I'd rather keep it combined because: (1) LLVM has a single branch instruction so
there's precedent, familiarity, etc.; (2) for the lowered branch instruction,
there are actually 4 variants - conditional versus unconditional, and target
being an intra-block instruction versus the more usual target being the first
instruction of a basic block - so I'd rather not get too deep into that mess.

+  }
+}
+
+IceInstBr::IceInstBr(IceCfg *Cfg, IceCfgNode *Target)
+    : IceInst(Cfg, IceInst::Br, 0, NULL), TargetFalse(Target),
+      TargetTrue(NULL) {}
+
+IceNodeList IceInstBr::getTerminatorEdges() const {
+  IceNodeList OutEdges;
+  OutEdges.push_back(TargetFalse);
+  if (TargetTrue)
+    OutEdges.push_back(TargetTrue);
+  return OutEdges;
+}
+
+IceInstCast::IceInstCast(IceCfg *Cfg, OpKind CastKind, IceVariable *Dest,
+                         IceOperand *Source)
+    : IceInst(Cfg, IceInst::Cast, 1, Dest), CastKind(CastKind) {
+  addSource(Source);
+}
+
+IceInstFcmp::IceInstFcmp(IceCfg *Cfg, FCond Condition, IceVariable *Dest,
+                         IceOperand *Source1, IceOperand *Source2)
+    : IceInst(Cfg, IceInst::Fcmp, 2, Dest), Condition(Condition) {
+  addSource(Source1);
+  addSource(Source2);
+}
+
+IceInstIcmp::IceInstIcmp(IceCfg *Cfg, ICond Condition, IceVariable *Dest,
+                         IceOperand *Source1, IceOperand *Source2)
+    : IceInst(Cfg, IceInst::Icmp, 2, Dest), Condition(Condition) {
+  addSource(Source1);
+  addSource(Source2);
+}
+
+IceInstLoad::IceInstLoad(IceCfg *Cfg, IceVariable *Dest, IceOperand *SourceAddr)
+    : IceInst(Cfg, IceInst::Load, 1, Dest) {
+  addSource(SourceAddr);
+}
+
+IceInstPhi::IceInstPhi(IceCfg *Cfg, uint32_t MaxSrcs, IceVariable *Dest)
+    : IceInst(Cfg, Phi, MaxSrcs, Dest) {
+  Labels = Cfg->allocateArrayOf<IceCfgNode *>(MaxSrcs);
+}
+
+// TODO: A Switch instruction (and maybe others) can add duplicate
+// edges.  We may want to de-dup Phis and validate consistency (i.e.,
+// the source operands are the same for duplicate edges), though it
+// seems the current lowering code is OK with this situation.
+void IceInstPhi::addArgument(IceOperand *Source, IceCfgNode *Label) {
+  Labels[getSrcSize()] = Label;
+  addSource(Source);
+}
+
+IceInstRet::IceInstRet(IceCfg *Cfg, IceOperand *Source)
+    : IceInst(Cfg, Ret, Source ? 1 : 0, NULL) {
+  if (Source)
+    addSource(Source);
+}
+
+IceInstSelect::IceInstSelect(IceCfg *Cfg, IceVariable *Dest,
+                             IceOperand *Condition, IceOperand *SourceTrue,
+                             IceOperand *SourceFalse)
+    : IceInst(Cfg, IceInst::Select, 3, Dest) {
+  assert(Condition->getType() == IceType_i1);
+  addSource(Condition);
+  addSource(SourceTrue);
+  addSource(SourceFalse);
+}
+
+IceInstStore::IceInstStore(IceCfg *Cfg, IceOperand *Data, IceOperand *Addr)
+    : IceInst(Cfg, IceInst::Store, 2, NULL) {
+  addSource(Data);
+  addSource(Addr);
+}
+
+IceInstSwitch::IceInstSwitch(IceCfg *Cfg, uint32_t NumCases, IceOperand *Source,
+                             IceCfgNode *LabelDefault)
+    : IceInst(Cfg, IceInst::Switch, 1, NULL), LabelDefault(LabelDefault),
+      NumCases(NumCases) {
+  addSource(Source);
+  Values = Cfg->allocateArrayOf<uint64_t>(NumCases);
+  Labels = Cfg->allocateArrayOf<IceCfgNode *>(NumCases);
+  // Initialize in case buggy code doesn't set all entries
+  for (uint32_t I = 0; I < NumCases; ++I) {
+    Values[I] = 0;
+    Labels[I] = NULL;
+  }
+}
+
+void IceInstSwitch::addBranch(uint32_t CaseIndex, uint64_t Value,
+                              IceCfgNode *Label) {
+  assert(CaseIndex < NumCases);
+  Values[CaseIndex] = Value;
+  Labels[CaseIndex] = Label;
+}
+
+IceNodeList IceInstSwitch::getTerminatorEdges() const {
+  IceNodeList OutEdges;
+  OutEdges.push_back(LabelDefault);
+  for (uint32_t I = 0; I < NumCases; ++I) {
+    OutEdges.push_back(Labels[I]);
+  }
+  return OutEdges;
+}
+
+IceInstUnreachable::IceInstUnreachable(IceCfg *Cfg)
+    : IceInst(Cfg, IceInst::Unreachable, 0, NULL) {}
+
+// ======================== Dump routines ======================== //
+
+void IceInst::dumpDecorated(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  if (!Cfg->getContext()->isVerbose(IceV_Deleted) && isDeleted())
+    return;
+  if (Cfg->getContext()->isVerbose(IceV_InstNumbers)) {
+    char buf[30];
+    int32_t Number = getNumber();
+    if (Number < 0)
+      sprintf(buf, "[XXX]");
+    else
+      sprintf(buf, "[%3d]", Number);
+    Str << buf;
+  }
+  Str << "  ";
+  if (isDeleted())
+    Str << "  //";
+  dump(Cfg);
+  Str << "\n";
+}
+
+void IceInst::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " =~ ";
+  dumpSources(Cfg);
+}
+
+void IceInst::dumpSources(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  for (uint32_t I = 0; I < getSrcSize(); ++I) {
+    if (I > 0)
+      Str << ", ";
+    getSrc(I)->dump(Cfg);
+  }
+}
+
+void IceInst::dumpDest(const IceCfg *Cfg) const {
+  if (getDest())
+    getDest()->dump(Cfg);
+}
+
+void IceInstAlloca::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = alloca i8, i32 ";
+  getSrc(0)->dump(Cfg);
+  Str << ", align " << Align;
+}
+
+void IceInstArithmetic::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = ";
+  switch (getOp()) {
+  case Add:
+    Str << "add";
+    break;
+  case Fadd:
+    Str << "fadd";
+    break;
+  case Sub:
+    Str << "sub";
+    break;
+  case Fsub:
+    Str << "fsub";
+    break;
+  case Mul:
+    Str << "mul";
+    break;
+  case Fmul:
+    Str << "fmul";
+    break;
+  case Udiv:
+    Str << "udiv";
+    break;
+  case Sdiv:
+    Str << "sdiv";
+    break;
+  case Fdiv:
+    Str << "fdiv";
+    break;
+  case Urem:
+    Str << "urem";
+    break;
+  case Srem:
+    Str << "srem";
+    break;
+  case Frem:
+    Str << "frem";
+    break;
+  case Shl:
+    Str << "shl";
+    break;
+  case Lshr:
+    Str << "lshr";
+    break;
+  case Ashr:
+    Str << "ashr";
+    break;
+  case And:
+    Str << "and";
+    break;
+  case Or:
+    Str << "or";
+    break;
+  case Xor:
+    Str << "xor";
+    break;

[JF, 2014/04/16 01:27:32]

Another place where xmacros would be nice ;-)

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+  }
+  Str << " " << getDest()->getType() << " ";
+  dumpSources(Cfg);
+}
+
+void IceInstAssign::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = " << getDest()->getType() << " ";
+  dumpSources(Cfg);
+}
+
+void IceInstBr::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << "br ";
+  if (!isUnconditional()) {
+    Str << "i1 ";
+    getSrc(0)->dump(Cfg);
+    Str << ", label %" << getTargetTrue()->getName() << ", ";
+  }
+  Str << "label %" << getTargetFalse()->getName();
+}
+
+void IceInstCall::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  if (getDest()) {
+    dumpDest(Cfg);
+    Str << " = ";
+  }
+  if (Tail)
+    Str << "tail ";
+  Str << "call ";
+  if (getDest())
+    Str << getDest()->getType();
+  else
+    Str << "void";
+  Str << " ";
+  getCallTarget()->dump(Cfg);
+  Str << "(";
+  for (uint32_t I = 0; I < getNumArgs(); ++I) {
+    if (I > 0)
+      Str << ", ";
+    Str << getArg(I)->getType() << " ";
+    getArg(I)->dump(Cfg);
+  }
+  Str << ")";
+}
+
+void IceInstCast::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = ";
+  switch (getCastKind()) {
+  default:
+    Str << "UNKNOWN";
+    assert(0);
+    break;
+  case Trunc:
+    Str << "trunc";
+    break;
+  case Zext:
+    Str << "zext";
+    break;
+  case Sext:
+    Str << "sext";
+    break;
+  case Fptrunc:
+    Str << "fptrunc";
+    break;
+  case Fpext:
+    Str << "fpext";
+    break;
+  case Fptoui:
+    Str << "fptoui";
+    break;
+  case Fptosi:
+    Str << "fptosi";
+    break;
+  case Uitofp:
+    Str << "uitofp";
+    break;
+  case Sitofp:
+    Str << "sitofp";
+    break;
+  case Bitcast:
+    Str << "bitcast";
+    break;

[JF, 2014/04/16 01:27:32]

xmacros :-)

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+  }
+  Str << " " << getSrc(0)->getType() << " ";
+  dumpSources(Cfg);
+  Str << " to " << getDest()->getType();
+}
+
+void IceInstIcmp::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = icmp ";
+  switch (getCondition()) {
+  case Eq:
+    Str << "eq";
+    break;
+  case Ne:
+    Str << "ne";
+    break;
+  case Ugt:
+    Str << "ugt";
+    break;
+  case Uge:
+    Str << "uge";
+    break;
+  case Ult:
+    Str << "ult";
+    break;
+  case Ule:
+    Str << "ule";
+    break;
+  case Sgt:
+    Str << "sgt";
+    break;
+  case Sge:
+    Str << "sge";
+    break;
+  case Slt:
+    Str << "slt";
+    break;
+  case Sle:
+    Str << "sle";
+    break;

[JF, 2014/04/16 01:27:32]

Ditto.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+  }
+  Str << " " << getSrc(0)->getType() << " ";
+  dumpSources(Cfg);
+}
+
+void IceInstFcmp::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = fcmp ";
+
+  switch (getCondition()) {
+  case False:
+    Str << "false";
+    break;
+  case Oeq:
+    Str << "oeq";
+    break;
+  case Ogt:
+    Str << "ogt";
+    break;
+  case Oge:
+    Str << "oge";
+    break;
+  case Olt:
+    Str << "olt";
+    break;
+  case Ole:
+    Str << "ole";
+    break;
+  case One:
+    Str << "one";
+    break;
+  case Ord:
+    Str << "ord";
+    break;
+  case Ueq:
+    Str << "ueq";
+    break;
+  case Ugt:
+    Str << "ugt";
+    break;
+  case Uge:
+    Str << "uge";
+    break;
+  case Ult:
+    Str << "ult";
+    break;
+  case Ule:
+    Str << "ule";
+    break;
+  case Une:
+    Str << "une";
+    break;
+  case Uno:
+    Str << "uno";
+    break;
+  case True:
+    Str << "true";
+    break;

[JF, 2014/04/16 01:27:32]

Ditto.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+  }
+  Str << " " << getSrc(0)->getType() << " ";
+  dumpSources(Cfg);
+}
+
+void IceInstLoad::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  IceType Type = getDest()->getType();
+  Str << " = load " << Type << "* ";
+  dumpSources(Cfg);
+  switch (Type) {
+  case IceType_f32:
+    Str << ", align 4";
+    break;
+  case IceType_f64:
+    Str << ", align 8";
+    break;
+  default:
+    Str << ", align 1";
+    break;
+  }
+}
+
+void IceInstStore::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  IceType Type = getData()->getType();
+  Str << "store " << Type << " ";
+  getData()->dump(Cfg);
+  Str << ", " << Type << "* ";
+  getAddr()->dump(Cfg);
+  Str << ", align ";
+  switch (Type) {
+  case IceType_f32:
+    Str << "4";
+    break;
+  case IceType_f64:
+    Str << "8";
+    break;
+  default:
+    Str << "1";
+    break;
+  }
+}
+
+void IceInstSwitch::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  IceType Type = getSrc(0)->getType();
+  Str << "switch " << Type << " ";
+  getSrc(0)->dump(Cfg);
+  Str << ", label %" << getLabelDefault()->getName() << " [\n";
+  for (uint32_t I = 0; I < getNumCases(); ++I) {
+    Str << "    " << Type << " " << getValue(I) << ", label %"
+        << getLabel(I)->getName() << "\n";
+  }
+  Str << "  ]";
+}
+
+void IceInstPhi::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  Str << " = phi " << getDest()->getType() << " ";
+  for (uint32_t I = 0; I < getSrcSize(); ++I) {
+    if (I > 0)
+      Str << ", ";
+    Str << "[ ";
+    getSrc(I)->dump(Cfg);
+    Str << ", %" << Labels[I]->getName() << " ]";
+  }
+}
+
+void IceInstRet::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  IceType Type = getSrcSize() == 0 ? IceType_void : getSrc(0)->getType();
+  Str << "ret " << Type;
+  if (getSrcSize()) {
+    Str << " ";
+    dumpSources(Cfg);
+  }
+}
+
+void IceInstSelect::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  dumpDest(Cfg);
+  IceOperand *Condition = getCondition();
+  IceOperand *TrueOp = getTrueOperand();
+  IceOperand *FalseOp = getFalseOperand();
+  Str << " = select " << Condition->getType() << " ";
+  Condition->dump(Cfg);
+  Str << ", " << TrueOp->getType() << " ";
+  TrueOp->dump(Cfg);
+  Str << ", " << FalseOp->getType() << " ";
+  FalseOp->dump(Cfg);
+}
+
+void IceInstUnreachable::dump(const IceCfg *Cfg) const {
+  IceOstream &Str = Cfg->getContext()->StrDump;
+  Str << "unreachable";
+}