Home | History | Annotate | Download | only in wasm 
      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:
     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 
     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 
     64   void Compile() {
     65     InitializeInitFunction();
     66     RECURSE(VisitFunctionLiteral(literal_));
     67   }
     68 
     69   void VisitVariableDeclaration(VariableDeclaration* decl) {}
     70 
     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 
     83   void VisitImportDeclaration(ImportDeclaration* decl) {}
     84 
     85   void VisitExportDeclaration(ExportDeclaration* decl) {}
     86 
     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 
     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:
    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     }
    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 
    137   void VisitExpressionStatement(ExpressionStatement* stmt) {
    138     RECURSE(Visit(stmt->expression()));
    139   }
    140 
    141   void VisitEmptyStatement(EmptyStatement* stmt) {}
    142 
    143   void VisitEmptyParentheses(EmptyParentheses* paren) { UNREACHABLE(); }
    144 
    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 
    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 
    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 
    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 
    219   void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); }
    220 
    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 
    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 
    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 
    269   void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
    270 
    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 
    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 
    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 
    321   void VisitForInStatement(ForInStatement* stmt) { UNREACHABLE(); }
    322 
    323   void VisitForOfStatement(ForOfStatement* stmt) { UNREACHABLE(); }
    324 
    325   void VisitTryCatchStatement(TryCatchStatement* stmt) { UNREACHABLE(); }
    326 
    327   void VisitTryFinallyStatement(TryFinallyStatement* stmt) { UNREACHABLE(); }
    328 
    329   void VisitDebuggerStatement(DebuggerStatement* stmt) { UNREACHABLE(); }
    330 
    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 
    351   void VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
    352     UNREACHABLE();
    353   }
    354 
    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 
    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 
    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 
    428   void VisitRegExpLiteral(RegExpLiteral* expr) { UNREACHABLE(); }
    429 
    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 
    451   void VisitArrayLiteral(ArrayLiteral* expr) { UNREACHABLE(); }
    452 
    453   void LoadInitFunction() {
    454     current_function_builder_ = builder_->FunctionAt(init_function_index);
    455     in_function_ = true;
    456   }
    457 
    458   void UnLoadInitFunction() {
    459     in_function_ = false;
    460     current_function_builder_ = nullptr;
    461   }
    462 
    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 
    492   void VisitYield(Yield* expr) { UNREACHABLE(); }
    493 
    494   void VisitThrow(Throw* expr) { UNREACHABLE(); }
    495 
    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 
    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 
    582   void VisitCallNew(CallNew* expr) { UNREACHABLE(); }
    583 
    584   void VisitCallRuntime(CallRuntime* expr) { UNREACHABLE(); }
    585 
    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 
    599   void VisitCountOperation(CountOperation* expr) { UNREACHABLE(); }
    600 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    907   void VisitThisFunction(ThisFunction* expr) { UNREACHABLE(); }
    908 
    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 
    916   void VisitClassLiteral(ClassLiteral* expr) { UNREACHABLE(); }
    917 
    918   void VisitSpread(Spread* expr) { UNREACHABLE(); }
    919 
    920   void VisitSuperPropertyReference(SuperPropertyReference* expr) {
    921     UNREACHABLE();
    922   }
    923 
    924   void VisitSuperCallReference(SuperCallReference* expr) { UNREACHABLE(); }
    925 
    926   void VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement* expr) {
    927     UNREACHABLE();
    928   }
    929 
    930   void VisitDoExpression(DoExpression* expr) { UNREACHABLE(); }
    931 
    932   void VisitRewritableAssignmentExpression(
    933       RewritableAssignmentExpression* expr) {
    934     UNREACHABLE();
    935   }
    936 
    937   struct IndexContainer : public ZoneObject {
    938     uint16_t index;
    939   };
    940 
    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 
    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 
    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 
    990   LocalType TypeOf(Expression* expr) {
    991     DCHECK(expr->bounds().lower == expr->bounds().upper);
    992     return TypeFrom(expr->bounds().lower);
    993   }
    994 
    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 
   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 
   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.
   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