Line data Source code
1 : // Copyright 2016 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/asmjs/switch-logic.h"
6 :
7 : namespace v8 {
8 : namespace internal {
9 : namespace wasm {
10 :
11 : namespace {
12 10815 : CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) {
13 10815 : if (end < begin) {
14 : return nullptr;
15 9079 : } else if (end == begin) {
16 3820 : return nodes->at(begin);
17 : } else {
18 5259 : size_t root_index = (begin + end) / 2;
19 5259 : CaseNode* root = nodes->at(root_index);
20 5259 : if (root_index != 0) {
21 5074 : root->left = CreateBst(nodes, begin, root_index - 1);
22 : }
23 5259 : root->right = CreateBst(nodes, root_index + 1, end);
24 5259 : return root;
25 : }
26 : }
27 : } // namespace
28 :
29 483 : CaseNode* OrderCases(ZoneVector<int>* cases, Zone* zone) {
30 : const int max_distance = 2;
31 : const int min_size = 4;
32 28485 : if (cases->empty()) {
33 : return nullptr;
34 : }
35 482 : std::sort(cases->begin(), cases->end());
36 : ZoneVector<size_t> table_breaks(zone);
37 56004 : for (size_t i = 1; i < cases->size(); ++i) {
38 55040 : if (cases->at(i) - cases->at(i - 1) > max_distance) {
39 8254 : table_breaks.push_back(i);
40 : }
41 : }
42 964 : table_breaks.push_back(cases->size());
43 : ZoneVector<CaseNode*> nodes(zone);
44 : size_t curr_pos = 0;
45 18436 : for (size_t i = 0; i < table_breaks.size(); ++i) {
46 8736 : size_t break_pos = table_breaks[i];
47 8736 : if (break_pos - curr_pos >= min_size) {
48 317 : int begin = cases->at(curr_pos);
49 634 : int end = cases->at(break_pos - 1);
50 634 : nodes.push_back(new (zone) CaseNode(begin, end));
51 : curr_pos = break_pos;
52 : } else {
53 8762 : for (; curr_pos < break_pos; curr_pos++) {
54 : nodes.push_back(new (zone)
55 26286 : CaseNode(cases->at(curr_pos), cases->at(curr_pos)));
56 : }
57 : }
58 : }
59 964 : return CreateBst(&nodes, 0, nodes.size() - 1);
60 : }
61 : } // namespace wasm
62 : } // namespace internal
63 : } // namespace v8
|