Introduction of improved switch lowering.

src/IceInst.cpp

Index: src/IceInst.cpp
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index ecfb1b660f4e5327088373336e9a1582459fa208..eccfb45cad22a1a65d6929e8a4eb34ddd029fca9 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -19,6 +19,7 @@
 #include "IceCfgNode.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
+#include "IceTargetLowering.h"
 
 namespace Ice {
 
@@ -295,15 +296,17 @@ NodeList InstBr::getTerminatorEdges() const {
   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)
@@ -461,21 +464,25 @@ NodeList InstSwitch::getTerminatorEdges() const {
   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)
@@ -504,6 +511,30 @@ InstFakeUse::InstFakeUse(Cfg *Func, Variable *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;
@@ -917,6 +948,39 @@ void InstFakeKill::dump(const Cfg *Func) const {
   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;