optimized switch implementation

src/wasm/asm-wasm-builder.cc

 // Copyright 2015 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/v8.h"
 
 // Required to get M_E etc. in MSVC.
 #if defined(_WIN32)
 #define _USE_MATH_DEFINES
 #endif
 #include <math.h>
 
 #include "src/wasm/asm-wasm-builder.h"
+#include "src/wasm/switch-logic.h"
 #include "src/wasm/wasm-macro-gen.h"
 #include "src/wasm/wasm-opcodes.h"
 
 #include "src/ast/ast.h"
 #include "src/ast/scopes.h"
 #include "src/codegen.h"
 #include "src/type-cache.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 68 matching lines @@
     local_variables_.Clear();
   }
 
   void VisitImportDeclaration(ImportDeclaration* decl) {}
 
   void VisitExportDeclaration(ExportDeclaration* decl) {}
 
   void VisitStatements(ZoneList<Statement*>* stmts) {
     for (int i = 0; i < stmts->length(); ++i) {
       Statement* stmt = stmts->at(i);
+      ExpressionStatement* e = stmt->AsExpressionStatement();
+      if (e != nullptr && e->expression()->IsUndefinedLiteral()) {
+        block_size_--;
+        continue;
+      }
       RECURSE(Visit(stmt));
       if (stmt->IsJump()) break;
     }
   }
 
   void VisitBlock(Block* stmt) {
     if (stmt->statements()->length() == 1) {
       ExpressionStatement* expr =
           stmt->statements()->at(0)->AsExpressionStatement();
       if (expr != nullptr) {
@@ skipping 116 matching lines @@
       marking_exported = true;
     }
     RECURSE(Visit(stmt->expression()));
     if (!in_function_) {
       marking_exported = false;
     }
   }
 
   void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); }
 
