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 #include "src/wasm/asm-wasm-builder.h"
8 #include "src/wasm/wasm-macro-gen.h"
9 #include "src/wasm/wasm-opcodes.h"
10 
11 #include "src/ast/ast.h"
12 #include "src/ast/scopes.h"
13 #include "src/codegen.h"
14 #include "src/type-cache.h"
15 
16 namespace v8 {
17 namespace internal {
18 namespace wasm {
19 
20 #define RECURSE(call)               \
21   do {                              \
22     DCHECK(!HasStackOverflow());    \
23     call;                           \
24     if (HasStackOverflow()) return; \
25   } while (false)
26 
27 
28 class AsmWasmBuilderImpl : public AstVisitor {
29  public:
AsmWasmBuilderImpl(Isolate * isolate,Zone * zone,FunctionLiteral * literal)30   AsmWasmBuilderImpl(Isolate* isolate, Zone* zone, FunctionLiteral* literal)
31       : local_variables_(HashMap::PointersMatch,
32                          ZoneHashMap::kDefaultHashMapCapacity,
33                          ZoneAllocationPolicy(zone)),
34         functions_(HashMap::PointersMatch, ZoneHashMap::kDefaultHashMapCapacity,
35                    ZoneAllocationPolicy(zone)),
36         global_variables_(HashMap::PointersMatch,
37                           ZoneHashMap::kDefaultHashMapCapacity,
38                           ZoneAllocationPolicy(zone)),
39         in_function_(false),
40         is_set_op_(false),
41         marking_exported(false),
42         builder_(new (zone) WasmModuleBuilder(zone)),
43         current_function_builder_(nullptr),
44         literal_(literal),
45         isolate_(isolate),
46         zone_(zone),
47         cache_(TypeCache::Get()),
48         breakable_blocks_(zone),
49         block_size_(0),
50         init_function_index(0) {
51     InitializeAstVisitor(isolate);
52   }
53 
InitializeInitFunction()54   void InitializeInitFunction() {
55     unsigned char init[] = "__init__";
56     init_function_index = builder_->AddFunction();
57     current_function_builder_ = builder_->FunctionAt(init_function_index);
58     current_function_builder_->SetName(init, 8);
59     current_function_builder_->ReturnType(kAstStmt);
60     current_function_builder_->Exported(1);
61     current_function_builder_ = nullptr;
62   }
63 
Compile()64   void Compile() {
65     InitializeInitFunction();
66     RECURSE(VisitFunctionLiteral(literal_));
67   }
68 
VisitVariableDeclaration(VariableDeclaration * decl)69   void VisitVariableDeclaration(VariableDeclaration* decl) {}
70 
VisitFunctionDeclaration(FunctionDeclaration * decl)71   void VisitFunctionDeclaration(FunctionDeclaration* decl) {
72     DCHECK(!in_function_);
73     DCHECK(current_function_builder_ == nullptr);
74     uint16_t index = LookupOrInsertFunction(decl->proxy()->var());
75     current_function_builder_ = builder_->FunctionAt(index);
76     in_function_ = true;
77     RECURSE(Visit(decl->fun()));
78     in_function_ = false;
79     current_function_builder_ = nullptr;
80     local_variables_.Clear();
81   }
82 
VisitImportDeclaration(ImportDeclaration * decl)83   void VisitImportDeclaration(ImportDeclaration* decl) {}
84 
VisitExportDeclaration(ExportDeclaration * decl)85   void VisitExportDeclaration(ExportDeclaration* decl) {}
86 
VisitStatements(ZoneList<Statement * > * stmts)87   void VisitStatements(ZoneList<Statement*>* stmts) {
88     for (int i = 0; i < stmts->length(); ++i) {
89       Statement* stmt = stmts->at(i);
90       RECURSE(Visit(stmt));
91       if (stmt->IsJump()) break;
92     }
93   }
94 
VisitBlock(Block * stmt)95   void VisitBlock(Block* stmt) {
96     if (stmt->statements()->length() == 1) {
97       ExpressionStatement* expr =
98           stmt->statements()->at(0)->AsExpressionStatement();
99       if (expr != nullptr) {
100         if (expr->expression()->IsAssignment()) {
101           RECURSE(VisitExpressionStatement(expr));
102           return;
103         }
104       }
105     }
106     DCHECK(in_function_);
107     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false,
108                          static_cast<byte>(stmt->statements()->length()));
109     RECURSE(VisitStatements(stmt->statements()));
110     DCHECK(block_size_ >= 0);
111   }
112 
113   class BlockVisitor {
114    private:
115     int prev_block_size_;
116     uint32_t index_;
117     AsmWasmBuilderImpl* builder_;
118 
119    public:
BlockVisitor(AsmWasmBuilderImpl * builder,BreakableStatement * stmt,WasmOpcode opcode,bool is_loop,int initial_block_size)120     BlockVisitor(AsmWasmBuilderImpl* builder, BreakableStatement* stmt,
121                  WasmOpcode opcode, bool is_loop, int initial_block_size)
122         : builder_(builder) {
123       builder_->breakable_blocks_.push_back(std::make_pair(stmt, is_loop));
124       builder_->current_function_builder_->Emit(opcode);
125       index_ = builder_->current_function_builder_->EmitEditableImmediate(0);
126       prev_block_size_ = builder_->block_size_;
127       builder_->block_size_ = initial_block_size;
128     }
~BlockVisitor()129     ~BlockVisitor() {
130       builder_->current_function_builder_->EditImmediate(index_,
131                                                          builder_->block_size_);
132       builder_->block_size_ = prev_block_size_;
133       builder_->breakable_blocks_.pop_back();
134     }
135   };
136 
VisitExpressionStatement(ExpressionStatement * stmt)137   void VisitExpressionStatement(ExpressionStatement* stmt) {
138     RECURSE(Visit(stmt->expression()));
139   }
140 
VisitEmptyStatement(EmptyStatement * stmt)141   void VisitEmptyStatement(EmptyStatement* stmt) {}
142 
VisitEmptyParentheses(EmptyParentheses * paren)143   void VisitEmptyParentheses(EmptyParentheses* paren) { UNREACHABLE(); }
144 
VisitIfStatement(IfStatement * stmt)145   void VisitIfStatement(IfStatement* stmt) {
146     DCHECK(in_function_);
147     if (stmt->HasElseStatement()) {
148       current_function_builder_->Emit(kExprIfElse);
149     } else {
150       current_function_builder_->Emit(kExprIf);
151     }
152     RECURSE(Visit(stmt->condition()));
153     if (stmt->HasThenStatement()) {
154       RECURSE(Visit(stmt->then_statement()));
155     } else {
156       current_function_builder_->Emit(kExprNop);
157     }
158     if (stmt->HasElseStatement()) {
159       RECURSE(Visit(stmt->else_statement()));
160     }
161   }
162 
VisitContinueStatement(ContinueStatement * stmt)163   void VisitContinueStatement(ContinueStatement* stmt) {
164     DCHECK(in_function_);
165     DCHECK(stmt->target() != NULL);
166     int i = static_cast<int>(breakable_blocks_.size()) - 1;
167     int block_distance = 0;
168     for (; i >= 0; i--) {
169       auto elem = breakable_blocks_.at(i);
170       if (elem.first == stmt->target()) {
171         DCHECK(elem.second);
172         break;
173       } else if (elem.second) {
174         block_distance += 2;
175       } else {
176         block_distance += 1;
177       }
178     }
179     DCHECK(i >= 0);
180     current_function_builder_->EmitWithU8(kExprBr, block_distance);
181     current_function_builder_->Emit(kExprNop);
182   }
183 
VisitBreakStatement(BreakStatement * stmt)184   void VisitBreakStatement(BreakStatement* stmt) {
185     DCHECK(in_function_);
186     DCHECK(stmt->target() != NULL);
187     int i = static_cast<int>(breakable_blocks_.size()) - 1;
188     int block_distance = 0;
189     for (; i >= 0; i--) {
190       auto elem = breakable_blocks_.at(i);
191       if (elem.first == stmt->target()) {
192         if (elem.second) {
193           block_distance++;
194         }
195         break;
196       } else if (elem.second) {
197         block_distance += 2;
198       } else {
199         block_distance += 1;
200       }
201     }
202     DCHECK(i >= 0);
203     current_function_builder_->EmitWithU8(kExprBr, block_distance);
204     current_function_builder_->Emit(kExprNop);
205   }
206 
VisitReturnStatement(ReturnStatement * stmt)207   void VisitReturnStatement(ReturnStatement* stmt) {
208     if (in_function_) {
209       current_function_builder_->Emit(kExprReturn);
210     } else {
211       marking_exported = true;
212     }
213     RECURSE(Visit(stmt->expression()));
214     if (!in_function_) {
215       marking_exported = false;
216     }
217   }
218 
VisitWithStatement(WithStatement * stmt)219   void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); }
220 
SetLocalTo(uint16_t index,int value)221   void SetLocalTo(uint16_t index, int value) {
222     current_function_builder_->Emit(kExprSetLocal);
223     AddLeb128(index, true);
224     byte code[] = {WASM_I32(value)};
225     current_function_builder_->EmitCode(code, sizeof(code));
226     block_size_++;
227   }
228 
CompileCase(CaseClause * clause,uint16_t fall_through,VariableProxy * tag)229   void CompileCase(CaseClause* clause, uint16_t fall_through,
230                    VariableProxy* tag) {
231     Literal* label = clause->label()->AsLiteral();
232     DCHECK(label != nullptr);
233     block_size_++;
234     current_function_builder_->Emit(kExprIf);
235     current_function_builder_->Emit(kExprI32Ior);
236     current_function_builder_->Emit(kExprI32Eq);
237     VisitVariableProxy(tag);
238     VisitLiteral(label);
239     current_function_builder_->Emit(kExprGetLocal);
240     AddLeb128(fall_through, true);
241     BlockVisitor visitor(this, nullptr, kExprBlock, false, 0);
242     SetLocalTo(fall_through, 1);
243     ZoneList<Statement*>* stmts = clause->statements();
244     block_size_ += stmts->length();
245     RECURSE(VisitStatements(stmts));
246   }
247 
VisitSwitchStatement(SwitchStatement * stmt)248   void VisitSwitchStatement(SwitchStatement* stmt) {
249     VariableProxy* tag = stmt->tag()->AsVariableProxy();
250     DCHECK(tag != NULL);
251     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false,
252                          0);
253     uint16_t fall_through = current_function_builder_->AddLocal(kAstI32);
254     SetLocalTo(fall_through, 0);
255 
256     ZoneList<CaseClause*>* clauses = stmt->cases();
257     for (int i = 0; i < clauses->length(); ++i) {
258       CaseClause* clause = clauses->at(i);
259       if (!clause->is_default()) {
260         CompileCase(clause, fall_through, tag);
261       } else {
262         ZoneList<Statement*>* stmts = clause->statements();
263         block_size_ += stmts->length();
264         RECURSE(VisitStatements(stmts));
265       }
266     }
267   }
268 
VisitCaseClause(CaseClause * clause)269   void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
270 
VisitDoWhileStatement(DoWhileStatement * stmt)271   void VisitDoWhileStatement(DoWhileStatement* stmt) {
272     DCHECK(in_function_);
273     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
274                          2);
275     RECURSE(Visit(stmt->body()));
276     current_function_builder_->Emit(kExprIf);
277     RECURSE(Visit(stmt->cond()));
278     current_function_builder_->EmitWithU8(kExprBr, 0);
279     current_function_builder_->Emit(kExprNop);
280   }
281 
VisitWhileStatement(WhileStatement * stmt)282   void VisitWhileStatement(WhileStatement* stmt) {
283     DCHECK(in_function_);
284     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
285                          1);
286     current_function_builder_->Emit(kExprIf);
287     RECURSE(Visit(stmt->cond()));
288     current_function_builder_->EmitWithU8(kExprBr, 0);
289     RECURSE(Visit(stmt->body()));
290   }
291 
VisitForStatement(ForStatement * stmt)292   void VisitForStatement(ForStatement* stmt) {
293     DCHECK(in_function_);
294     if (stmt->init() != nullptr) {
295       block_size_++;
296       RECURSE(Visit(stmt->init()));
297     }
298     BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
299                          0);
300     if (stmt->cond() != nullptr) {
301       block_size_++;
302       current_function_builder_->Emit(kExprIf);
303       current_function_builder_->Emit(kExprBoolNot);
304       RECURSE(Visit(stmt->cond()));
305       current_function_builder_->EmitWithU8(kExprBr, 1);
306       current_function_builder_->Emit(kExprNop);
307     }
308     if (stmt->body() != nullptr) {
309       block_size_++;
310       RECURSE(Visit(stmt->body()));
311     }
312     if (stmt->next() != nullptr) {
313       block_size_++;
314       RECURSE(Visit(stmt->next()));
315     }
316     block_size_++;
317     current_function_builder_->EmitWithU8(kExprBr, 0);
318     current_function_builder_->Emit(kExprNop);
319   }
320 
VisitForInStatement(ForInStatement * stmt)321   void VisitForInStatement(ForInStatement* stmt) { UNREACHABLE(); }
322 
VisitForOfStatement(ForOfStatement * stmt)323   void VisitForOfStatement(ForOfStatement* stmt) { UNREACHABLE(); }
324 
VisitTryCatchStatement(TryCatchStatement * stmt)325   void VisitTryCatchStatement(TryCatchStatement* stmt) { UNREACHABLE(); }
326 
VisitTryFinallyStatement(TryFinallyStatement * stmt)327   void VisitTryFinallyStatement(TryFinallyStatement* stmt) { UNREACHABLE(); }
328 
VisitDebuggerStatement(DebuggerStatement * stmt)329   void VisitDebuggerStatement(DebuggerStatement* stmt) { UNREACHABLE(); }
330 
VisitFunctionLiteral(FunctionLiteral * expr)331   void VisitFunctionLiteral(FunctionLiteral* expr) {
332     Scope* scope = expr->scope();
333     if (in_function_) {
334       if (expr->bounds().lower->IsFunction()) {
335         Type::FunctionType* func_type = expr->bounds().lower->AsFunction();
336         LocalType return_type = TypeFrom(func_type->Result());
337         current_function_builder_->ReturnType(return_type);
338         for (int i = 0; i < expr->parameter_count(); i++) {
339           LocalType type = TypeFrom(func_type->Parameter(i));
340           DCHECK(type != kAstStmt);
341           LookupOrInsertLocal(scope->parameter(i), type);
342         }
343       } else {
344         UNREACHABLE();
345       }
346     }
347     RECURSE(VisitDeclarations(scope->declarations()));
348     RECURSE(VisitStatements(expr->body()));
349   }
350 
VisitNativeFunctionLiteral(NativeFunctionLiteral * expr)351   void VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
352     UNREACHABLE();
353   }
354 
VisitConditional(Conditional * expr)355   void VisitConditional(Conditional* expr) {
356     DCHECK(in_function_);
357     current_function_builder_->Emit(kExprIfElse);
358     RECURSE(Visit(expr->condition()));
359     RECURSE(Visit(expr->then_expression()));
360     RECURSE(Visit(expr->else_expression()));
361   }
362 
VisitVariableProxy(VariableProxy * expr)363   void VisitVariableProxy(VariableProxy* expr) {
364     if (in_function_) {
365       Variable* var = expr->var();
366       if (var->is_function()) {
367         DCHECK(!is_set_op_);
368         std::vector<uint8_t> index =
369             UnsignedLEB128From(LookupOrInsertFunction(var));
370         current_function_builder_->EmitCode(
371             &index[0], static_cast<uint32_t>(index.size()));
372       } else {
373         if (is_set_op_) {
374           if (var->IsContextSlot()) {
375             current_function_builder_->Emit(kExprStoreGlobal);
376           } else {
377             current_function_builder_->Emit(kExprSetLocal);
378           }
379           is_set_op_ = false;
380         } else {
381           if (var->IsContextSlot()) {
382             current_function_builder_->Emit(kExprLoadGlobal);
383           } else {
384             current_function_builder_->Emit(kExprGetLocal);
385           }
386         }
387         LocalType var_type = TypeOf(expr);
388         DCHECK(var_type != kAstStmt);
389         if (var->IsContextSlot()) {
390           AddLeb128(LookupOrInsertGlobal(var, var_type), false);
391         } else {
392           AddLeb128(LookupOrInsertLocal(var, var_type), true);
393         }
394       }
395     }
396   }
397 
VisitLiteral(Literal * expr)398   void VisitLiteral(Literal* expr) {
399     if (in_function_) {
400       if (expr->raw_value()->IsNumber()) {
401         LocalType type = TypeOf(expr);
402         switch (type) {
403           case kAstI32: {
404             int val = static_cast<int>(expr->raw_value()->AsNumber());
405             byte code[] = {WASM_I32(val)};
406             current_function_builder_->EmitCode(code, sizeof(code));
407             break;
408           }
409           case kAstF32: {
410             float val = static_cast<float>(expr->raw_value()->AsNumber());
411             byte code[] = {WASM_F32(val)};
412             current_function_builder_->EmitCode(code, sizeof(code));
413             break;
414           }
415           case kAstF64: {
416             double val = static_cast<double>(expr->raw_value()->AsNumber());
417             byte code[] = {WASM_F64(val)};
418             current_function_builder_->EmitCode(code, sizeof(code));
419             break;
420           }
421           default:
422             UNREACHABLE();
423         }
424       }
425     }
426   }
427 
VisitRegExpLiteral(RegExpLiteral * expr)428   void VisitRegExpLiteral(RegExpLiteral* expr) { UNREACHABLE(); }
429 
VisitObjectLiteral(ObjectLiteral * expr)430   void VisitObjectLiteral(ObjectLiteral* expr) {
431     ZoneList<ObjectLiteralProperty*>* props = expr->properties();
432     for (int i = 0; i < props->length(); ++i) {
433       ObjectLiteralProperty* prop = props->at(i);
434       DCHECK(marking_exported);
435       VariableProxy* expr = prop->value()->AsVariableProxy();
436       DCHECK(expr != nullptr);
437       Variable* var = expr->var();
438       Literal* name = prop->key()->AsLiteral();
439       DCHECK(name != nullptr);
440       DCHECK(name->IsPropertyName());
441       const AstRawString* raw_name = name->AsRawPropertyName();
442       if (var->is_function()) {
443         uint16_t index = LookupOrInsertFunction(var);
444         builder_->FunctionAt(index)->Exported(1);
445         builder_->FunctionAt(index)
446             ->SetName(raw_name->raw_data(), raw_name->length());
447       }
448     }
449   }
450 
VisitArrayLiteral(ArrayLiteral * expr)451   void VisitArrayLiteral(ArrayLiteral* expr) { UNREACHABLE(); }
452 
LoadInitFunction()453   void LoadInitFunction() {
454     current_function_builder_ = builder_->FunctionAt(init_function_index);
455     in_function_ = true;
456   }
457 
UnLoadInitFunction()458   void UnLoadInitFunction() {
459     in_function_ = false;
460     current_function_builder_ = nullptr;
461   }
462 
VisitAssignment(Assignment * expr)463   void VisitAssignment(Assignment* expr) {
464     bool in_init = false;
465     if (!in_function_) {
466       // TODO(bradnelson): Get rid of this.
467       if (TypeOf(expr->value()) == kAstStmt) {
468         return;
469       }
470       in_init = true;
471       LoadInitFunction();
472     }
473     BinaryOperation* value_op = expr->value()->AsBinaryOperation();
474     if (value_op != nullptr && MatchBinaryOperation(value_op) == kAsIs) {
475       VariableProxy* target_var = expr->target()->AsVariableProxy();
476       VariableProxy* effective_value_var = GetLeft(value_op)->AsVariableProxy();
477       if (target_var != nullptr && effective_value_var != nullptr &&
478           target_var->var() == effective_value_var->var()) {
479         block_size_--;
480         return;
481       }
482     }
483     is_set_op_ = true;
484     RECURSE(Visit(expr->target()));
485     DCHECK(!is_set_op_);
486     RECURSE(Visit(expr->value()));
487     if (in_init) {
488       UnLoadInitFunction();
489     }
490   }
491 
VisitYield(Yield * expr)492   void VisitYield(Yield* expr) { UNREACHABLE(); }
493 
VisitThrow(Throw * expr)494   void VisitThrow(Throw* expr) { UNREACHABLE(); }
495 
VisitProperty(Property * expr)496   void VisitProperty(Property* expr) {
497     Expression* obj = expr->obj();
498     DCHECK(obj->bounds().lower == obj->bounds().upper);
499     TypeImpl<ZoneTypeConfig>* type = obj->bounds().lower;
500     MachineType mtype;
501     int size;
502     if (type->Is(cache_.kUint8Array)) {
503       mtype = MachineType::Uint8();
504       size = 1;
505     } else if (type->Is(cache_.kInt8Array)) {
506       mtype = MachineType::Int8();
507       size = 1;
508     } else if (type->Is(cache_.kUint16Array)) {
509       mtype = MachineType::Uint16();
510       size = 2;
511     } else if (type->Is(cache_.kInt16Array)) {
512       mtype = MachineType::Int16();
513       size = 2;
514     } else if (type->Is(cache_.kUint32Array)) {
515       mtype = MachineType::Uint32();
516       size = 4;
517     } else if (type->Is(cache_.kInt32Array)) {
518       mtype = MachineType::Int32();
519       size = 4;
520     } else if (type->Is(cache_.kUint32Array)) {
521       mtype = MachineType::Uint32();
522       size = 4;
523     } else if (type->Is(cache_.kFloat32Array)) {
524       mtype = MachineType::Float32();
525       size = 4;
526     } else if (type->Is(cache_.kFloat64Array)) {
527       mtype = MachineType::Float64();
528       size = 8;
529     } else {
530       UNREACHABLE();
531     }
532     current_function_builder_->EmitWithU8(
533         WasmOpcodes::LoadStoreOpcodeOf(mtype, is_set_op_),
534         WasmOpcodes::LoadStoreAccessOf(false));
535     is_set_op_ = false;
536     Literal* value = expr->key()->AsLiteral();
537     if (value) {
538       DCHECK(value->raw_value()->IsNumber());
539       DCHECK(kAstI32 == TypeOf(value));
540       int val = static_cast<int>(value->raw_value()->AsNumber());
541       byte code[] = {WASM_I32(val * size)};
542       current_function_builder_->EmitCode(code, sizeof(code));
543       return;
544     }
545     BinaryOperation* binop = expr->key()->AsBinaryOperation();
546     if (binop) {
547       DCHECK(Token::SAR == binop->op());
548       DCHECK(binop->right()->AsLiteral()->raw_value()->IsNumber());
549       DCHECK(kAstI32 == TypeOf(binop->right()->AsLiteral()));
550       DCHECK(size ==
551              1 << static_cast<int>(
552                  binop->right()->AsLiteral()->raw_value()->AsNumber()));
553       // Mask bottom bits to match asm.js behavior.
554       current_function_builder_->Emit(kExprI32And);
555       byte code[] = {WASM_I8(~(size - 1))};
556       current_function_builder_->EmitCode(code, sizeof(code));
557       RECURSE(Visit(binop->left()));
558       return;
559     }
560     UNREACHABLE();
561   }
562 
VisitCall(Call * expr)563   void VisitCall(Call* expr) {
564     Call::CallType call_type = expr->GetCallType(isolate_);
565     switch (call_type) {
566       case Call::OTHER_CALL: {
567         DCHECK(in_function_);
568         current_function_builder_->Emit(kExprCallFunction);
569         RECURSE(Visit(expr->expression()));
570         ZoneList<Expression*>* args = expr->arguments();
571         for (int i = 0; i < args->length(); ++i) {
572           Expression* arg = args->at(i);
573           RECURSE(Visit(arg));
574         }
575         break;
576       }
577       default:
578         UNREACHABLE();
579     }
580   }
581 
VisitCallNew(CallNew * expr)582   void VisitCallNew(CallNew* expr) { UNREACHABLE(); }
583 
VisitCallRuntime(CallRuntime * expr)584   void VisitCallRuntime(CallRuntime* expr) { UNREACHABLE(); }
585 
VisitUnaryOperation(UnaryOperation * expr)586   void VisitUnaryOperation(UnaryOperation* expr) {
587     switch (expr->op()) {
588       case Token::NOT: {
589         DCHECK(TypeOf(expr->expression()) == kAstI32);
590         current_function_builder_->Emit(kExprBoolNot);
591         break;
592       }
593       default:
594         UNREACHABLE();
595     }
596     RECURSE(Visit(expr->expression()));
597   }
598 
VisitCountOperation(CountOperation * expr)599   void VisitCountOperation(CountOperation* expr) { UNREACHABLE(); }
600 
MatchIntBinaryOperation(BinaryOperation * expr,Token::Value op,int32_t val)601   bool MatchIntBinaryOperation(BinaryOperation* expr, Token::Value op,
602                                int32_t val) {
603     DCHECK(expr->right() != nullptr);
604     if (expr->op() == op && expr->right()->IsLiteral() &&
605         TypeOf(expr) == kAstI32) {
606       Literal* right = expr->right()->AsLiteral();
607       DCHECK(right->raw_value()->IsNumber());
608       if (static_cast<int32_t>(right->raw_value()->AsNumber()) == val) {
609         return true;
610       }
611     }
612     return false;
613   }
614 
MatchDoubleBinaryOperation(BinaryOperation * expr,Token::Value op,double val)615   bool MatchDoubleBinaryOperation(BinaryOperation* expr, Token::Value op,
616                                   double val) {
617     DCHECK(expr->right() != nullptr);
618     if (expr->op() == op && expr->right()->IsLiteral() &&
619         TypeOf(expr) == kAstF64) {
620       Literal* right = expr->right()->AsLiteral();
621       DCHECK(right->raw_value()->IsNumber());
622       if (right->raw_value()->AsNumber() == val) {
623         return true;
624       }
625     }
626     return false;
627   }
628 
629   enum ConvertOperation { kNone, kAsIs, kToInt, kToDouble };
630 
MatchOr(BinaryOperation * expr)631   ConvertOperation MatchOr(BinaryOperation* expr) {
632     if (MatchIntBinaryOperation(expr, Token::BIT_OR, 0)) {
633       return (TypeOf(expr->left()) == kAstI32) ? kAsIs : kToInt;
634     } else {
635       return kNone;
636     }
637   }
638 
MatchShr(BinaryOperation * expr)639   ConvertOperation MatchShr(BinaryOperation* expr) {
640     if (MatchIntBinaryOperation(expr, Token::SHR, 0)) {
641       // TODO(titzer): this probably needs to be kToUint
642       return (TypeOf(expr->left()) == kAstI32) ? kAsIs : kToInt;
643     } else {
644       return kNone;
645     }
646   }
647 
MatchXor(BinaryOperation * expr)648   ConvertOperation MatchXor(BinaryOperation* expr) {
649     if (MatchIntBinaryOperation(expr, Token::BIT_XOR, 0xffffffff)) {
650       DCHECK(TypeOf(expr->left()) == kAstI32);
651       DCHECK(TypeOf(expr->right()) == kAstI32);
652       BinaryOperation* op = expr->left()->AsBinaryOperation();
653       if (op != nullptr) {
654         if (MatchIntBinaryOperation(op, Token::BIT_XOR, 0xffffffff)) {
655           DCHECK(TypeOf(op->right()) == kAstI32);
656           if (TypeOf(op->left()) != kAstI32) {
657             return kToInt;
658           } else {
659             return kAsIs;
660           }
661         }
662       }
663     }
664     return kNone;
665   }
666 
MatchMul(BinaryOperation * expr)667   ConvertOperation MatchMul(BinaryOperation* expr) {
668     if (MatchDoubleBinaryOperation(expr, Token::MUL, 1.0)) {
669       DCHECK(TypeOf(expr->right()) == kAstF64);
670       if (TypeOf(expr->left()) != kAstF64) {
671         return kToDouble;
672       } else {
673         return kAsIs;
674       }
675     } else {
676       return kNone;
677     }
678   }
679 
MatchBinaryOperation(BinaryOperation * expr)680   ConvertOperation MatchBinaryOperation(BinaryOperation* expr) {
681     switch (expr->op()) {
682       case Token::BIT_OR:
683         return MatchOr(expr);
684       case Token::SHR:
685         return MatchShr(expr);
686       case Token::BIT_XOR:
687         return MatchXor(expr);
688       case Token::MUL:
689         return MatchMul(expr);
690       default:
691         return kNone;
692     }
693   }
694 
695 // Work around Mul + Div being defined in PPC assembler.
696 #ifdef Mul
697 #undef Mul
698 #endif
699 #ifdef Div
700 #undef Div
701 #endif
702 
703 #define NON_SIGNED_BINOP(op)      \
704   static WasmOpcode opcodes[] = { \
705     kExprI32##op,                 \
706     kExprI32##op,                 \
707     kExprF32##op,                 \
708     kExprF64##op                  \
709   }
710 
711 #define SIGNED_BINOP(op)          \
712   static WasmOpcode opcodes[] = { \
713     kExprI32##op##S,              \
714     kExprI32##op##U,              \
715     kExprF32##op,                 \
716     kExprF64##op                  \
717   }
718 
719 #define NON_SIGNED_INT_BINOP(op) \
720   static WasmOpcode opcodes[] = { kExprI32##op, kExprI32##op }
721 
722 #define BINOP_CASE(token, op, V, ignore_sign)                         \
723   case token: {                                                       \
724     V(op);                                                            \
725     int type = TypeIndexOf(expr->left(), expr->right(), ignore_sign); \
726     current_function_builder_->Emit(opcodes[type]);                   \
727     break;                                                            \
728   }
729 
GetLeft(BinaryOperation * expr)730   Expression* GetLeft(BinaryOperation* expr) {
731     if (expr->op() == Token::BIT_XOR) {
732       return expr->left()->AsBinaryOperation()->left();
733     } else {
734       return expr->left();
735     }
736   }
737 
VisitBinaryOperation(BinaryOperation * expr)738   void VisitBinaryOperation(BinaryOperation* expr) {
739     ConvertOperation convertOperation = MatchBinaryOperation(expr);
740     if (convertOperation == kToDouble) {
741       TypeIndex type = TypeIndexOf(expr->left());
742       if (type == kInt32 || type == kFixnum) {
743         current_function_builder_->Emit(kExprF64SConvertI32);
744       } else if (type == kUint32) {
745         current_function_builder_->Emit(kExprF64UConvertI32);
746       } else if (type == kFloat32) {
747         current_function_builder_->Emit(kExprF64ConvertF32);
748       } else {
749         UNREACHABLE();
750       }
751       RECURSE(Visit(expr->left()));
752     } else if (convertOperation == kToInt) {
753       TypeIndex type = TypeIndexOf(GetLeft(expr));
754       if (type == kFloat32) {
755         current_function_builder_->Emit(kExprI32SConvertF32);
756       } else if (type == kFloat64) {
757         current_function_builder_->Emit(kExprI32SConvertF64);
758       } else {
759         UNREACHABLE();
760       }
761       RECURSE(Visit(GetLeft(expr)));
762     } else if (convertOperation == kAsIs) {
763       RECURSE(Visit(GetLeft(expr)));
764     } else {
765       switch (expr->op()) {
766         BINOP_CASE(Token::ADD, Add, NON_SIGNED_BINOP, true);
767         BINOP_CASE(Token::SUB, Sub, NON_SIGNED_BINOP, true);
768         BINOP_CASE(Token::MUL, Mul, NON_SIGNED_BINOP, true);
769         BINOP_CASE(Token::DIV, Div, SIGNED_BINOP, false);
770         BINOP_CASE(Token::BIT_OR, Ior, NON_SIGNED_INT_BINOP, true);
771         BINOP_CASE(Token::BIT_XOR, Xor, NON_SIGNED_INT_BINOP, true);
772         BINOP_CASE(Token::SHL, Shl, NON_SIGNED_INT_BINOP, true);
773         BINOP_CASE(Token::SAR, ShrS, NON_SIGNED_INT_BINOP, true);
774         BINOP_CASE(Token::SHR, ShrU, NON_SIGNED_INT_BINOP, true);
775         case Token::MOD: {
776           TypeIndex type = TypeIndexOf(expr->left(), expr->right(), false);
777           if (type == kInt32) {
778             current_function_builder_->Emit(kExprI32RemS);
779           } else if (type == kUint32) {
780             current_function_builder_->Emit(kExprI32RemU);
781           } else if (type == kFloat64) {
782             ModF64(expr);
783             return;
784           } else {
785             UNREACHABLE();
786           }
787           break;
788         }
789         default:
790           UNREACHABLE();
791       }
792       RECURSE(Visit(expr->left()));
793       RECURSE(Visit(expr->right()));
794     }
795   }
796 
ModF64(BinaryOperation * expr)797   void ModF64(BinaryOperation* expr) {
798     current_function_builder_->EmitWithU8(kExprBlock, 3);
799     uint16_t index_0 = current_function_builder_->AddLocal(kAstF64);
800     uint16_t index_1 = current_function_builder_->AddLocal(kAstF64);
801     current_function_builder_->Emit(kExprSetLocal);
802     AddLeb128(index_0, true);
803     RECURSE(Visit(expr->left()));
804     current_function_builder_->Emit(kExprSetLocal);
805     AddLeb128(index_1, true);
806     RECURSE(Visit(expr->right()));
807     current_function_builder_->Emit(kExprF64Sub);
808     current_function_builder_->Emit(kExprGetLocal);
809     AddLeb128(index_0, true);
810     current_function_builder_->Emit(kExprF64Mul);
811     current_function_builder_->Emit(kExprGetLocal);
812     AddLeb128(index_1, true);
813     // Use trunc instead of two casts
814     current_function_builder_->Emit(kExprF64SConvertI32);
815     current_function_builder_->Emit(kExprI32SConvertF64);
816     current_function_builder_->Emit(kExprF64Div);
817     current_function_builder_->Emit(kExprGetLocal);
818     AddLeb128(index_0, true);
819     current_function_builder_->Emit(kExprGetLocal);
820     AddLeb128(index_1, true);
821   }
822 
AddLeb128(uint32_t index,bool is_local)823   void AddLeb128(uint32_t index, bool is_local) {
824     std::vector<uint8_t> index_vec = UnsignedLEB128From(index);
825     if (is_local) {
826       uint32_t pos_of_index[1] = {0};
827       current_function_builder_->EmitCode(
828           &index_vec[0], static_cast<uint32_t>(index_vec.size()), pos_of_index,
829           1);
830     } else {
831       current_function_builder_->EmitCode(
832           &index_vec[0], static_cast<uint32_t>(index_vec.size()));
833     }
834   }
835 
VisitCompareOperation(CompareOperation * expr)836   void VisitCompareOperation(CompareOperation* expr) {
837     switch (expr->op()) {
838       BINOP_CASE(Token::EQ, Eq, NON_SIGNED_BINOP, false);
839       BINOP_CASE(Token::LT, Lt, SIGNED_BINOP, false);
840       BINOP_CASE(Token::LTE, Le, SIGNED_BINOP, false);
841       BINOP_CASE(Token::GT, Gt, SIGNED_BINOP, false);
842       BINOP_CASE(Token::GTE, Ge, SIGNED_BINOP, false);
843       default:
844         UNREACHABLE();
845     }
846     RECURSE(Visit(expr->left()));
847     RECURSE(Visit(expr->right()));
848   }
849 
850 #undef BINOP_CASE
851 #undef NON_SIGNED_INT_BINOP
852 #undef SIGNED_BINOP
853 #undef NON_SIGNED_BINOP
854 
855   enum TypeIndex {
856     kInt32 = 0,
857     kUint32 = 1,
858     kFloat32 = 2,
859     kFloat64 = 3,
860     kFixnum = 4
861   };
862 
TypeIndexOf(Expression * left,Expression * right,bool ignore_sign)863   TypeIndex TypeIndexOf(Expression* left, Expression* right, bool ignore_sign) {
864     TypeIndex left_index = TypeIndexOf(left);
865     TypeIndex right_index = TypeIndexOf(right);
866     if (left_index == kFixnum) {
867       left_index = right_index;
868     }
869     if (right_index == kFixnum) {
870       right_index = left_index;
871     }
872     if (left_index == kFixnum && right_index == kFixnum) {
873       left_index = kInt32;
874       right_index = kInt32;
875     }
876     DCHECK((left_index == right_index) ||
877            (ignore_sign && (left_index <= 1) && (right_index <= 1)));
878     return left_index;
879   }
880 
TypeIndexOf(Expression * expr)881   TypeIndex TypeIndexOf(Expression* expr) {
882     DCHECK(expr->bounds().lower == expr->bounds().upper);
883     TypeImpl<ZoneTypeConfig>* type = expr->bounds().lower;
884     if (type->Is(cache_.kAsmFixnum)) {
885       return kFixnum;
886     } else if (type->Is(cache_.kAsmSigned)) {
887       return kInt32;
888     } else if (type->Is(cache_.kAsmUnsigned)) {
889       return kUint32;
890     } else if (type->Is(cache_.kAsmInt)) {
891       return kInt32;
892     } else if (type->Is(cache_.kAsmFloat)) {
893       return kFloat32;
894     } else if (type->Is(cache_.kAsmDouble)) {
895       return kFloat64;
896     } else {
897       UNREACHABLE();
898       return kInt32;
899     }
900   }
901 
902 #undef CASE
903 #undef NON_SIGNED_INT
904 #undef SIGNED
905 #undef NON_SIGNED
906 
VisitThisFunction(ThisFunction * expr)907   void VisitThisFunction(ThisFunction* expr) { UNREACHABLE(); }
908 
VisitDeclarations(ZoneList<Declaration * > * decls)909   void VisitDeclarations(ZoneList<Declaration*>* decls) {
910     for (int i = 0; i < decls->length(); ++i) {
911       Declaration* decl = decls->at(i);
912       RECURSE(Visit(decl));
913     }
914   }
915 
VisitClassLiteral(ClassLiteral * expr)916   void VisitClassLiteral(ClassLiteral* expr) { UNREACHABLE(); }
917 
VisitSpread(Spread * expr)918   void VisitSpread(Spread* expr) { UNREACHABLE(); }
919 
VisitSuperPropertyReference(SuperPropertyReference * expr)920   void VisitSuperPropertyReference(SuperPropertyReference* expr) {
921     UNREACHABLE();
922   }
923 
VisitSuperCallReference(SuperCallReference * expr)924   void VisitSuperCallReference(SuperCallReference* expr) { UNREACHABLE(); }
925 
VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement * expr)926   void VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement* expr) {
927     UNREACHABLE();
928   }
929 
VisitDoExpression(DoExpression * expr)930   void VisitDoExpression(DoExpression* expr) { UNREACHABLE(); }
931 
VisitRewritableAssignmentExpression(RewritableAssignmentExpression * expr)932   void VisitRewritableAssignmentExpression(
933       RewritableAssignmentExpression* expr) {
934     UNREACHABLE();
935   }
936 
937   struct IndexContainer : public ZoneObject {
938     uint16_t index;
939   };
940 
LookupOrInsertLocal(Variable * v,LocalType type)941   uint16_t LookupOrInsertLocal(Variable* v, LocalType type) {
942     DCHECK(current_function_builder_ != nullptr);
943     ZoneHashMap::Entry* entry =
944         local_variables_.Lookup(v, ComputePointerHash(v));
945     if (entry == nullptr) {
946       uint16_t index;
947       if (v->IsParameter()) {
948         index = current_function_builder_->AddParam(type);
949       } else {
950         index = current_function_builder_->AddLocal(type);
951       }
952       IndexContainer* container = new (zone()) IndexContainer();
953       container->index = index;
954       entry = local_variables_.LookupOrInsert(v, ComputePointerHash(v),
955                                               ZoneAllocationPolicy(zone()));
956       entry->value = container;
957     }
958     return (reinterpret_cast<IndexContainer*>(entry->value))->index;
959   }
960 
LookupOrInsertGlobal(Variable * v,LocalType type)961   uint16_t LookupOrInsertGlobal(Variable* v, LocalType type) {
962     ZoneHashMap::Entry* entry =
963         global_variables_.Lookup(v, ComputePointerHash(v));
964     if (entry == nullptr) {
965       uint16_t index =
966           builder_->AddGlobal(WasmOpcodes::MachineTypeFor(type), 0);
967       IndexContainer* container = new (zone()) IndexContainer();
968       container->index = index;
969       entry = global_variables_.LookupOrInsert(v, ComputePointerHash(v),
970                                                ZoneAllocationPolicy(zone()));
971       entry->value = container;
972     }
973     return (reinterpret_cast<IndexContainer*>(entry->value))->index;
974   }
975 
LookupOrInsertFunction(Variable * v)976   uint16_t LookupOrInsertFunction(Variable* v) {
977     DCHECK(builder_ != nullptr);
978     ZoneHashMap::Entry* entry = functions_.Lookup(v, ComputePointerHash(v));
979     if (entry == nullptr) {
980       uint16_t index = builder_->AddFunction();
981       IndexContainer* container = new (zone()) IndexContainer();
982       container->index = index;
983       entry = functions_.LookupOrInsert(v, ComputePointerHash(v),
984                                         ZoneAllocationPolicy(zone()));
985       entry->value = container;
986     }
987     return (reinterpret_cast<IndexContainer*>(entry->value))->index;
988   }
989 
TypeOf(Expression * expr)990   LocalType TypeOf(Expression* expr) {
991     DCHECK(expr->bounds().lower == expr->bounds().upper);
992     return TypeFrom(expr->bounds().lower);
993   }
994 
TypeFrom(TypeImpl<ZoneTypeConfig> * type)995   LocalType TypeFrom(TypeImpl<ZoneTypeConfig>* type) {
996     if (type->Is(cache_.kAsmInt)) {
997       return kAstI32;
998     } else if (type->Is(cache_.kAsmFloat)) {
999       return kAstF32;
1000     } else if (type->Is(cache_.kAsmDouble)) {
1001       return kAstF64;
1002     } else {
1003       return kAstStmt;
1004     }
1005   }
1006 
zone()1007   Zone* zone() { return zone_; }
1008 
1009   ZoneHashMap local_variables_;
1010   ZoneHashMap functions_;
1011   ZoneHashMap global_variables_;
1012   bool in_function_;
1013   bool is_set_op_;
1014   bool marking_exported;
1015   WasmModuleBuilder* builder_;
1016   WasmFunctionBuilder* current_function_builder_;
1017   FunctionLiteral* literal_;
1018   Isolate* isolate_;
1019   Zone* zone_;
1020   TypeCache const& cache_;
1021   ZoneVector<std::pair<BreakableStatement*, bool>> breakable_blocks_;
1022   int block_size_;
1023   uint16_t init_function_index;
1024 
1025   DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
1026 
1027  private:
1028   DISALLOW_COPY_AND_ASSIGN(AsmWasmBuilderImpl);
1029 };
1030 
AsmWasmBuilder(Isolate * isolate,Zone * zone,FunctionLiteral * literal)1031 AsmWasmBuilder::AsmWasmBuilder(Isolate* isolate, Zone* zone,
1032                                FunctionLiteral* literal)
1033     : isolate_(isolate), zone_(zone), literal_(literal) {}
1034 
1035 // TODO(aseemgarg): probably should take zone (to write wasm to) as input so
1036 // that zone in constructor may be thrown away once wasm module is written.
Run()1037 WasmModuleIndex* AsmWasmBuilder::Run() {
1038   AsmWasmBuilderImpl impl(isolate_, zone_, literal_);
1039   impl.Compile();
1040   WasmModuleWriter* writer = impl.builder_->Build(zone_);
1041   return writer->WriteTo(zone_);
1042 }
1043 }  // namespace wasm
1044 }  // namespace internal
1045 }  // namespace v8
1046