asm-wasm-builder.cc revision 537ba893e2530051ec7f296e769fdd37bb4ae4a0 
1// Copyright 2015 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/v8.h"
6
7// Required to get M_E etc. in MSVC.
8#if defined(_WIN32)
9#define _USE_MATH_DEFINES
10#endif
11#include <math.h>
12
13#include "src/wasm/asm-wasm-builder.h"
14#include "src/wasm/switch-logic.h"
15#include "src/wasm/wasm-macro-gen.h"
16#include "src/wasm/wasm-opcodes.h"
17
18#include "src/ast/ast.h"
19#include "src/ast/scopes.h"
20#include "src/codegen.h"
21#include "src/type-cache.h"
22
23namespace v8 {
24namespace internal {
25namespace wasm {
26
27#define RECURSE(call)               \
28  do {                              \
29    DCHECK(!HasStackOverflow());    \
30    call;                           \
31    if (HasStackOverflow()) return; \
32  } while (false)
33
34enum AsmScope { kModuleScope, kInitScope, kFuncScope, kExportScope };
35
36class AsmWasmBuilderImpl : public AstVisitor {
37 public:
38  AsmWasmBuilderImpl(Isolate* isolate, Zone* zone, FunctionLiteral* literal,
39                     Handle<Object> foreign, AsmTyper* typer)
40      : local_variables_(HashMap::PointersMatch,
41                         ZoneHashMap::kDefaultHashMapCapacity,
42                         ZoneAllocationPolicy(zone)),
43        functions_(HashMap::PointersMatch, ZoneHashMap::kDefaultHashMapCapacity,
44                   ZoneAllocationPolicy(zone)),
45        global_variables_(HashMap::PointersMatch,
46                          ZoneHashMap::kDefaultHashMapCapacity,
47                          ZoneAllocationPolicy(zone)),
48        scope_(kModuleScope),
49        builder_(new (zone) WasmModuleBuilder(zone)),
50        current_function_builder_(nullptr),
51        literal_(literal),
52        isolate_(isolate),
53        zone_(zone),
54        foreign_(foreign),
55        typer_(typer),
56        cache_(TypeCache::Get()),
57        breakable_blocks_(zone),
58        init_function_index_(0),
59        next_table_index_(0),
60        function_tables_(HashMap::PointersMatch,
61                         ZoneHashMap::kDefaultHashMapCapacity,
62                         ZoneAllocationPolicy(zone)),
63        imported_function_table_(this),
64        bounds_(typer->bounds()) {
65    InitializeAstVisitor(isolate);
66  }
67
68  void InitializeInitFunction() {
69    init_function_index_ = builder_->AddFunction();
70    FunctionSig::Builder b(zone(), 0, 0);
71    current_function_builder_ = builder_->FunctionAt(init_function_index_);
72    current_function_builder_->SetSignature(b.Build());
73    builder_->MarkStartFunction(init_function_index_);
74    current_function_builder_ = nullptr;
75  }
76
77  void Compile() {
78    InitializeInitFunction();
79    RECURSE(VisitFunctionLiteral(literal_));
80  }
81
82  void VisitVariableDeclaration(VariableDeclaration* decl) {}
83
84  void VisitFunctionDeclaration(FunctionDeclaration* decl) {
85    DCHECK_EQ(kModuleScope, scope_);
86    DCHECK_NULL(current_function_builder_);
87    uint32_t index = LookupOrInsertFunction(decl->proxy()->var());
88    current_function_builder_ = builder_->FunctionAt(index);
89    scope_ = kFuncScope;
90    RECURSE(Visit(decl->fun()));
91    scope_ = kModuleScope;
92    current_function_builder_ = nullptr;
93    local_variables_.Clear();
94  }
95
96  void VisitImportDeclaration(ImportDeclaration* decl) {}
97
98  void VisitExportDeclaration(ExportDeclaration* decl) {}
99
100  void VisitStatements(ZoneList<Statement*>* stmts) {
101    for (int i = 0; i < stmts->length(); ++i) {
102      Statement* stmt = stmts->at(i);
103      ExpressionStatement* e = stmt->AsExpressionStatement();
104      if (e != nullptr && e->expression()->IsUndefinedLiteral()) {
105        continue;
106      }
107      RECURSE(Visit(stmt));
108      if (stmt->IsJump()) break;
109    }
110  }
111
112  void VisitBlock(Block* stmt) {
113    if (stmt->statements()->length() == 1) {
114      ExpressionStatement* expr =
115          stmt->statements()->at(0)->AsExpressionStatement();
116      if (expr != nullptr) {
117        if (expr->expression()->IsAssignment()) {
118          RECURSE(VisitExpressionStatement(expr));
119          return;
120        }
121      }
122    }
123    if (scope_ == kFuncScope) {
124      BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock,
125                           false);
126      RECURSE(VisitStatements(stmt->statements()));
127    } else {
128      RECURSE(VisitStatements(stmt->statements()));
129    }
130  }
131
132  class BlockVisitor {
133   private:
134    AsmWasmBuilderImpl* builder_;
135
136   public:
137    BlockVisitor(AsmWasmBuilderImpl* builder, BreakableStatement* stmt,
138                 WasmOpcode opcode, bool is_loop)
139        : builder_(builder) {
140      builder_->breakable_blocks_.push_back(std::make_pair(stmt, is_loop));
141      builder_->current_function_builder_->Emit(opcode);
142    }
143    ~BlockVisitor() {
144      builder_->current_function_builder_->Emit(kExprEnd);
145      builder_->breakable_blocks_.pop_back();
146    }
147  };
148
149  void VisitExpressionStatement(ExpressionStatement* stmt) {
150    RECURSE(Visit(stmt->expression()));
151  }
152
153  void VisitEmptyStatement(EmptyStatement* stmt) {}
154
155  void VisitEmptyParentheses(EmptyParentheses* paren) { UNREACHABLE(); }
156
157  void VisitIfStatement(IfStatement* stmt) {
158    DCHECK_EQ(kFuncScope, scope_);
159    RECURSE(Visit(stmt->condition()));
160    current_function_builder_->Emit(kExprIf);
161    // WASM ifs come with implement blocks for both arms.
162    breakable_blocks_.push_back(std::make_pair(nullptr, false));
163    if (stmt->HasThenStatement()) {
164      RECURSE(Visit(stmt->then_statement()));
165    }
166    if (stmt->HasElseStatement()) {
167      current_function_builder_->Emit(kExprElse);
168      RECURSE(Visit(stmt->else_statement()));
169    }
170    current_function_builder_->Emit(kExprEnd);
171    breakable_blocks_.pop_back();
172  }
173
174  void VisitContinueStatement(ContinueStatement* stmt) {
175    DCHECK_EQ(kFuncScope, scope_);
176    DCHECK_NOT_NULL(stmt->target());
177    int i = static_cast<int>(breakable_blocks_.size()) - 1;
178    int block_distance = 0;
179    for (; i >= 0; i--) {
180      auto elem = breakable_blocks_.at(i);
181      if (elem.first == stmt->target()) {
182        DCHECK(elem.second);
183        break;
184      } else if (elem.second) {
185        block_distance += 2;
186      } else {
187        block_distance += 1;
188      }
189    }
190    DCHECK(i >= 0);
191    current_function_builder_->EmitWithU8(kExprBr, ARITY_0);
192    current_function_builder_->EmitVarInt(block_distance);
193  }
194
195  void VisitBreakStatement(BreakStatement* stmt) {
196    DCHECK_EQ(kFuncScope, scope_);
197    DCHECK_NOT_NULL(stmt->target());
198    int i = static_cast<int>(breakable_blocks_.size()) - 1;
199    int block_distance = 0;
200    for (; i >= 0; i--) {
201      auto elem = breakable_blocks_.at(i);
202      if (elem.first == stmt->target()) {
203        if (elem.second) {
204          block_distance++;
205        }
206        break;
207      } else if (elem.second) {
208        block_distance += 2;
209      } else {
210        block_distance += 1;
211      }
212    }
213    DCHECK(i >= 0);
214    current_function_builder_->EmitWithU8(kExprBr, ARITY_0);
215    current_function_builder_->EmitVarInt(block_distance);
216  }
217
218  void VisitReturnStatement(ReturnStatement* stmt) {
219    if (scope_ == kModuleScope) {
220      scope_ = kExportScope;
221      RECURSE(Visit(stmt->expression()));
222      scope_ = kModuleScope;
223    } else if (scope_ == kFuncScope) {
224      RECURSE(Visit(stmt->expression()));
225      uint8_t arity =
226          TypeOf(stmt->expression()) == kAstStmt ? ARITY_0 : ARITY_1;
227      current_function_builder_->EmitWithU8(kExprReturn, arity);
228    } else {
229      UNREACHABLE();
230    }
231  }
232
233  void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); }
234
235  void HandleCase(CaseNode* node,
236                  const ZoneMap<int, unsigned int>& case_to_block,
237                  VariableProxy* tag, int default_block, int if_depth) {
238    int prev_if_depth = if_depth;
239    if (node->left != nullptr) {
240      VisitVariableProxy(tag);
241      current_function_builder_->EmitI32Const(node->begin);
242      current_function_builder_->Emit(kExprI32LtS);
243      current_function_builder_->Emit(kExprIf);
244      if_depth++;
245      breakable_blocks_.push_back(std::make_pair(nullptr, false));
246      HandleCase(node->left, case_to_block, tag, default_block, if_depth);
247      current_function_builder_->Emit(kExprElse);
248    }
249    if (node->right != nullptr) {
250      VisitVariableProxy(tag);
251      current_function_builder_->EmitI32Const(node->end);
252      current_function_builder_->Emit(kExprI32GtS);
253      current_function_builder_->Emit(kExprIf);
254      if_depth++;
255      breakable_blocks_.push_back(std::make_pair(nullptr, false));
256      HandleCase(node->right, case_to_block, tag, default_block, if_depth);
257      current_function_builder_->Emit(kExprElse);
258    }
259    if (node->begin == node->end) {
260      VisitVariableProxy(tag);
261      current_function_builder_->EmitI32Const(node->begin);
262      current_function_builder_->Emit(kExprI32Eq);
263      current_function_builder_->Emit(kExprIf);
264      DCHECK(case_to_block.find(node->begin) != case_to_block.end());
265      current_function_builder_->EmitWithU8(kExprBr, ARITY_0);
266      current_function_builder_->EmitVarInt(1 + if_depth +
267                                            case_to_block.at(node->begin));
268      current_function_builder_->Emit(kExprEnd);
269    } else {
270      if (node->begin != 0) {
271        VisitVariableProxy(tag);
272        current_function_builder_->EmitI32Const(node->begin);
273        current_function_builder_->Emit(kExprI32Sub);
274      } else {
275        VisitVariableProxy(tag);
276      }
277      current_function_builder_->EmitWithU8(kExprBrTable, ARITY_0);
278      current_function_builder_->EmitVarInt(node->end - node->begin + 1);
279      for (int v = node->begin; v <= node->end; v++) {
280        if (case_to_block.find(v) != case_to_block.end()) {
281          byte break_code[] = {BR_TARGET(if_depth + case_to_block.at(v))};
282          current_function_builder_->EmitCode(break_code, sizeof(break_code));
283        } else {
284          byte break_code[] = {BR_TARGET(if_depth + default_block)};
285          current_function_builder_->EmitCode(break_code, sizeof(break_code));
286        }
287        if (v == kMaxInt) {
288          break;
289        }
290      }
291      byte break_code[] = {BR_TARGET(if_depth + default_block)};
292      current_function_builder_->EmitCode(break_code, sizeof(break_code));
293    }
294
295    while (if_depth-- != prev_if_depth) {
296      breakable_blocks_.pop_back();
297      current_function_builder_->Emit(kExprEnd);
298    }
299  }
300
301  void VisitSwitchStatement(SwitchStatement* stmt) {
302    VariableProxy* tag = stmt->tag()->AsVariableProxy();
303    DCHECK_NOT_NULL(tag);
304    ZoneList<CaseClause*>* clauses = stmt->cases();
305    int case_count = clauses->length();
306    if (case_count == 0) {
307      return;
308    }
309    BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false);
310    ZoneVector<BlockVisitor*> blocks(zone_);
311    ZoneVector<int32_t> cases(zone_);
312    ZoneMap<int, unsigned int> case_to_block(zone_);
313    bool has_default = false;
314    for (int i = case_count - 1; i >= 0; i--) {
315      CaseClause* clause = clauses->at(i);
316      blocks.push_back(new BlockVisitor(this, nullptr, kExprBlock, false));
317      if (!clause->is_default()) {
318        Literal* label = clause->label()->AsLiteral();
319        Handle<Object> value = label->value();
320        DCHECK(value->IsNumber() &&
321               bounds_->get(label).upper->Is(cache_.kAsmSigned));
322        int32_t label_value;
323        if (!value->ToInt32(&label_value)) {
324          UNREACHABLE();
325        }
326        case_to_block[label_value] = i;
327        cases.push_back(label_value);
328      } else {
329        DCHECK_EQ(i, case_count - 1);
330        has_default = true;
331      }
332    }
333    if (!has_default || case_count > 1) {
334      int default_block = has_default ? case_count - 1 : case_count;
335      BlockVisitor switch_logic_block(this, nullptr, kExprBlock, false);
336      CaseNode* root = OrderCases(&cases, zone_);
337      HandleCase(root, case_to_block, tag, default_block, 0);
338      if (root->left != nullptr || root->right != nullptr ||
339          root->begin == root->end) {
340        current_function_builder_->EmitWithU8(kExprBr, ARITY_0);
341        current_function_builder_->EmitVarInt(default_block);
342      }
343    }
344    for (int i = 0; i < case_count; i++) {
345      CaseClause* clause = clauses->at(i);
346      RECURSE(VisitStatements(clause->statements()));
347      BlockVisitor* v = blocks.at(case_count - i - 1);
348      blocks.pop_back();
349      delete v;
350    }
351  }
352
353  void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
354
355  void VisitDoWhileStatement(DoWhileStatement* stmt) {
356    DCHECK_EQ(kFuncScope, scope_);
357    BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true);
358    RECURSE(Visit(stmt->body()));
359    RECURSE(Visit(stmt->cond()));
360    current_function_builder_->Emit(kExprIf);
361    current_function_builder_->EmitWithU8U8(kExprBr, ARITY_0, 1);
362    current_function_builder_->Emit(kExprEnd);
363  }
364
365  void VisitWhileStatement(WhileStatement* stmt) {
366    DCHECK_EQ(kFuncScope, scope_);
367    BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true);
368    RECURSE(Visit(stmt->cond()));
369    breakable_blocks_.push_back(std::make_pair(nullptr, false));
370    current_function_builder_->Emit(kExprIf);
371    RECURSE(Visit(stmt->body()));
372    current_function_builder_->EmitWithU8U8(kExprBr, ARITY_0, 1);
373    current_function_builder_->Emit(kExprEnd);
374    breakable_blocks_.pop_back();
375  }
376
377  void VisitForStatement(ForStatement* stmt) {
378    DCHECK_EQ(kFuncScope, scope_);
379    if (stmt->init() != nullptr) {
380      RECURSE(Visit(stmt->init()));
381    }
382    BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true);
383    if (stmt->cond() != nullptr) {
384      RECURSE(Visit(stmt->cond()));
385      current_function_builder_->Emit(kExprI32Eqz);
386      current_function_builder_->Emit(kExprIf);
387      current_function_builder_->Emit(kExprNop);
388      current_function_builder_->EmitWithU8U8(kExprBr, ARITY_0, 2);
389      current_function_builder_->Emit(kExprEnd);
390    }
391    if (stmt->body() != nullptr) {
392      RECURSE(Visit(stmt->body()));
393    }
394    if (stmt->next() != nullptr) {
395      RECURSE(Visit(stmt->next()));
396    }
397    current_function_builder_->Emit(kExprNop);
398    current_function_builder_->EmitWithU8U8(kExprBr, ARITY_0, 0);
399  }
400
401  void VisitForInStatement(ForInStatement* stmt) { UNREACHABLE(); }
402
403  void VisitForOfStatement(ForOfStatement* stmt) { UNREACHABLE(); }
404
405  void VisitTryCatchStatement(TryCatchStatement* stmt) { UNREACHABLE(); }
406
407  void VisitTryFinallyStatement(TryFinallyStatement* stmt) { UNREACHABLE(); }
408
409  void VisitDebuggerStatement(DebuggerStatement* stmt) { UNREACHABLE(); }
410
411  void VisitFunctionLiteral(FunctionLiteral* expr) {
412    Scope* scope = expr->scope();
413    if (scope_ == kFuncScope) {
414      if (bounds_->get(expr).lower->IsFunction()) {
415        // Build the signature for the function.
416        FunctionType* func_type = bounds_->get(expr).lower->AsFunction();
417        LocalType return_type = TypeFrom(func_type->Result());
418        FunctionSig::Builder b(zone(), return_type == kAstStmt ? 0 : 1,
419                               func_type->Arity());
420        if (return_type != kAstStmt) b.AddReturn(return_type);
421        for (int i = 0; i < expr->parameter_count(); i++) {
422          LocalType type = TypeFrom(func_type->Parameter(i));
423          DCHECK_NE(kAstStmt, type);
424          b.AddParam(type);
425          InsertParameter(scope->parameter(i), type, i);
426        }
427        current_function_builder_->SetSignature(b.Build());
428      } else {
429        UNREACHABLE();
430      }
431    }
432    RECURSE(VisitStatements(expr->body()));
433    RECURSE(VisitDeclarations(scope->declarations()));
434  }
435
436  void VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
437    UNREACHABLE();
438  }
439
440  void VisitConditional(Conditional* expr) {
441    DCHECK_EQ(kFuncScope, scope_);
442    RECURSE(Visit(expr->condition()));
443    // WASM ifs come with implicit blocks for both arms.
444    breakable_blocks_.push_back(std::make_pair(nullptr, false));
445    current_function_builder_->Emit(kExprIf);
446    RECURSE(Visit(expr->then_expression()));
447    current_function_builder_->Emit(kExprElse);
448    RECURSE(Visit(expr->else_expression()));
449    current_function_builder_->Emit(kExprEnd);
450    breakable_blocks_.pop_back();
451  }
452
453  bool VisitStdlibConstant(Variable* var) {
454    AsmTyper::StandardMember standard_object =
455        typer_->VariableAsStandardMember(var);
456    double value;
457    switch (standard_object) {
458      case AsmTyper::kInfinity: {
459        value = std::numeric_limits<double>::infinity();
460        break;
461      }
462      case AsmTyper::kNaN: {
463        value = std::numeric_limits<double>::quiet_NaN();
464        break;
465      }
466      case AsmTyper::kMathE: {
467        value = M_E;
468        break;
469      }
470      case AsmTyper::kMathLN10: {
471        value = M_LN10;
472        break;
473      }
474      case AsmTyper::kMathLN2: {
475        value = M_LN2;
476        break;
477      }
478      case AsmTyper::kMathLOG10E: {
479        value = M_LOG10E;
480        break;
481      }
482      case AsmTyper::kMathLOG2E: {
483        value = M_LOG2E;
484        break;
485      }
486      case AsmTyper::kMathPI: {
487        value = M_PI;
488        break;
489      }
490      case AsmTyper::kMathSQRT1_2: {
491        value = M_SQRT1_2;
492        break;
493      }
494      case AsmTyper::kMathSQRT2: {
495        value = M_SQRT2;
496        break;
497      }
498      default: { return false; }
499    }
500    byte code[] = {WASM_F64(value)};
501    current_function_builder_->EmitCode(code, sizeof(code));
502    return true;
503  }
504
505  void VisitVariableProxy(VariableProxy* expr) {
506    if (scope_ == kFuncScope || scope_ == kInitScope) {
507      Variable* var = expr->var();
508      if (VisitStdlibConstant(var)) {
509        return;
510      }
511      LocalType var_type = TypeOf(expr);
512      DCHECK_NE(kAstStmt, var_type);
513      if (var->IsContextSlot()) {
514        current_function_builder_->EmitWithVarInt(
515            kExprLoadGlobal, LookupOrInsertGlobal(var, var_type));
516      } else {
517        current_function_builder_->EmitGetLocal(
518            LookupOrInsertLocal(var, var_type));
519      }
520    }
521  }
522
523  void VisitLiteral(Literal* expr) {
524    Handle<Object> value = expr->value();
525    if (!value->IsNumber() || (scope_ != kFuncScope && scope_ != kInitScope)) {
526      return;
527    }
528    Type* type = bounds_->get(expr).upper;
529    if (type->Is(cache_.kAsmSigned)) {
530      int32_t i = 0;
531      if (!value->ToInt32(&i)) {
532        UNREACHABLE();
533      }
534      byte code[] = {WASM_I32V(i)};
535      current_function_builder_->EmitCode(code, sizeof(code));
536    } else if (type->Is(cache_.kAsmUnsigned) || type->Is(cache_.kAsmFixnum)) {
537      uint32_t u = 0;
538      if (!value->ToUint32(&u)) {
539        UNREACHABLE();
540      }
541      int32_t i = static_cast<int32_t>(u);
542      byte code[] = {WASM_I32V(i)};
543      current_function_builder_->EmitCode(code, sizeof(code));
544    } else if (type->Is(cache_.kAsmDouble)) {
545      double val = expr->raw_value()->AsNumber();
546      byte code[] = {WASM_F64(val)};
547      current_function_builder_->EmitCode(code, sizeof(code));
548    } else {
549      UNREACHABLE();
550    }
551  }
552
553  void VisitRegExpLiteral(RegExpLiteral* expr) { UNREACHABLE(); }
554
555  void VisitObjectLiteral(ObjectLiteral* expr) {
556    ZoneList<ObjectLiteralProperty*>* props = expr->properties();
557    for (int i = 0; i < props->length(); ++i) {
558      ObjectLiteralProperty* prop = props->at(i);
559      DCHECK_EQ(kExportScope, scope_);
560      VariableProxy* expr = prop->value()->AsVariableProxy();
561      DCHECK_NOT_NULL(expr);
562      Variable* var = expr->var();
563      Literal* name = prop->key()->AsLiteral();
564      DCHECK_NOT_NULL(name);
565      DCHECK(name->IsPropertyName());
566      const AstRawString* raw_name = name->AsRawPropertyName();
567      if (var->is_function()) {
568        uint32_t index = LookupOrInsertFunction(var);
569        builder_->FunctionAt(index)->Exported(1);
570        builder_->FunctionAt(index)->SetName(
571            reinterpret_cast<const char*>(raw_name->raw_data()),
572            raw_name->length());
573      }
574    }
575  }
576
577  void VisitArrayLiteral(ArrayLiteral* expr) { UNREACHABLE(); }
578
579  void LoadInitFunction() {
580    current_function_builder_ = builder_->FunctionAt(init_function_index_);
581    scope_ = kInitScope;
582  }
583
584  void UnLoadInitFunction() {
585    scope_ = kModuleScope;
586    current_function_builder_ = nullptr;
587  }
588
589  void AddFunctionTable(VariableProxy* table, ArrayLiteral* funcs) {
590    FunctionType* func_type =
591        bounds_->get(funcs).lower->AsArray()->Element()->AsFunction();
592    LocalType return_type = TypeFrom(func_type->Result());
593    FunctionSig::Builder sig(zone(), return_type == kAstStmt ? 0 : 1,
594                             func_type->Arity());
595    if (return_type != kAstStmt) {
596      sig.AddReturn(static_cast<LocalType>(return_type));
597    }
598    for (int i = 0; i < func_type->Arity(); i++) {
599      sig.AddParam(TypeFrom(func_type->Parameter(i)));
600    }
601    uint32_t signature_index = builder_->AddSignature(sig.Build());
602    InsertFunctionTable(table->var(), next_table_index_, signature_index);
603    next_table_index_ += funcs->values()->length();
604    for (int i = 0; i < funcs->values()->length(); i++) {
605      VariableProxy* func = funcs->values()->at(i)->AsVariableProxy();
606      DCHECK_NOT_NULL(func);
607      builder_->AddIndirectFunction(LookupOrInsertFunction(func->var()));
608    }
609  }
610
611  struct FunctionTableIndices : public ZoneObject {
612    uint32_t start_index;
613    uint32_t signature_index;
614  };
615
616  void InsertFunctionTable(Variable* v, uint32_t start_index,
617                           uint32_t signature_index) {
618    FunctionTableIndices* container = new (zone()) FunctionTableIndices();
619    container->start_index = start_index;
620    container->signature_index = signature_index;
621    ZoneHashMap::Entry* entry = function_tables_.LookupOrInsert(
622        v, ComputePointerHash(v), ZoneAllocationPolicy(zone()));
623    entry->value = container;
624  }
625
626  FunctionTableIndices* LookupFunctionTable(Variable* v) {
627    ZoneHashMap::Entry* entry =
628        function_tables_.Lookup(v, ComputePointerHash(v));
629    DCHECK_NOT_NULL(entry);
630    return reinterpret_cast<FunctionTableIndices*>(entry->value);
631  }
632
633  class ImportedFunctionTable {
634   private:
635    class ImportedFunctionIndices : public ZoneObject {
636     public:
637      const char* name_;
638      int name_length_;
639      WasmModuleBuilder::SignatureMap signature_to_index_;
640
641      ImportedFunctionIndices(const char* name, int name_length, Zone* zone)
642          : name_(name), name_length_(name_length), signature_to_index_(zone) {}
643    };
644    ZoneHashMap table_;
645    AsmWasmBuilderImpl* builder_;
646
647   public:
648    explicit ImportedFunctionTable(AsmWasmBuilderImpl* builder)
649        : table_(HashMap::PointersMatch, ZoneHashMap::kDefaultHashMapCapacity,
650                 ZoneAllocationPolicy(builder->zone())),
651          builder_(builder) {}
652
653    void AddImport(Variable* v, const char* name, int name_length) {
654      ImportedFunctionIndices* indices = new (builder_->zone())
655          ImportedFunctionIndices(name, name_length, builder_->zone());
656      ZoneHashMap::Entry* entry = table_.LookupOrInsert(
657          v, ComputePointerHash(v), ZoneAllocationPolicy(builder_->zone()));
658      entry->value = indices;
659    }
660
661    uint32_t GetFunctionIndex(Variable* v, FunctionSig* sig) {
662      ZoneHashMap::Entry* entry = table_.Lookup(v, ComputePointerHash(v));
663      DCHECK_NOT_NULL(entry);
664      ImportedFunctionIndices* indices =
665          reinterpret_cast<ImportedFunctionIndices*>(entry->value);
666      WasmModuleBuilder::SignatureMap::iterator pos =
667          indices->signature_to_index_.find(sig);
668      if (pos != indices->signature_to_index_.end()) {
669        return pos->second;
670      } else {
671        uint32_t index = builder_->builder_->AddImport(
672            indices->name_, indices->name_length_, sig);
673        indices->signature_to_index_[sig] = index;
674        return index;
675      }
676    }
677  };
678
679  void EmitAssignmentLhs(Expression* target, MachineType* mtype) {
680    // Match the left hand side of the assignment.
681    VariableProxy* target_var = target->AsVariableProxy();
682    if (target_var != nullptr) {
683      // Left hand side is a local or a global variable, no code on LHS.
684      return;
685    }
686
687    Property* target_prop = target->AsProperty();
688    if (target_prop != nullptr) {
689      // Left hand side is a property access, i.e. the asm.js heap.
690      VisitPropertyAndEmitIndex(target_prop, mtype);
691      return;
692    }
693
694    if (target_var == nullptr && target_prop == nullptr) {
695      UNREACHABLE();  // invalid assignment.
696    }
697  }
698
699  void EmitAssignmentRhs(Expression* target, Expression* value, bool* is_nop) {
700    BinaryOperation* binop = value->AsBinaryOperation();
701    if (binop != nullptr) {
702      if (scope_ == kInitScope) {
703        // Handle foreign variables in the initialization scope.
704        Property* prop = binop->left()->AsProperty();
705        if (binop->op() == Token::MUL) {
706          DCHECK(binop->right()->IsLiteral());
707          DCHECK_EQ(1.0, binop->right()->AsLiteral()->raw_value()->AsNumber());
708          DCHECK(binop->right()->AsLiteral()->raw_value()->ContainsDot());
709          VisitForeignVariable(true, prop);
710          return;
711        } else if (binop->op() == Token::BIT_OR) {
712          DCHECK(binop->right()->IsLiteral());
713          DCHECK_EQ(0.0, binop->right()->AsLiteral()->raw_value()->AsNumber());
714          DCHECK(!binop->right()->AsLiteral()->raw_value()->ContainsDot());
715          VisitForeignVariable(false, prop);
716          return;
717        } else {
718          UNREACHABLE();
719        }
720      }
721      if (MatchBinaryOperation(binop) == kAsIs) {
722        VariableProxy* target_var = target->AsVariableProxy();
723        VariableProxy* effective_value_var = GetLeft(binop)->AsVariableProxy();
724        if (target_var != nullptr && effective_value_var != nullptr &&
725            target_var->var() == effective_value_var->var()) {
726          *is_nop = true;
727          return;
728        }
729      }
730    }
731    RECURSE(Visit(value));
732  }
733
734  void EmitAssignment(Assignment* expr, MachineType type) {
735    // Match the left hand side of the assignment.
736    VariableProxy* target_var = expr->target()->AsVariableProxy();
737    if (target_var != nullptr) {
738      // Left hand side is a local or a global variable.
739      Variable* var = target_var->var();
740      LocalType var_type = TypeOf(expr);
741      DCHECK_NE(kAstStmt, var_type);
742      if (var->IsContextSlot()) {
743        current_function_builder_->EmitWithVarInt(
744            kExprStoreGlobal, LookupOrInsertGlobal(var, var_type));
745      } else {
746        current_function_builder_->EmitSetLocal(
747            LookupOrInsertLocal(var, var_type));
748      }
749    }
750
751    Property* target_prop = expr->target()->AsProperty();
752    if (target_prop != nullptr) {
753      // Left hand side is a property access, i.e. the asm.js heap.
754      if (TypeOf(expr->value()) == kAstF64 && expr->target()->IsProperty() &&
755          bounds_->get(expr->target()->AsProperty()->obj())
756              .lower->Is(cache_.kFloat32Array)) {
757        current_function_builder_->Emit(kExprF32ConvertF64);
758      }
759      WasmOpcode opcode;
760      if (type == MachineType::Int8()) {
761        opcode = kExprI32AsmjsStoreMem8;
762      } else if (type == MachineType::Uint8()) {
763        opcode = kExprI32AsmjsStoreMem8;
764      } else if (type == MachineType::Int16()) {
765        opcode = kExprI32AsmjsStoreMem16;
766      } else if (type == MachineType::Uint16()) {
767        opcode = kExprI32AsmjsStoreMem16;
768      } else if (type == MachineType::Int32()) {
769        opcode = kExprI32AsmjsStoreMem;
770      } else if (type == MachineType::Uint32()) {
771        opcode = kExprI32AsmjsStoreMem;
772      } else if (type == MachineType::Float32()) {
773        opcode = kExprF32AsmjsStoreMem;
774      } else if (type == MachineType::Float64()) {
775        opcode = kExprF64AsmjsStoreMem;
776      } else {
777        UNREACHABLE();
778      }
779      current_function_builder_->Emit(opcode);
780    }
781
782    if (target_var == nullptr && target_prop == nullptr) {
783      UNREACHABLE();  // invalid assignment.
784    }
785  }
786
787  void VisitAssignment(Assignment* expr) {
788    bool as_init = false;
789    if (scope_ == kModuleScope) {
790      Property* prop = expr->value()->AsProperty();
791      if (prop != nullptr) {
792        VariableProxy* vp = prop->obj()->AsVariableProxy();
793        if (vp != nullptr && vp->var()->IsParameter() &&
794            vp->var()->index() == 1) {
795          VariableProxy* target = expr->target()->AsVariableProxy();
796          if (bounds_->get(target).lower->Is(Type::Function())) {
797            const AstRawString* name =
798                prop->key()->AsLiteral()->AsRawPropertyName();
799            imported_function_table_.AddImport(
800                target->var(), reinterpret_cast<const char*>(name->raw_data()),
801                name->length());
802          }
803        }
804        // Property values in module scope don't emit code, so return.
805        return;
806      }
807      ArrayLiteral* funcs = expr->value()->AsArrayLiteral();
808      if (funcs != nullptr &&
809          bounds_->get(funcs).lower->AsArray()->Element()->IsFunction()) {
810        VariableProxy* target = expr->target()->AsVariableProxy();
811        DCHECK_NOT_NULL(target);
812        AddFunctionTable(target, funcs);
813        // Only add to the function table. No init needed.
814        return;
815      }
816      if (expr->value()->IsCallNew()) {
817        // No init code to emit for CallNew nodes.
818        return;
819      }
820      as_init = true;
821    }
822
823    if (as_init) LoadInitFunction();
824    MachineType mtype;
825    bool is_nop = false;
826    EmitAssignmentLhs(expr->target(), &mtype);
827    EmitAssignmentRhs(expr->target(), expr->value(), &is_nop);
828    if (!is_nop) {
829      EmitAssignment(expr, mtype);
830    }
831    if (as_init) UnLoadInitFunction();
832  }
833
834  void VisitYield(Yield* expr) { UNREACHABLE(); }
835
836  void VisitThrow(Throw* expr) { UNREACHABLE(); }
837
838  void VisitForeignVariable(bool is_float, Property* expr) {
839    DCHECK(expr->obj()->AsVariableProxy());
840    DCHECK(VariableLocation::PARAMETER ==
841           expr->obj()->AsVariableProxy()->var()->location());
842    DCHECK_EQ(1, expr->obj()->AsVariableProxy()->var()->index());
843    Literal* key_literal = expr->key()->AsLiteral();
844    DCHECK_NOT_NULL(key_literal);
845    if (!key_literal->value().is_null() && !foreign_.is_null() &&
846        foreign_->IsObject()) {
847      Handle<Name> name =
848          i::Object::ToName(isolate_, key_literal->value()).ToHandleChecked();
849      MaybeHandle<Object> maybe_value = i::Object::GetProperty(foreign_, name);
850      if (!maybe_value.is_null()) {
851        Handle<Object> value = maybe_value.ToHandleChecked();
852        if (is_float) {
853          MaybeHandle<Object> maybe_nvalue = i::Object::ToNumber(value);
854          if (!maybe_nvalue.is_null()) {
855            Handle<Object> nvalue = maybe_nvalue.ToHandleChecked();
856            if (nvalue->IsNumber()) {
857              double val = nvalue->Number();
858              byte code[] = {WASM_F64(val)};
859              current_function_builder_->EmitCode(code, sizeof(code));
860              return;
861            }
862          }
863        } else {
864          MaybeHandle<Object> maybe_nvalue =
865              i::Object::ToInt32(isolate_, value);
866          if (!maybe_nvalue.is_null()) {
867            Handle<Object> nvalue = maybe_nvalue.ToHandleChecked();
868            if (nvalue->IsNumber()) {
869              int32_t val = static_cast<int32_t>(nvalue->Number());
870              current_function_builder_->EmitI32Const(val);
871              return;
872            }
873          }
874        }
875      }
876    }
877    if (is_float) {
878      byte code[] = {WASM_F64(std::numeric_limits<double>::quiet_NaN())};
879      current_function_builder_->EmitCode(code, sizeof(code));
880    } else {
881      byte code[] = {WASM_I32V_1(0)};
882      current_function_builder_->EmitCode(code, sizeof(code));
883    }
884  }
885
886  void VisitPropertyAndEmitIndex(Property* expr, MachineType* mtype) {
887    Expression* obj = expr->obj();
888    DCHECK_EQ(bounds_->get(obj).lower, bounds_->get(obj).upper);
889    Type* type = bounds_->get(obj).lower;
890    int size;
891    if (type->Is(cache_.kUint8Array)) {
892      *mtype = MachineType::Uint8();
893      size = 1;
894    } else if (type->Is(cache_.kInt8Array)) {
895      *mtype = MachineType::Int8();
896      size = 1;
897    } else if (type->Is(cache_.kUint16Array)) {
898      *mtype = MachineType::Uint16();
899      size = 2;
900    } else if (type->Is(cache_.kInt16Array)) {
901      *mtype = MachineType::Int16();
902      size = 2;
903    } else if (type->Is(cache_.kUint32Array)) {
904      *mtype = MachineType::Uint32();
905      size = 4;
906    } else if (type->Is(cache_.kInt32Array)) {
907      *mtype = MachineType::Int32();
908      size = 4;
909    } else if (type->Is(cache_.kUint32Array)) {
910      *mtype = MachineType::Uint32();
911      size = 4;
912    } else if (type->Is(cache_.kFloat32Array)) {
913      *mtype = MachineType::Float32();
914      size = 4;
915    } else if (type->Is(cache_.kFloat64Array)) {
916      *mtype = MachineType::Float64();
917      size = 8;
918    } else {
919      UNREACHABLE();
920    }
921    if (size == 1) {
922      // Allow more general expression in byte arrays than the spec
923      // strictly permits.
924      // Early versions of Emscripten emit HEAP8[HEAP32[..]|0] in
925      // places that strictly should be HEAP8[HEAP32[..]>>0].
926      RECURSE(Visit(expr->key()));
927      return;
928    }
929
930    Literal* value = expr->key()->AsLiteral();
931    if (value) {
932      DCHECK(value->raw_value()->IsNumber());
933      DCHECK_EQ(kAstI32, TypeOf(value));
934      int32_t val = static_cast<int32_t>(value->raw_value()->AsNumber());
935      // TODO(titzer): handle overflow here.
936      current_function_builder_->EmitI32Const(val * size);
937      return;
938    }
939    BinaryOperation* binop = expr->key()->AsBinaryOperation();
940    if (binop) {
941      DCHECK_EQ(Token::SAR, binop->op());
942      DCHECK(binop->right()->AsLiteral()->raw_value()->IsNumber());
943      DCHECK(kAstI32 == TypeOf(binop->right()->AsLiteral()));
944      DCHECK_EQ(size,
945                1 << static_cast<int>(
946                    binop->right()->AsLiteral()->raw_value()->AsNumber()));
947      // Mask bottom bits to match asm.js behavior.
948      byte mask = static_cast<byte>(~(size - 1));
949      RECURSE(Visit(binop->left()));
950      current_function_builder_->EmitWithU8(kExprI8Const, mask);
951      current_function_builder_->Emit(kExprI32And);
952      return;
953    }
954    UNREACHABLE();
955  }
956
957  void VisitProperty(Property* expr) {
958    MachineType type;
959    VisitPropertyAndEmitIndex(expr, &type);
960    WasmOpcode opcode;
961    if (type == MachineType::Int8()) {
962      opcode = kExprI32AsmjsLoadMem8S;
963    } else if (type == MachineType::Uint8()) {
964      opcode = kExprI32AsmjsLoadMem8U;
965    } else if (type == MachineType::Int16()) {
966      opcode = kExprI32AsmjsLoadMem16S;
967    } else if (type == MachineType::Uint16()) {
968      opcode = kExprI32AsmjsLoadMem16U;
969    } else if (type == MachineType::Int32()) {
970      opcode = kExprI32AsmjsLoadMem;
971    } else if (type == MachineType::Uint32()) {
972      opcode = kExprI32AsmjsLoadMem;
973    } else if (type == MachineType::Float32()) {
974      opcode = kExprF32AsmjsLoadMem;
975    } else if (type == MachineType::Float64()) {
976      opcode = kExprF64AsmjsLoadMem;
977    } else {
978      UNREACHABLE();
979    }
980
981    current_function_builder_->Emit(opcode);
982  }
983
984  bool VisitStdlibFunction(Call* call, VariableProxy* expr) {
985    Variable* var = expr->var();
986    AsmTyper::StandardMember standard_object =
987        typer_->VariableAsStandardMember(var);
988    ZoneList<Expression*>* args = call->arguments();
989    LocalType call_type = TypeOf(call);
990
991    switch (standard_object) {
992      case AsmTyper::kNone: {
993        return false;
994      }
995      case AsmTyper::kMathAcos: {
996        VisitCallArgs(call);
997        DCHECK_EQ(kAstF64, call_type);
998        current_function_builder_->Emit(kExprF64Acos);
999        break;
1000      }
1001      case AsmTyper::kMathAsin: {
1002        VisitCallArgs(call);
1003        DCHECK_EQ(kAstF64, call_type);
1004        current_function_builder_->Emit(kExprF64Asin);
1005        break;
1006      }
1007      case AsmTyper::kMathAtan: {
1008        VisitCallArgs(call);
1009        DCHECK_EQ(kAstF64, call_type);
1010        current_function_builder_->Emit(kExprF64Atan);
1011        break;
1012      }
1013      case AsmTyper::kMathCos: {
1014        VisitCallArgs(call);
1015        DCHECK_EQ(kAstF64, call_type);
1016        current_function_builder_->Emit(kExprF64Cos);
1017        break;
1018      }
1019      case AsmTyper::kMathSin: {
1020        VisitCallArgs(call);
1021        DCHECK_EQ(kAstF64, call_type);
1022        current_function_builder_->Emit(kExprF64Sin);
1023        break;
1024      }
1025      case AsmTyper::kMathTan: {
1026        VisitCallArgs(call);
1027        DCHECK_EQ(kAstF64, call_type);
1028        current_function_builder_->Emit(kExprF64Tan);
1029        break;
1030      }
1031      case AsmTyper::kMathExp: {
1032        VisitCallArgs(call);
1033        DCHECK_EQ(kAstF64, call_type);
1034        current_function_builder_->Emit(kExprF64Exp);
1035        break;
1036      }
1037      case AsmTyper::kMathLog: {
1038        VisitCallArgs(call);
1039        DCHECK_EQ(kAstF64, call_type);
1040        current_function_builder_->Emit(kExprF64Log);
1041        break;
1042      }
1043      case AsmTyper::kMathCeil: {
1044        VisitCallArgs(call);
1045        if (call_type == kAstF32) {
1046          current_function_builder_->Emit(kExprF32Ceil);
1047        } else if (call_type == kAstF64) {
1048          current_function_builder_->Emit(kExprF64Ceil);
1049        } else {
1050          UNREACHABLE();
1051        }
1052        break;
1053      }
1054      case AsmTyper::kMathFloor: {
1055        VisitCallArgs(call);
1056        if (call_type == kAstF32) {
1057          current_function_builder_->Emit(kExprF32Floor);
1058        } else if (call_type == kAstF64) {
1059          current_function_builder_->Emit(kExprF64Floor);
1060        } else {
1061          UNREACHABLE();
1062        }
1063        break;
1064      }
1065      case AsmTyper::kMathSqrt: {
1066        VisitCallArgs(call);
1067        if (call_type == kAstF32) {
1068          current_function_builder_->Emit(kExprF32Sqrt);
1069        } else if (call_type == kAstF64) {
1070          current_function_builder_->Emit(kExprF64Sqrt);
1071        } else {
1072          UNREACHABLE();
1073        }
1074        break;
1075      }
1076      case AsmTyper::kMathAbs: {
1077        if (call_type == kAstI32) {
1078          uint32_t tmp = current_function_builder_->AddLocal(kAstI32);
1079
1080          // if set_local(tmp, x) < 0
1081          Visit(call->arguments()->at(0));
1082          current_function_builder_->EmitSetLocal(tmp);
1083          byte code[] = {WASM_I8(0)};
1084          current_function_builder_->EmitCode(code, sizeof(code));
1085          current_function_builder_->Emit(kExprI32LtS);
1086          current_function_builder_->Emit(kExprIf);
1087
1088          // then (0 - tmp)
1089          current_function_builder_->EmitCode(code, sizeof(code));
1090          current_function_builder_->EmitGetLocal(tmp);
1091          current_function_builder_->Emit(kExprI32Sub);
1092
1093          // else tmp
1094          current_function_builder_->Emit(kExprElse);
1095          current_function_builder_->EmitGetLocal(tmp);
1096          // end
1097          current_function_builder_->Emit(kExprEnd);
1098
1099        } else if (call_type == kAstF32) {
1100          VisitCallArgs(call);
1101          current_function_builder_->Emit(kExprF32Abs);
1102        } else if (call_type == kAstF64) {
1103          VisitCallArgs(call);
1104          current_function_builder_->Emit(kExprF64Abs);
1105        } else {
1106          UNREACHABLE();
1107        }
1108        break;
1109      }
1110      case AsmTyper::kMathMin: {
1111        // TODO(bradnelson): Change wasm to match Math.min in asm.js mode.
1112        if (call_type == kAstI32) {
1113          uint32_t tmp_x = current_function_builder_->AddLocal(kAstI32);
1114          uint32_t tmp_y = current_function_builder_->AddLocal(kAstI32);
1115
1116          // if set_local(tmp_x, x) < set_local(tmp_y, y)
1117          Visit(call->arguments()->at(0));
1118          current_function_builder_->EmitSetLocal(tmp_x);
1119
1120          Visit(call->arguments()->at(1));
1121          current_function_builder_->EmitSetLocal(tmp_y);
1122
1123          current_function_builder_->Emit(kExprI32LeS);
1124          current_function_builder_->Emit(kExprIf);
1125
1126          // then tmp_x
1127          current_function_builder_->EmitGetLocal(tmp_x);
1128
1129          // else tmp_y
1130          current_function_builder_->Emit(kExprElse);
1131          current_function_builder_->EmitGetLocal(tmp_y);
1132          current_function_builder_->Emit(kExprEnd);
1133
1134        } else if (call_type == kAstF32) {
1135          VisitCallArgs(call);
1136          current_function_builder_->Emit(kExprF32Min);
1137        } else if (call_type == kAstF64) {
1138          VisitCallArgs(call);
1139          current_function_builder_->Emit(kExprF64Min);
1140        } else {
1141          UNREACHABLE();
1142        }
1143        break;
1144      }
1145      case AsmTyper::kMathMax: {
1146        // TODO(bradnelson): Change wasm to match Math.max in asm.js mode.
1147        if (call_type == kAstI32) {
1148          uint32_t tmp_x = current_function_builder_->AddLocal(kAstI32);
1149          uint32_t tmp_y = current_function_builder_->AddLocal(kAstI32);
1150
1151          // if set_local(tmp_x, x) < set_local(tmp_y, y)
1152          Visit(call->arguments()->at(0));
1153
1154          current_function_builder_->EmitSetLocal(tmp_x);
1155
1156          Visit(call->arguments()->at(1));
1157          current_function_builder_->EmitSetLocal(tmp_y);
1158
1159          current_function_builder_->Emit(kExprI32LeS);
1160          current_function_builder_->Emit(kExprIf);
1161
1162          // then tmp_y
1163          current_function_builder_->EmitGetLocal(tmp_y);
1164
1165          // else tmp_x
1166          current_function_builder_->Emit(kExprElse);
1167          current_function_builder_->EmitGetLocal(tmp_x);
1168          current_function_builder_->Emit(kExprEnd);
1169
1170        } else if (call_type == kAstF32) {
1171          VisitCallArgs(call);
1172          current_function_builder_->Emit(kExprF32Max);
1173        } else if (call_type == kAstF64) {
1174          VisitCallArgs(call);
1175          current_function_builder_->Emit(kExprF64Max);
1176        } else {
1177          UNREACHABLE();
1178        }
1179        break;
1180      }
1181      case AsmTyper::kMathAtan2: {
1182        VisitCallArgs(call);
1183        DCHECK_EQ(kAstF64, call_type);
1184        current_function_builder_->Emit(kExprF64Atan2);
1185        break;
1186      }
1187      case AsmTyper::kMathPow: {
1188        VisitCallArgs(call);
1189        DCHECK_EQ(kAstF64, call_type);
1190        current_function_builder_->Emit(kExprF64Pow);
1191        break;
1192      }
1193      case AsmTyper::kMathImul: {
1194        VisitCallArgs(call);
1195        current_function_builder_->Emit(kExprI32Mul);
1196        break;
1197      }
1198      case AsmTyper::kMathFround: {
1199        DCHECK(args->length() == 1);
1200        Literal* literal = args->at(0)->AsLiteral();
1201        if (literal != nullptr) {
1202          // constant fold Math.fround(#const);
1203          if (literal->raw_value()->IsNumber()) {
1204            float val = static_cast<float>(literal->raw_value()->AsNumber());
1205            byte code[] = {WASM_F32(val)};
1206            current_function_builder_->EmitCode(code, sizeof(code));
1207            return true;
1208          }
1209        }
1210        VisitCallArgs(call);
1211        switch (TypeIndexOf(args->at(0))) {
1212          case kInt32:
1213          case kFixnum:
1214            current_function_builder_->Emit(kExprF32SConvertI32);
1215            break;
1216          case kUint32:
1217            current_function_builder_->Emit(kExprF32UConvertI32);
1218            break;
1219          case kFloat32:
1220            break;
1221          case kFloat64:
1222            current_function_builder_->Emit(kExprF32ConvertF64);
1223            break;
1224          default:
1225            UNREACHABLE();
1226        }
1227        break;
1228      }
1229      default: {
1230        UNREACHABLE();
1231        break;
1232      }
1233    }
1234    return true;
1235  }
1236
1237  void VisitCallArgs(Call* expr) {
1238    ZoneList<Expression*>* args = expr->arguments();
1239    for (int i = 0; i < args->length(); ++i) {
1240      Expression* arg = args->at(i);
1241      RECURSE(Visit(arg));
1242    }
1243  }
1244
1245  void VisitCall(Call* expr) {
1246    Call::CallType call_type = expr->GetCallType(isolate_);
1247    switch (call_type) {
1248      case Call::OTHER_CALL: {
1249        DCHECK_EQ(kFuncScope, scope_);
1250        VariableProxy* proxy = expr->expression()->AsVariableProxy();
1251        if (proxy != nullptr) {
1252          if (VisitStdlibFunction(expr, proxy)) {
1253            return;
1254          }
1255        }
1256        uint32_t index;
1257        VariableProxy* vp = expr->expression()->AsVariableProxy();
1258        if (vp != nullptr &&
1259            Type::Any()->Is(bounds_->get(vp).lower->AsFunction()->Result())) {
1260          LocalType return_type = TypeOf(expr);
1261          ZoneList<Expression*>* args = expr->arguments();
1262          FunctionSig::Builder sig(zone(), return_type == kAstStmt ? 0 : 1,
1263                                   args->length());
1264          if (return_type != kAstStmt) {
1265            sig.AddReturn(return_type);
1266          }
1267          for (int i = 0; i < args->length(); i++) {
1268            sig.AddParam(TypeOf(args->at(i)));
1269          }
1270          index =
1271              imported_function_table_.GetFunctionIndex(vp->var(), sig.Build());
1272          VisitCallArgs(expr);
1273          current_function_builder_->Emit(kExprCallImport);
1274          current_function_builder_->EmitVarInt(expr->arguments()->length());
1275          current_function_builder_->EmitVarInt(index);
1276        } else {
1277          index = LookupOrInsertFunction(vp->var());
1278          VisitCallArgs(expr);
1279          current_function_builder_->Emit(kExprCallFunction);
1280          current_function_builder_->EmitVarInt(expr->arguments()->length());
1281          current_function_builder_->EmitVarInt(index);
1282        }
1283        break;
1284      }
1285      case Call::KEYED_PROPERTY_CALL: {
1286        DCHECK_EQ(kFuncScope, scope_);
1287        Property* p = expr->expression()->AsProperty();
1288        DCHECK_NOT_NULL(p);
1289        VariableProxy* var = p->obj()->AsVariableProxy();
1290        DCHECK_NOT_NULL(var);
1291        FunctionTableIndices* indices = LookupFunctionTable(var->var());
1292        RECURSE(Visit(p->key()));
1293        current_function_builder_->EmitI32Const(indices->start_index);
1294        current_function_builder_->Emit(kExprI32Add);
1295        VisitCallArgs(expr);
1296        current_function_builder_->Emit(kExprCallIndirect);
1297        current_function_builder_->EmitVarInt(expr->arguments()->length());
1298        current_function_builder_->EmitVarInt(indices->signature_index);
1299        break;
1300      }
1301      default:
1302        UNREACHABLE();
1303    }
1304  }
1305
1306  void VisitCallNew(CallNew* expr) { UNREACHABLE(); }
1307
1308  void VisitCallRuntime(CallRuntime* expr) { UNREACHABLE(); }
1309
1310  void VisitUnaryOperation(UnaryOperation* expr) {
1311    RECURSE(Visit(expr->expression()));
1312    switch (expr->op()) {
1313      case Token::NOT: {
1314        DCHECK_EQ(kAstI32, TypeOf(expr->expression()));
1315        current_function_builder_->Emit(kExprI32Eqz);
1316        break;
1317      }
1318      default:
1319        UNREACHABLE();
1320    }
1321  }
1322
1323  void VisitCountOperation(CountOperation* expr) { UNREACHABLE(); }
1324
1325  bool MatchIntBinaryOperation(BinaryOperation* expr, Token::Value op,
1326                               int32_t val) {
1327    DCHECK_NOT_NULL(expr->right());
1328    if (expr->op() == op && expr->right()->IsLiteral() &&
1329        TypeOf(expr) == kAstI32) {
1330      Literal* right = expr->right()->AsLiteral();
1331      DCHECK(right->raw_value()->IsNumber());
1332      if (static_cast<int32_t>(right->raw_value()->AsNumber()) == val) {
1333        return true;
1334      }
1335    }
1336    return false;
1337  }
1338
1339  bool MatchDoubleBinaryOperation(BinaryOperation* expr, Token::Value op,
1340                                  double val) {
1341    DCHECK_NOT_NULL(expr->right());
1342    if (expr->op() == op && expr->right()->IsLiteral() &&
1343        TypeOf(expr) == kAstF64) {
1344      Literal* right = expr->right()->AsLiteral();
1345      DCHECK(right->raw_value()->IsNumber());
1346      if (right->raw_value()->AsNumber() == val) {
1347        return true;
1348      }
1349    }
1350    return false;
1351  }
1352
1353  enum ConvertOperation { kNone, kAsIs, kToInt, kToDouble };
1354
1355  ConvertOperation MatchOr(BinaryOperation* expr) {
1356    if (MatchIntBinaryOperation(expr, Token::BIT_OR, 0) &&
1357        (TypeOf(expr->left()) == kAstI32)) {
1358      return kAsIs;
1359    } else {
1360      return kNone;
1361    }
1362  }
1363
1364  ConvertOperation MatchShr(BinaryOperation* expr) {
1365    if (MatchIntBinaryOperation(expr, Token::SHR, 0)) {
1366      // TODO(titzer): this probably needs to be kToUint
1367      return (TypeOf(expr->left()) == kAstI32) ? kAsIs : kToInt;
1368    } else {
1369      return kNone;
1370    }
1371  }
1372
1373  ConvertOperation MatchXor(BinaryOperation* expr) {
1374    if (MatchIntBinaryOperation(expr, Token::BIT_XOR, 0xffffffff)) {
1375      DCHECK_EQ(kAstI32, TypeOf(expr->left()));
1376      DCHECK_EQ(kAstI32, TypeOf(expr->right()));
1377      BinaryOperation* op = expr->left()->AsBinaryOperation();
1378      if (op != nullptr) {
1379        if (MatchIntBinaryOperation(op, Token::BIT_XOR, 0xffffffff)) {
1380          DCHECK_EQ(kAstI32, TypeOf(op->right()));
1381          if (TypeOf(op->left()) != kAstI32) {
1382            return kToInt;
1383          } else {
1384            return kAsIs;
1385          }
1386        }
1387      }
1388    }
1389    return kNone;
1390  }
1391
1392  ConvertOperation MatchMul(BinaryOperation* expr) {
1393    if (MatchDoubleBinaryOperation(expr, Token::MUL, 1.0)) {
1394      DCHECK_EQ(kAstF64, TypeOf(expr->right()));
1395      if (TypeOf(expr->left()) != kAstF64) {
1396        return kToDouble;
1397      } else {
1398        return kAsIs;
1399      }
1400    } else {
1401      return kNone;
1402    }
1403  }
1404
1405  ConvertOperation MatchBinaryOperation(BinaryOperation* expr) {
1406    switch (expr->op()) {
1407      case Token::BIT_OR:
1408        return MatchOr(expr);
1409      case Token::SHR:
1410        return MatchShr(expr);
1411      case Token::BIT_XOR:
1412        return MatchXor(expr);
1413      case Token::MUL:
1414        return MatchMul(expr);
1415      default:
1416        return kNone;
1417    }
1418  }
1419
1420// Work around Mul + Div being defined in PPC assembler.
1421#ifdef Mul
1422#undef Mul
1423#endif
1424
1425#define NON_SIGNED_BINOP(op)      \
1426  static WasmOpcode opcodes[] = { \
1427    kExprI32##op,                 \
1428    kExprI32##op,                 \
1429    kExprF32##op,                 \
1430    kExprF64##op                  \
1431  }
1432
1433#define SIGNED_BINOP(op)          \
1434  static WasmOpcode opcodes[] = { \
1435    kExprI32##op##S,              \
1436    kExprI32##op##U,              \
1437    kExprF32##op,                 \
1438    kExprF64##op                  \
1439  }
1440
1441#define NON_SIGNED_INT_BINOP(op) \
1442  static WasmOpcode opcodes[] = { kExprI32##op, kExprI32##op }
1443
1444#define BINOP_CASE(token, op, V, ignore_sign)                         \
1445  case token: {                                                       \
1446    V(op);                                                            \
1447    int type = TypeIndexOf(expr->left(), expr->right(), ignore_sign); \
1448    current_function_builder_->Emit(opcodes[type]);                   \
1449    break;                                                            \
1450  }
1451
1452  Expression* GetLeft(BinaryOperation* expr) {
1453    if (expr->op() == Token::BIT_XOR) {
1454      return expr->left()->AsBinaryOperation()->left();
1455    } else {
1456      return expr->left();
1457    }
1458  }
1459
1460  void VisitBinaryOperation(BinaryOperation* expr) {
1461    ConvertOperation convertOperation = MatchBinaryOperation(expr);
1462    if (convertOperation == kToDouble) {
1463      RECURSE(Visit(expr->left()));
1464      TypeIndex type = TypeIndexOf(expr->left());
1465      if (type == kInt32 || type == kFixnum) {
1466        current_function_builder_->Emit(kExprF64SConvertI32);
1467      } else if (type == kUint32) {
1468        current_function_builder_->Emit(kExprF64UConvertI32);
1469      } else if (type == kFloat32) {
1470        current_function_builder_->Emit(kExprF64ConvertF32);
1471      } else {
1472        UNREACHABLE();
1473      }
1474    } else if (convertOperation == kToInt) {
1475      RECURSE(Visit(GetLeft(expr)));
1476      TypeIndex type = TypeIndexOf(GetLeft(expr));
1477      if (type == kFloat32) {
1478        current_function_builder_->Emit(kExprI32AsmjsSConvertF32);
1479      } else if (type == kFloat64) {
1480        current_function_builder_->Emit(kExprI32AsmjsSConvertF64);
1481      } else {
1482        UNREACHABLE();
1483      }
1484    } else if (convertOperation == kAsIs) {
1485      RECURSE(Visit(GetLeft(expr)));
1486    } else {
1487      if (expr->op() == Token::COMMA) {
1488        current_function_builder_->Emit(kExprBlock);
1489      }
1490
1491      RECURSE(Visit(expr->left()));
1492      RECURSE(Visit(expr->right()));
1493
1494      if (expr->op() == Token::COMMA) {
1495        current_function_builder_->Emit(kExprEnd);
1496      }
1497
1498      switch (expr->op()) {
1499        BINOP_CASE(Token::ADD, Add, NON_SIGNED_BINOP, true);
1500        BINOP_CASE(Token::SUB, Sub, NON_SIGNED_BINOP, true);
1501        BINOP_CASE(Token::MUL, Mul, NON_SIGNED_BINOP, true);
1502        BINOP_CASE(Token::BIT_OR, Ior, NON_SIGNED_INT_BINOP, true);
1503        BINOP_CASE(Token::BIT_AND, And, NON_SIGNED_INT_BINOP, true);
1504        BINOP_CASE(Token::BIT_XOR, Xor, NON_SIGNED_INT_BINOP, true);
1505        BINOP_CASE(Token::SHL, Shl, NON_SIGNED_INT_BINOP, true);
1506        BINOP_CASE(Token::SAR, ShrS, NON_SIGNED_INT_BINOP, true);
1507        BINOP_CASE(Token::SHR, ShrU, NON_SIGNED_INT_BINOP, true);
1508        case Token::DIV: {
1509          static WasmOpcode opcodes[] = {kExprI32AsmjsDivS, kExprI32AsmjsDivU,
1510                                         kExprF32Div, kExprF64Div};
1511          int type = TypeIndexOf(expr->left(), expr->right(), false);
1512          current_function_builder_->Emit(opcodes[type]);
1513          break;
1514        }
1515        case Token::MOD: {
1516          TypeIndex type = TypeIndexOf(expr->left(), expr->right(), false);
1517          if (type == kInt32) {
1518            current_function_builder_->Emit(kExprI32AsmjsRemS);
1519          } else if (type == kUint32) {
1520            current_function_builder_->Emit(kExprI32AsmjsRemU);
1521          } else if (type == kFloat64) {
1522            current_function_builder_->Emit(kExprF64Mod);
1523            return;
1524          } else {
1525            UNREACHABLE();
1526          }
1527          break;
1528        }
1529        case Token::COMMA: {
1530          break;
1531        }
1532        default:
1533          UNREACHABLE();
1534      }
1535    }
1536  }
1537
1538  void VisitCompareOperation(CompareOperation* expr) {
1539    RECURSE(Visit(expr->left()));
1540    RECURSE(Visit(expr->right()));
1541    switch (expr->op()) {
1542      BINOP_CASE(Token::EQ, Eq, NON_SIGNED_BINOP, false);
1543      BINOP_CASE(Token::LT, Lt, SIGNED_BINOP, false);
1544      BINOP_CASE(Token::LTE, Le, SIGNED_BINOP, false);
1545      BINOP_CASE(Token::GT, Gt, SIGNED_BINOP, false);
1546      BINOP_CASE(Token::GTE, Ge, SIGNED_BINOP, false);
1547      default:
1548        UNREACHABLE();
1549    }
1550  }
1551
1552#undef BINOP_CASE
1553#undef NON_SIGNED_INT_BINOP
1554#undef SIGNED_BINOP
1555#undef NON_SIGNED_BINOP
1556
1557  enum TypeIndex {
1558    kInt32 = 0,
1559    kUint32 = 1,
1560    kFloat32 = 2,
1561    kFloat64 = 3,
1562    kFixnum = 4
1563  };
1564
1565  TypeIndex TypeIndexOf(Expression* left, Expression* right, bool ignore_sign) {
1566    TypeIndex left_index = TypeIndexOf(left);
1567    TypeIndex right_index = TypeIndexOf(right);
1568    if (left_index == kFixnum) {
1569      left_index = right_index;
1570    }
1571    if (right_index == kFixnum) {
1572      right_index = left_index;
1573    }
1574    if (left_index == kFixnum && right_index == kFixnum) {
1575      left_index = kInt32;
1576      right_index = kInt32;
1577    }
1578    DCHECK((left_index == right_index) ||
1579           (ignore_sign && (left_index <= 1) && (right_index <= 1)));
1580    return left_index;
1581  }
1582
1583  TypeIndex TypeIndexOf(Expression* expr) {
1584    DCHECK_EQ(bounds_->get(expr).lower, bounds_->get(expr).upper);
1585    Type* type = bounds_->get(expr).lower;
1586    if (type->Is(cache_.kAsmFixnum)) {
1587      return kFixnum;
1588    } else if (type->Is(cache_.kAsmSigned)) {
1589      return kInt32;
1590    } else if (type->Is(cache_.kAsmUnsigned)) {
1591      return kUint32;
1592    } else if (type->Is(cache_.kAsmInt)) {
1593      return kInt32;
1594    } else if (type->Is(cache_.kAsmFloat)) {
1595      return kFloat32;
1596    } else if (type->Is(cache_.kAsmDouble)) {
1597      return kFloat64;
1598    } else {
1599      UNREACHABLE();
1600      return kInt32;
1601    }
1602  }
1603
1604#undef CASE
1605#undef NON_SIGNED_INT
1606#undef SIGNED
1607#undef NON_SIGNED
1608
1609  void VisitThisFunction(ThisFunction* expr) { UNREACHABLE(); }
1610
1611  void VisitDeclarations(ZoneList<Declaration*>* decls) {
1612    for (int i = 0; i < decls->length(); ++i) {
1613      Declaration* decl = decls->at(i);
1614      RECURSE(Visit(decl));
1615    }
1616  }
1617
1618  void VisitClassLiteral(ClassLiteral* expr) { UNREACHABLE(); }
1619
1620  void VisitSpread(Spread* expr) { UNREACHABLE(); }
1621
1622  void VisitSuperPropertyReference(SuperPropertyReference* expr) {
1623    UNREACHABLE();
1624  }
1625
1626  void VisitSuperCallReference(SuperCallReference* expr) { UNREACHABLE(); }
1627
1628  void VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement* expr) {
1629    UNREACHABLE();
1630  }
1631
1632  void VisitDoExpression(DoExpression* expr) { UNREACHABLE(); }
1633
1634  void VisitRewritableExpression(RewritableExpression* expr) { UNREACHABLE(); }
1635
1636  struct IndexContainer : public ZoneObject {
1637    uint32_t index;
1638  };
1639
1640  uint32_t LookupOrInsertLocal(Variable* v, LocalType type) {
1641    DCHECK_NOT_NULL(current_function_builder_);
1642    ZoneHashMap::Entry* entry =
1643        local_variables_.Lookup(v, ComputePointerHash(v));
1644    if (entry == nullptr) {
1645      uint32_t index;
1646      DCHECK(!v->IsParameter());
1647      index = current_function_builder_->AddLocal(type);
1648      IndexContainer* container = new (zone()) IndexContainer();
1649      container->index = index;
1650      entry = local_variables_.LookupOrInsert(v, ComputePointerHash(v),
1651                                              ZoneAllocationPolicy(zone()));
1652      entry->value = container;
1653    }
1654    return (reinterpret_cast<IndexContainer*>(entry->value))->index;
1655  }
1656
1657  void InsertParameter(Variable* v, LocalType type, uint32_t index) {
1658    DCHECK(v->IsParameter());
1659    DCHECK_NOT_NULL(current_function_builder_);
1660    ZoneHashMap::Entry* entry =
1661        local_variables_.Lookup(v, ComputePointerHash(v));
1662    DCHECK_NULL(entry);
1663    IndexContainer* container = new (zone()) IndexContainer();
1664    container->index = index;
1665    entry = local_variables_.LookupOrInsert(v, ComputePointerHash(v),
1666                                            ZoneAllocationPolicy(zone()));
1667    entry->value = container;
1668  }
1669
1670  uint32_t LookupOrInsertGlobal(Variable* v, LocalType type) {
1671    ZoneHashMap::Entry* entry =
1672        global_variables_.Lookup(v, ComputePointerHash(v));
1673    if (entry == nullptr) {
1674      uint32_t index =
1675          builder_->AddGlobal(WasmOpcodes::MachineTypeFor(type), 0);
1676      IndexContainer* container = new (zone()) IndexContainer();
1677      container->index = index;
1678      entry = global_variables_.LookupOrInsert(v, ComputePointerHash(v),
1679                                               ZoneAllocationPolicy(zone()));
1680      entry->value = container;
1681    }
1682    return (reinterpret_cast<IndexContainer*>(entry->value))->index;
1683  }
1684
1685  uint32_t LookupOrInsertFunction(Variable* v) {
1686    DCHECK_NOT_NULL(builder_);
1687    ZoneHashMap::Entry* entry = functions_.Lookup(v, ComputePointerHash(v));
1688    if (entry == nullptr) {
1689      uint32_t index = builder_->AddFunction();
1690      IndexContainer* container = new (zone()) IndexContainer();
1691      container->index = index;
1692      entry = functions_.LookupOrInsert(v, ComputePointerHash(v),
1693                                        ZoneAllocationPolicy(zone()));
1694      entry->value = container;
1695    }
1696    return (reinterpret_cast<IndexContainer*>(entry->value))->index;
1697  }
1698
1699  LocalType TypeOf(Expression* expr) {
1700    DCHECK_EQ(bounds_->get(expr).lower, bounds_->get(expr).upper);
1701    return TypeFrom(bounds_->get(expr).lower);
1702  }
1703
1704  LocalType TypeFrom(Type* type) {
1705    if (type->Is(cache_.kAsmInt)) {
1706      return kAstI32;
1707    } else if (type->Is(cache_.kAsmFloat)) {
1708      return kAstF32;
1709    } else if (type->Is(cache_.kAsmDouble)) {
1710      return kAstF64;
1711    } else {
1712      return kAstStmt;
1713    }
1714  }
1715
1716  Zone* zone() { return zone_; }
1717
1718  ZoneHashMap local_variables_;
1719  ZoneHashMap functions_;
1720  ZoneHashMap global_variables_;
1721  AsmScope scope_;
1722  WasmModuleBuilder* builder_;
1723  WasmFunctionBuilder* current_function_builder_;
1724  FunctionLiteral* literal_;
1725  Isolate* isolate_;
1726  Zone* zone_;
1727  Handle<Object> foreign_;
1728  AsmTyper* typer_;
1729  TypeCache const& cache_;
1730  ZoneVector<std::pair<BreakableStatement*, bool>> breakable_blocks_;
1731  uint32_t init_function_index_;
1732  uint32_t next_table_index_;
1733  ZoneHashMap function_tables_;
1734  ImportedFunctionTable imported_function_table_;
1735  const AstTypeBounds* bounds_;
1736
1737  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
1738
1739 private:
1740  DISALLOW_COPY_AND_ASSIGN(AsmWasmBuilderImpl);
1741};
1742
1743AsmWasmBuilder::AsmWasmBuilder(Isolate* isolate, Zone* zone,
1744                               FunctionLiteral* literal, Handle<Object> foreign,
1745                               AsmTyper* typer)
1746    : isolate_(isolate),
1747      zone_(zone),
1748      literal_(literal),
1749      foreign_(foreign),
1750      typer_(typer) {}
1751
1752// TODO(aseemgarg): probably should take zone (to write wasm to) as input so
1753// that zone in constructor may be thrown away once wasm module is written.
1754WasmModuleIndex* AsmWasmBuilder::Run() {
1755  AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_);
1756  impl.Compile();
1757  WasmModuleWriter* writer = impl.builder_->Build(zone_);
1758  return writer->WriteTo(zone_);
1759}
1760}  // namespace wasm
1761}  // namespace internal
1762}  // namespace v8
1763