Introduction of improved switch 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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements the Inst class, primarily the various
 /// subclass constructors and dump routines.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceInst.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
+#include "IceTargetLowering.h"
 
 namespace Ice {
 
 namespace {
 
 // Using non-anonymous struct so that array_lengthof works.
 const struct InstArithmeticAttributes_ {
   const char *DisplayString;
   bool IsCommutative;
 } InstArithmeticAttributes[] = {
@@ skipping 256 matching lines @@
 
 NodeList InstBr::getTerminatorEdges() const {
   NodeList OutEdges;
   OutEdges.reserve(TargetTrue ? 2 : 1);
   OutEdges.push_back(TargetFalse);
   if (TargetTrue)
     OutEdges.push_back(TargetTrue);
   return OutEdges;
 }
 
-bool InstBr::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+bool InstBr::repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
+  bool Found = false;
   if (TargetFalse == OldNode) {
     TargetFalse = NewNode;
-    return true;
-  } else if (TargetTrue == OldNode) {
+    Found = true;
+  }
+  if (TargetTrue == OldNode) {
     TargetTrue = NewNode;
-    return true;
+    Found = true;
   }
-  return false;
+  return Found;
 }
 
 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) {
@@ skipping 137 matching lines @@
   Labels[CaseIndex] = Label;
 }
 
 NodeList InstSwitch::getTerminatorEdges() const {
   NodeList OutEdges;
   OutEdges.reserve(NumCases + 1);
   OutEdges.push_back(LabelDefault);
   for (SizeT I = 0; I < NumCases; ++I) {
     OutEdges.push_back(Labels[I]);
   }
+  std::sort(OutEdges.begin(), OutEdges.end());

[Jim Stichnoth, 2015/07/15 19:17:42]

What is the comparison function here?  It needs to be something deterministic
and not address-based so that we can ensure deterministic execution across
different runs and even different platforms.

Ideally the comparison would be on node numbers.

[ascull, 2015/07/16 19:38:45]

Done.

+  auto last = std::unique(OutEdges.begin(), OutEdges.end());

[Jim Stichnoth, 2015/07/15 19:17:42]

capitalize Last per LLVM convention

[ascull, 2015/07/16 19:38:45]

Done.

+  OutEdges.erase(last, OutEdges.end());
   return OutEdges;
 }
 
-bool InstSwitch::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+bool InstSwitch::repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
+  bool Found = false;
   if (LabelDefault == OldNode) {
     LabelDefault = NewNode;
-    return true;
+    Found = true;
   }
   for (SizeT I = 0; I < NumCases; ++I) {
     if (Labels[I] == OldNode) {
       Labels[I] = NewNode;
-      return true;
+      Found = true;
     }
   }
-  return false;
+  return Found;
 }
 
 InstUnreachable::InstUnreachable(Cfg *Func)
     : InstHighLevel(Func, Inst::Unreachable, 0, nullptr) {}
 
 InstBundleLock::InstBundleLock(Cfg *Func, InstBundleLock::Option BundleOption)
     : InstHighLevel(Func, Inst::BundleLock, 0, nullptr),
       BundleOption(BundleOption) {}
 
 InstBundleUnlock::InstBundleUnlock(Cfg *Func)
     : InstHighLevel(Func, Inst::BundleUnlock, 0, nullptr) {}
 
 InstFakeDef::InstFakeDef(Cfg *Func, Variable *Dest, Variable *Src)
     : InstHighLevel(Func, Inst::FakeDef, Src ? 1 : 0, Dest) {
   assert(Dest);
   if (Src)
     addSource(Src);
 }
 
 InstFakeUse::InstFakeUse(Cfg *Func, Variable *Src)
     : InstHighLevel(Func, Inst::FakeUse, 1, nullptr) {
   assert(Src);
   addSource(Src);
 }
 
 InstFakeKill::InstFakeKill(Cfg *Func, const Inst *Linked)
     : InstHighLevel(Func, Inst::FakeKill, 0, nullptr), Linked(Linked) {}
 
