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(),
+            [](const CfgNode *x, const CfgNode *y) {
+              return x->getIndex() < y->getIndex();
+            });
+  auto Last = std::unique(OutEdges.begin(), OutEdges.end());
+  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),
+      LabelNumber(Func->getTarget()->makeNextLabelNumber()),
+      NumTargets(NumTargets) {
+  Targets = Func->allocateArrayOf<CfgNode *>(NumTargets);
+  for (SizeT I = 0; I < NumTargets; ++I)
+    Targets[I] = Default;
+}
+
+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(LabelNumber);
+}
+
 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 {
+  // 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 {
+  // TODO(ascull): put jump table in the global context for emission later
+  (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