Introduction of improved switch lowering.

src/IceSwitchLowering.cpp

Index: src/IceSwitchLowering.cpp
diff --git a/src/IceSwitchLowering.cpp b/src/IceSwitchLowering.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..60c27d18826b83dc312addb91f12160b8dc72e4f
--- /dev/null
+++ b/src/IceSwitchLowering.cpp
@@ -0,0 +1,88 @@
+//===----- subzero/src/IceSwitchLowering.h - Switch lowering -----*- C++ -*-==//

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

.cpp

and no need for the -*- C++ -*- in the .cpp

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

.cpp , and also don't need the -*- C++ -*- stuff.

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

Done.

+//
+//                        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.
+
+  // Small number of cases is trivial

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

By "trivial" you mean that loading from the jump table, doing indirect jumps,
and for NaCl sandboxing, aligning the CfgNode targets of the jump table, seems
to be not "profitable" compared to direct jumps (which don't require the target
to be aligned)?

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

Done.

+  if (CaseClusters.size() < Func->getTarget()->getMinJumpTableSize())
+    return CaseClusters;
+
+  // Test for a single jump table

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

I think it would be good to document why a single one instead of a tree of them.

For a tree of jump tables, we'd have to traverse to the leaves before anything
happens. So, we're sort of looking for an *unbalanced* tree, where there is a
bias toward frequently executed code.  The problem is that we don't have profile
information to do this *well*. 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.

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

Done.

+  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& x) {

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

"x" -> "X"

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

More descriptive argument name than "x"?

Capitalize variable names per LLVM convention.

Run "make format".

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

Done.

+  // Can only append ranges with the same target and are adjacent
+  bool can = this->Label == x.Label && this->High+1 == x.Low;

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

Start variable name with capital letter ("Can")

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

Done.

+  if (can) this->High = x.High;
+  return can;
+}
+
+} // end of namespace Ice