Introduction of improved switch lowering.

src/IceSwitchLowering.h

Index: src/IceSwitchLowering.h
diff --git a/src/IceSwitchLowering.h b/src/IceSwitchLowering.h
new file mode 100644
index 0000000000000000000000000000000000000000..f0b6adb1d199cd5c429f870071ac7153acf8607a
--- /dev/null
+++ b/src/IceSwitchLowering.h
@@ -0,0 +1,77 @@
+//===---- subzero/src/IceSwitchLowering.h - Switch lowering ----*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief The file contains helpers for switch lowering.
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICESWITCHLOWERING_H
+#define SUBZERO_SRC_ICESWITCHLOWERING_H
+
+#include "IceCfgNode.h"
+#include "IceInst.h"
+
+namespace Ice {
+
+class CaseCluster;
+
+typedef std::vector<CaseCluster, CfgLocalAllocator<CaseCluster>>
+  CaseClusterArray;
+
+/// A cluster of cases can be tested by a common method during switch lowering.
+class CaseCluster {
+  CaseCluster() = delete;
+
+public:
+  enum CaseClusterKind {
+    Range,     /// Numerically adjacent case values with same target.
+    JumpTable, /// Different targets and possibly sparse.
+  };
+
+  /// Create a cluster of a single case represented by a unitary range.

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

At first I was surprised this was unitary, while the jumptable version is not
unitary. Perhaps the case is that tryAppend will increase the range as you go?
Could you clarify?

+  CaseCluster(uint64_t Value, CfgNode *Label)
+    : Kind(Range), Low(Value), High(Value), Label(Label) {}
+  /// Create a case consisting of a jump table.
+  CaseCluster(uint64_t Low, uint64_t High, InstJumpTable *JT)
+    : Kind(JumpTable), Low(Low), High(High), JT(JT) {}
+
+private:

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

nit: I tend to prefer just having all the public: section continuous and the
private: continuous.

It should be okay to define the getters in terms of the fields before the fields
are actually defined?

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

Done.

+  CaseClusterKind Kind;
+  uint64_t Low;
+  uint64_t High;
+  union {
+    CfgNode       *Label; /// Target for a range.
+    InstJumpTable *JT;    /// Jump table targets.
+  };
+
+public:
+  CaseClusterKind getKind() const { return Kind; }
+  uint64_t getLow() const { return Low; }
+  uint64_t getHigh() const { return High; }
+  CfgNode *getLabel() const {
+    assert(Kind == Range);
+    return Label;
+  }
+  InstJumpTable *getJumpTable() const {
+    assert(Kind == JumpTable);
+    return JT;
+  }
+
+  /// Discover cases which can be clustered together and return the clusters
+  /// ordered by case value.
+  static CaseClusterArray clusterizeSwitch(Cfg *Func, const InstSwitch *Inst);
+
+private:
+  /// Try and append a cluster returning whether or not it was successful.
+  bool tryAppend(const CaseCluster& x);

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

I think LLVM style puts the & next to the x? Did clang-format get this?

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

Done.

+};
+
+} // end of namespace Ice
+
+#endif //  SUBZERO_SRC_ICESWITCHLOWERING_H