-  void SetLocalTo(uint16_t index, int value) {
-    current_function_builder_->Emit(kExprSetLocal);
-    AddLeb128(index, true);
-    // TODO(bradnelson): variable size
+  void GenerateCaseComparisonCode(int value, WasmOpcode op,
+                                  VariableProxy* tag) {
+    current_function_builder_->Emit(kExprIfElse);
+    current_function_builder_->Emit(op);
+    VisitVariableProxy(tag);
     byte code[] = {WASM_I32V(value)};
     current_function_builder_->EmitCode(code, sizeof(code));
-    block_size_++;
   }
 
-  void CompileCase(CaseClause* clause, uint16_t fall_through,
-                   VariableProxy* tag) {
-    Literal* label = clause->label()->AsLiteral();
-    DCHECK_NOT_NULL(label);
-    block_size_++;
-    current_function_builder_->Emit(kExprIf);
-    current_function_builder_->Emit(kExprI32Ior);
-    current_function_builder_->Emit(kExprI32Eq);
-    VisitVariableProxy(tag);
-    VisitLiteral(label);
-    current_function_builder_->Emit(kExprGetLocal);
-    AddLeb128(fall_through, true);
-    BlockVisitor visitor(this, nullptr, kExprBlock, false, 0);
-    SetLocalTo(fall_through, 1);
-    ZoneList<Statement*>* stmts = clause->statements();
-    block_size_ += stmts->length();
-    RECURSE(VisitStatements(stmts));
+  void HandleCase(CaseNode* node,
+                  const ZoneMap<int, unsigned int>& case_to_block,
+                  VariableProxy* tag, int default_block) {
+    if (node->left != nullptr) {

[titzer, 2016/04/01 09:22:45]

I kind of doubt that a binary search tree is worth it. Either a flat dense table
or a series of if's will probably suffice.

[bradn, 2016/04/04 22:31:12]

FWIW, a survey of module suggests these are fairly sparse.
Are you concerned about negative consequences of the tree?
Something we should measure?

+      GenerateCaseComparisonCode(node->begin, kExprI32LtS, tag);
+      HandleCase(node->left, case_to_block, tag, default_block);
+    }
+    if (node->right != nullptr) {
+      GenerateCaseComparisonCode(node->end, kExprI32GtS, tag);
+      HandleCase(node->right, case_to_block, tag, default_block);
+    }
+    if (node->begin == node->end) {
+      current_function_builder_->Emit(kExprIf);
+      current_function_builder_->Emit(kExprI32Eq);
+      VisitVariableProxy(tag);
+      byte code[] = {WASM_I32V(node->begin)};
+      current_function_builder_->EmitCode(code, sizeof(code));
+      DCHECK(case_to_block.find(node->begin) != case_to_block.end());
+      current_function_builder_->EmitWithVarInt(kExprBr,
+                                                case_to_block.at(node->begin));
+      current_function_builder_->Emit(kExprNop);
+    } else {
+      current_function_builder_->Emit(kExprBrTable);
+      byte count[] = {U32V_1(node->end - node->begin + 1)};
+      current_function_builder_->EmitCode(count, sizeof(count));
+      for (int v = node->begin; v <= node->end; v++) {
+        if (case_to_block.find(v) != case_to_block.end()) {
+          byte break_code[] = {BR_TARGET(case_to_block.at(v))};
+          current_function_builder_->EmitCode(break_code, sizeof(break_code));
+        } else {
+          byte break_code[] = {BR_TARGET(default_block)};
+          current_function_builder_->EmitCode(break_code, sizeof(break_code));
+        }
+      }
+      byte break_code[] = {BR_TARGET(default_block)};
+      current_function_builder_->EmitCode(break_code, sizeof(break_code));
+      current_function_builder_->Emit(kExprI32Sub);
+      VisitVariableProxy(tag);
+      byte code[] = {WASM_I32V(node->begin)};
+      current_function_builder_->EmitCode(code, sizeof(code));
+    }
   }
 
   void VisitSwitchStatement(SwitchStatement* stmt) {
     VariableProxy* tag = stmt->tag()->AsVariableProxy();
     DCHECK_NOT_NULL(tag);
+    ZoneList<CaseClause*>* clauses = stmt->cases();
+    int case_count = clauses->length();
+    if (case_count == 0) {
+      block_size_--;
+      return;
+    }
     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false,
-                         0);
-    uint16_t fall_through = current_function_builder_->AddLocal(kAstI32);
-    SetLocalTo(fall_through, 0);
-
-    ZoneList<CaseClause*>* clauses = stmt->cases();
-    for (int i = 0; i < clauses->length(); ++i) {
+                         1);
+    ZoneVector<BlockVisitor*> blocks(zone_);
+    ZoneVector<int32_t> cases(zone_);
+    ZoneMap<int, unsigned int> case_to_block(zone_);
+    int default_block = -1;
+    bool has_default = false;
+    for (int i = case_count - 1; i >= 0; i--) {
       CaseClause* clause = clauses->at(i);
+      blocks.push_back(new BlockVisitor(this, nullptr, kExprBlock, false,
+                                        clause->statements()->length() + 1));
       if (!clause->is_default()) {
-        CompileCase(clause, fall_through, tag);
+        Literal* label = clause->label()->AsLiteral();
+        Handle<Object> value = label->value();
+        DCHECK(value->IsNumber() &&
+               label->bounds().upper->Is(cache_.kAsmSigned));
+        int32_t label_value;
+        if (!value->ToInt32(&label_value)) {
+          UNREACHABLE();
+        }
+        case_to_block[label_value] = i;
+        cases.push_back(label_value);
       } else {
-        ZoneList<Statement*>* stmts = clause->statements();
-        block_size_ += stmts->length();
-        RECURSE(VisitStatements(stmts));
+        default_block = i;
+        has_default = true;
       }
     }
+    if (!has_default) {
+      default_block = case_count;
+    }
+    if (!has_default || case_count > 1) {
+      BlockVisitor switch_logic_block(this, nullptr, kExprBlock, false, 1);
+      CaseNode* root = OrderCases(&cases, zone_);
+      HandleCase(root, case_to_block, tag, default_block);
+      if (root->left != nullptr || root->right != nullptr ||
+          root->begin == root->end) {
+        block_size_++;
+        current_function_builder_->EmitWithVarInt(kExprBr, default_block);
+        current_function_builder_->Emit(kExprNop);
+      }
+    } else {
+      block_size_ = clauses->at(0)->statements()->length();
+    }
+    for (int i = 0; i < case_count; i++) {

[titzer, 2016/04/01 09:22:45]

I'm not sure if the block depths are right here; we need a lot more tests for
this.

[aseemgarg, 2016/04/07 23:32:36]

Re-read. Seems to be fine and working.

+      CaseClause* clause = clauses->at(i);
+      RECURSE(VisitStatements(clause->statements()));
+      BlockVisitor* v = blocks.at(case_count - i - 1);
+      blocks.pop_back();
+      delete v;
+    }
   }
 
   void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
 
   void VisitDoWhileStatement(DoWhileStatement* stmt) {
     DCHECK(in_function_);
     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
                          2);
     RECURSE(Visit(stmt->body()));
     current_function_builder_->Emit(kExprIf);
@@ skipping 1238 matching lines @@
 // that zone in constructor may be thrown away once wasm module is written.
 WasmModuleIndex* AsmWasmBuilder::Run() {
   AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_);
   impl.Compile();
   WasmModuleWriter* writer = impl.builder_->Build(zone_);
   return writer->WriteTo(zone_);
 }
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8