optimized switch implementation

src/wasm/switch-logic.cc

Index: src/wasm/switch-logic.cc
diff --git a/src/wasm/switch-logic.cc b/src/wasm/switch-logic.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8342005a712797d73e375a7153e374bb1c43a013
--- /dev/null
+++ b/src/wasm/switch-logic.cc
@@ -0,0 +1,58 @@
+// Copyright 2016 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/wasm/switch-logic.h"
+
+namespace v8 {
+namespace internal {
+namespace wasm {
+
+CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) {

[bradn, 2016/03/31 21:39:09]

Put this in an anonymous namespace.

[aseemgarg, 2016/03/31 22:04:54]

Done.

+  if (end < begin) {
+    return nullptr;
+  } else if (end == begin) {
+    return nodes->at(begin);
+  } else {
+    size_t root_index = (begin + end) / 2;
+    CaseNode* root = nodes->at(root_index);
+    if (root_index != 0) {
+      root->left_ = CreateBst(nodes, begin, root_index - 1);
+    }
+    root->right_ = CreateBst(nodes, root_index + 1, end);
+    return root;
+  }
+}
+
+CaseNode* OrderCases(ZoneVector<int>* cases, Zone* zone) {
+  const int max_distance = 2;
+  const int min_size = 4;
+  std::sort(cases->begin(), cases->end());
+  ZoneVector<size_t> table_breaks(zone);
+  for (size_t i = 1; i < cases->size(); i++) {
+    if (cases->at(i) - cases->at(i - 1) > max_distance) {
+      table_breaks.push_back(i);
+    }
+  }
+  table_breaks.push_back(cases->size());
+  ZoneVector<CaseNode*> nodes(zone);
+  size_t curr_pos = 0;
+  for (size_t i = 0; i < table_breaks.size(); i++) {
+    size_t break_pos = table_breaks[i];
+    if (break_pos - curr_pos >= min_size) {
+      int begin = cases->at(curr_pos);
+      int end = cases->at(break_pos - 1);
+      nodes.push_back(new (zone) CaseNode(begin, end));
+      curr_pos = break_pos;
+    } else {
+      for (; curr_pos < break_pos; curr_pos++) {
+        nodes.push_back(new (zone)
+                            CaseNode(cases->at(curr_pos), cases->at(curr_pos)));
+      }
+    }
+  }
+  return CreateBst(&nodes, 0, nodes.size() - 1);
+}
+}  // namespace wasm
+}  // namespace internal
+}  // namespace v8