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