+InstJumpTable::InstJumpTable(Cfg *Func, SizeT NumTargets, CfgNode *Default)
+  : InstHighLevel(Func, Inst::JumpTable, 1, nullptr),
+    Number(Func->getTarget()->makeNextLabelNumber()), NumTargets(NumTargets) {
+  Targets = Func->allocateArrayOf<CfgNode *>(NumTargets);
+  for (SizeT I = 0; I < NumTargets; ++I)
+    Targets[I] = Default;

[Jim Stichnoth, 2015/07/15 19:17:42]

For safety, maybe all of these could be initialized to nullptr except for the
entry that actually represents the default target?

[ascull, 2015/07/16 19:38:45]

Every element of the jump table can be jumped to so if it doesn't match a case
it should go to the default case (since it can be sparse). What do you mean by
safety in this case?

+}
+
+bool InstJumpTable::repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
+  bool Found = false;
+  for (SizeT I = 0; I < NumTargets; ++I) {
+    if (Targets[I] == OldNode) {
+      Targets[I] = NewNode;
+      Found = true;
+    }
+  }
+  return Found;
+}
+
+IceString InstJumpTable::getName(const Cfg *Func) const {
+  return ".L" + Func->getFunctionName()
+       + "$jumptable$__" + std::to_string(Number);
+}
+
 Type InstCall::getReturnType() const {
   if (Dest == nullptr)
     return IceType_void;
   return Dest->getType();
 }
 
 // ======================== Dump routines ======================== //
 
 void Inst::dumpDecorated(const Cfg *Func) const {
   if (!BuildDefs::dump())
@@ skipping 393 matching lines @@
 
 void InstFakeKill::dump(const Cfg *Func) const {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrDump();
   if (Linked->isDeleted())
     Str << "// ";
   Str << "kill.pseudo scratch_regs";
 }
 
+void InstJumpTable::emit(const Cfg *Func) const {

[Jim Stichnoth, 2015/07/15 19:17:42]

This should be tied in to the target data lowering.

In fact, any subclass of InstHighLevel should not have an emit() or emitIAS()
method (and we should probably declare those as final in InstHighLevel).

[ascull, 2015/07/16 19:38:45]

I'm going to be doing this for emitIAS which is still to come, is it OK to leave
a TODO for now?

[Jim Stichnoth, 2015/07/17 15:33:47]

TODO is fine for now, thanks.

+  // TODO(ascull): should this be a target specific lowering (with access built
+  // in?) and just have InstJumpTable as a high level, similar to br? or should
+  // this follow the same path as emitIAS i.e. put it in global context and
+  // produce this code later?
+  if (!BuildDefs::dump())
+    return;
+  Ostream &Str = Func->getContext()->getStrEmit();
+  // TODO(ascull): softcode pointer size of 4
+  // TODO(ascull): is .long portable?
+  Str << "\n\t.section\t.rodata."
+      << Func->getFunctionName() << "$jumptable,\"a\",@progbits\n"
+      << "\t.align 4\n"
+      << getName(Func) << ":";
+  for (SizeT I = 0; I < NumTargets; ++I)
+    Str << "\n\t.long\t" << Targets[I]->getAsmName();
+  Str << "\n\n\t.text";
+}
+void InstJumpTable::emitIAS(const Cfg *Func) const {

[jvoung (off chromium), 2015/07/15 18:32:01]

add a newline between functions

[ascull, 2015/07/16 19:38:45]

Done.

+  // TODO(ascull): put jump table in the global context for emision later

[jvoung (off chromium), 2015/07/15 18:32:01]

emision -> emission

[ascull, 2015/07/16 19:38:45]

Done.

+  (void)Func;
+}
+
+void InstJumpTable::dump(const Cfg *Func) const {
+  if (!BuildDefs::dump())
+    return;
+  Ostream &Str = Func->getContext()->getStrDump();
+  Str << "jump table [";
+  for (SizeT I = 0; I < NumTargets; ++I)
+    Str << "\n    " << Targets[I]->getName();
+  Str << "\n  ]";
+}
+
 void InstTarget::dump(const Cfg *Func) const {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrDump();
   Str << "[TARGET] ";
   Inst::dump(Func);
 }
 
 bool checkForRedundantAssign(const Variable *Dest, const Operand *Source) {
   const auto SrcVar = llvm::dyn_cast<const Variable>(Source);
   if (!SrcVar)
     return false;
   if (Dest->hasReg() && Dest->getRegNum() == SrcVar->getRegNum()) {
     // TODO: On x86-64, instructions like "mov eax, eax" are used to
     // clear the upper 32 bits of rax.  We need to recognize and
     // preserve these.
     return true;
   }
   if (!Dest->hasReg() && !SrcVar->hasReg() &&
       Dest->getStackOffset() == SrcVar->getStackOffset())
     return true;
   return false;
 }
 
 } // end of namespace Ice