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