Introduction of improved switch lowering.

src/IceSwitchLowering.cpp

+//===- subzero/src/IceSwitchLowering.cpp - Switch lowering -----------------==//
+//
+//                        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 platform independent analysis of switch cases to
+/// improve the generated code.
+///
+//===----------------------------------------------------------------------===//
+#include "IceSwitchLowering.h"
+
+#include "IceTargetLowering.h"
+
+#include <algorithm>
+
+namespace Ice {
+
+CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func,
+                                               const InstSwitch *Inst) {
+  CaseClusterArray CaseClusters;
+
+  // Load the cases
+  SizeT NumCases = Inst->getNumCases();
+  CaseClusters.reserve(NumCases);
+  for (SizeT I = 0; I < NumCases; ++I)
+    CaseClusters.emplace_back(Inst->getValue(I), Inst->getLabel(I));
+
+  // Sort the cases
+  std::sort(CaseClusters.begin(), CaseClusters.end(),
+            [](const CaseCluster &x, const CaseCluster &y) {
+              return x.High < y.Low;
+            });
+
+  // Merge adjacent case ranges
+  auto Active = CaseClusters.begin();
+  std::for_each(Active + 1, CaseClusters.end(),
+                [&Active](const CaseCluster &x) {
+                  if (!Active->tryAppend(x))
+                    *(++Active) = x;
+                });
+  CaseClusters.erase(Active + 1, CaseClusters.end());
+
+  // TODO(ascull): Merge in a cycle i.e. -1(=UINTXX_MAX) to 0. This depends on
+  // the types for correct wrap around behavior.
+
+  // A small number of cases is more efficient without a jump table
+  if (CaseClusters.size() < Func->getTarget()->getMinJumpTableSize())
+    return CaseClusters;
+
+  // Test for a single jump table. This can be done in constant time whereas
+  // finding the best set of jump table would be quadratic, too slow(?). If
+  // jump tables were included in the search tree we'd first have to traverse to
+  // them. Ideally we would have an unbalanced tree which is biased towards
+  // frequently executed code but we can't do this well without profiling data.
+  // So, this single jump table is a good starting point where you can get to
+  // the jump table quickly without figuring out how to unbalance the tree.
+  uint64_t MaxValue = CaseClusters.back().High;
+  uint64_t MinValue = CaseClusters.front().Low;
+  // Don't +1 yet to avoid (INT64_MAX-0)+1 overflow
+  uint64_t TotalRange = MaxValue - MinValue;
+
+  // Might be too sparse for the jump table
+  if (NumCases * 2 <= TotalRange)
+    return CaseClusters;
+  // Unlikely. Would mean can't store size of jump table.
+  if (TotalRange == UINT64_MAX)
+    return CaseClusters;
+  ++TotalRange;
+
+  // Replace everything with a jump table
+  InstJumpTable *JumpTable =
+      InstJumpTable::create(Func, TotalRange, Inst->getLabelDefault());
+  for (const CaseCluster &Case : CaseClusters)
+    for (uint64_t I = Case.Low; I <= Case.High; ++I)
+      JumpTable->addTarget(I - MinValue, Case.Label);
+
+  CaseClusters.clear();
+  CaseClusters.emplace_back(MinValue, MaxValue, JumpTable);
+
+  return CaseClusters;
+}
+
+bool CaseCluster::tryAppend(const CaseCluster &New) {
+  // Can only append ranges with the same target and are adjacent
+  bool CanAppend = this->Label == New.Label && this->High + 1 == New.Low;
+  if (CanAppend)
+    this->High = New.High;
+  return CanAppend;
+}
+
+} // end of namespace Ice