Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1041)

Side by Side Diff: src/wasm/asm-wasm-builder.cc

Issue 1838973002: optimized switch implementation (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 4 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2015 the V8 project authors. All rights reserved. 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 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "src/v8.h" 5 #include "src/v8.h"
6 6
7 // Required to get M_E etc. in MSVC. 7 // Required to get M_E etc. in MSVC.
8 #if defined(_WIN32) 8 #if defined(_WIN32)
9 #define _USE_MATH_DEFINES 9 #define _USE_MATH_DEFINES
10 #endif 10 #endif
11 #include <math.h> 11 #include <math.h>
12 12
13 #include "src/wasm/asm-wasm-builder.h" 13 #include "src/wasm/asm-wasm-builder.h"
14 #include "src/wasm/switch-logic.h"
14 #include "src/wasm/wasm-macro-gen.h" 15 #include "src/wasm/wasm-macro-gen.h"
15 #include "src/wasm/wasm-opcodes.h" 16 #include "src/wasm/wasm-opcodes.h"
16 17
17 #include "src/ast/ast.h" 18 #include "src/ast/ast.h"
18 #include "src/ast/scopes.h" 19 #include "src/ast/scopes.h"
19 #include "src/codegen.h" 20 #include "src/codegen.h"
20 #include "src/type-cache.h" 21 #include "src/type-cache.h"
21 22
22 namespace v8 { 23 namespace v8 {
23 namespace internal { 24 namespace internal {
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after
92 local_variables_.Clear(); 93 local_variables_.Clear();
93 } 94 }
94 95
95 void VisitImportDeclaration(ImportDeclaration* decl) {} 96 void VisitImportDeclaration(ImportDeclaration* decl) {}
96 97
97 void VisitExportDeclaration(ExportDeclaration* decl) {} 98 void VisitExportDeclaration(ExportDeclaration* decl) {}
98 99
99 void VisitStatements(ZoneList<Statement*>* stmts) { 100 void VisitStatements(ZoneList<Statement*>* stmts) {
100 for (int i = 0; i < stmts->length(); ++i) { 101 for (int i = 0; i < stmts->length(); ++i) {
101 Statement* stmt = stmts->at(i); 102 Statement* stmt = stmts->at(i);
103 ExpressionStatement* e = stmt->AsExpressionStatement();
104 if (e != nullptr && e->expression()->IsUndefinedLiteral()) {
105 block_size_--;
106 continue;
107 }
102 RECURSE(Visit(stmt)); 108 RECURSE(Visit(stmt));
103 if (stmt->IsJump()) break; 109 if (stmt->IsJump()) break;
104 } 110 }
105 } 111 }
106 112
107 void VisitBlock(Block* stmt) { 113 void VisitBlock(Block* stmt) {
108 if (stmt->statements()->length() == 1) { 114 if (stmt->statements()->length() == 1) {
109 ExpressionStatement* expr = 115 ExpressionStatement* expr =
110 stmt->statements()->at(0)->AsExpressionStatement(); 116 stmt->statements()->at(0)->AsExpressionStatement();
111 if (expr != nullptr) { 117 if (expr != nullptr) {
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after
228 marking_exported = true; 234 marking_exported = true;
229 } 235 }
230 RECURSE(Visit(stmt->expression())); 236 RECURSE(Visit(stmt->expression()));
231 if (!in_function_) { 237 if (!in_function_) {
232 marking_exported = false; 238 marking_exported = false;
233 } 239 }
234 } 240 }
235 241
236 void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); } 242 void VisitWithStatement(WithStatement* stmt) { UNREACHABLE(); }
237 243
238 void SetLocalTo(uint16_t index, int value) { 244 void GenerateCaseComparisonCode(int value, WasmOpcode op,
239 current_function_builder_->Emit(kExprSetLocal); 245 VariableProxy* tag) {
240 AddLeb128(index, true); 246 current_function_builder_->Emit(kExprIfElse);
241 // TODO(bradnelson): variable size 247 current_function_builder_->Emit(op);
248 VisitVariableProxy(tag);
242 byte code[] = {WASM_I32V(value)}; 249 byte code[] = {WASM_I32V(value)};
243 current_function_builder_->EmitCode(code, sizeof(code)); 250 current_function_builder_->EmitCode(code, sizeof(code));
244 block_size_++;
245 } 251 }
246 252
247 void CompileCase(CaseClause* clause, uint16_t fall_through, 253 void HandleCase(CaseNode* node,
248 VariableProxy* tag) { 254 const ZoneMap<int, unsigned int>& case_to_block,
249 Literal* label = clause->label()->AsLiteral(); 255 VariableProxy* tag, int default_block) {
250 DCHECK_NOT_NULL(label); 256 if (node->left_ != nullptr) {
251 block_size_++; 257 GenerateCaseComparisonCode(node->begin_, kExprI32LtS, tag);
252 current_function_builder_->Emit(kExprIf); 258 HandleCase(node->left_, case_to_block, tag, default_block);
253 current_function_builder_->Emit(kExprI32Ior); 259 }
254 current_function_builder_->Emit(kExprI32Eq); 260 if (node->right_ != nullptr) {
255 VisitVariableProxy(tag); 261 GenerateCaseComparisonCode(node->end_, kExprI32GtS, tag);
256 VisitLiteral(label); 262 HandleCase(node->right_, case_to_block, tag, default_block);
257 current_function_builder_->Emit(kExprGetLocal); 263 }
258 AddLeb128(fall_through, true); 264 if (node->begin_ == node->end_) {
259 BlockVisitor visitor(this, nullptr, kExprBlock, false, 0); 265 current_function_builder_->Emit(kExprIf);
260 SetLocalTo(fall_through, 1); 266 current_function_builder_->Emit(kExprI32Eq);
261 ZoneList<Statement*>* stmts = clause->statements(); 267 VisitVariableProxy(tag);
262 block_size_ += stmts->length(); 268 byte code[] = {WASM_I32V(node->begin_)};
263 RECURSE(VisitStatements(stmts)); 269 current_function_builder_->EmitCode(code, sizeof(code));
270 DCHECK(case_to_block.find(node->begin_) != case_to_block.end());
271 current_function_builder_->EmitWithVarInt(kExprBr,
272 case_to_block.at(node->begin_));
273 current_function_builder_->Emit(kExprNop);
274 } else {
275 current_function_builder_->Emit(kExprBrTable);
276 byte count[] = {U32V_1(node->end_ - node->begin_ + 1)};
277 current_function_builder_->EmitCode(count, sizeof(count));
278 for (int v = node->begin_; v <= node->end_; v++) {
279 if (case_to_block.find(v) != case_to_block.end()) {
280 byte break_code[] = {BR_TARGET(case_to_block.at(v))};
281 current_function_builder_->EmitCode(break_code, sizeof(break_code));
282 } else {
283 byte break_code[] = {BR_TARGET(default_block)};
284 current_function_builder_->EmitCode(break_code, sizeof(break_code));
285 }
286 }
287 byte break_code[] = {BR_TARGET(default_block)};
288 current_function_builder_->EmitCode(break_code, sizeof(break_code));
289 current_function_builder_->Emit(kExprI32Sub);
290 VisitVariableProxy(tag);
291 byte code[] = {WASM_I32V(node->begin_)};
292 current_function_builder_->EmitCode(code, sizeof(code));
293 }
264 } 294 }
265 295
266 void VisitSwitchStatement(SwitchStatement* stmt) { 296 void VisitSwitchStatement(SwitchStatement* stmt) {
267 VariableProxy* tag = stmt->tag()->AsVariableProxy(); 297 VariableProxy* tag = stmt->tag()->AsVariableProxy();
268 DCHECK_NOT_NULL(tag); 298 DCHECK_NOT_NULL(tag);
299 ZoneList<CaseClause*>* clauses = stmt->cases();
300 int case_count = clauses->length();
301 if (case_count == 0) {
302 block_size_--;
303 return;
304 }
269 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false, 305 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false,
270 0); 306 1);
271 uint16_t fall_through = current_function_builder_->AddLocal(kAstI32); 307 ZoneVector<BlockVisitor*> blocks(zone_);
272 SetLocalTo(fall_through, 0); 308 ZoneVector<int32_t> cases(zone_);
273 309 ZoneMap<int, unsigned int> case_to_block(zone_);
274 ZoneList<CaseClause*>* clauses = stmt->cases(); 310 int default_block = -1;
275 for (int i = 0; i < clauses->length(); ++i) { 311 bool has_default = false;
312 for (int i = case_count - 1; i >= 0; i--) {
276 CaseClause* clause = clauses->at(i); 313 CaseClause* clause = clauses->at(i);
314 blocks.push_back(new BlockVisitor(this, nullptr, kExprBlock, false,
315 clause->statements()->length() + 1));
277 if (!clause->is_default()) { 316 if (!clause->is_default()) {
278 CompileCase(clause, fall_through, tag); 317 Literal* label = clause->label()->AsLiteral();
318 Handle<Object> value = label->value();
319 DCHECK(value->IsNumber() &&
320 label->bounds().upper->Is(cache_.kAsmSigned));
321 int32_t label_value;
322 if (!value->ToInt32(&label_value)) {
323 UNREACHABLE();
324 }
325 case_to_block[label_value] = i;
326 cases.push_back(label_value);
279 } else { 327 } else {
280 ZoneList<Statement*>* stmts = clause->statements(); 328 default_block = i;
281 block_size_ += stmts->length(); 329 has_default = true;
282 RECURSE(VisitStatements(stmts));
283 } 330 }
284 } 331 }
332 if (!has_default) {
333 default_block = case_count;
334 }
335 if (!has_default || case_count > 1) {
336 BlockVisitor switch_logic_block(this, nullptr, kExprBlock, false, 1);
337 CaseNode* root = OrderCases(&cases, zone_);
338 HandleCase(root, case_to_block, tag, default_block);
339 if (root->left_ != nullptr || root->right_ != nullptr ||
340 root->begin_ == root->end_) {
341 block_size_++;
342 current_function_builder_->EmitWithVarInt(kExprBr, default_block);
343 current_function_builder_->Emit(kExprNop);
344 }
345 } else {
346 block_size_ = clauses->at(0)->statements()->length();
347 }
348 for (int i = 0; i < case_count; i++) {
349 CaseClause* clause = clauses->at(i);
350 RECURSE(VisitStatements(clause->statements()));
351 BlockVisitor* v = blocks.at(case_count - i - 1);
352 blocks.pop_back();
353 delete (v);
354 }
285 } 355 }
286 356
287 void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); } 357 void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
288 358
289 void VisitDoWhileStatement(DoWhileStatement* stmt) { 359 void VisitDoWhileStatement(DoWhileStatement* stmt) {
290 DCHECK(in_function_); 360 DCHECK(in_function_);
291 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true, 361 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
292 2); 362 2);
293 RECURSE(Visit(stmt->body())); 363 RECURSE(Visit(stmt->body()));
294 current_function_builder_->Emit(kExprIf); 364 current_function_builder_->Emit(kExprIf);
(...skipping 1238 matching lines...) Expand 10 before | Expand all | Expand 10 after
1533 // that zone in constructor may be thrown away once wasm module is written. 1603 // that zone in constructor may be thrown away once wasm module is written.
1534 WasmModuleIndex* AsmWasmBuilder::Run() { 1604 WasmModuleIndex* AsmWasmBuilder::Run() {
1535 AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_); 1605 AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_);
1536 impl.Compile(); 1606 impl.Compile();
1537 WasmModuleWriter* writer = impl.builder_->Build(zone_); 1607 WasmModuleWriter* writer = impl.builder_->Build(zone_);
1538 return writer->WriteTo(zone_); 1608 return writer->WriteTo(zone_);
1539 } 1609 }
1540 } // namespace wasm 1610 } // namespace wasm
1541 } // namespace internal 1611 } // namespace internal
1542 } // namespace v8 1612 } // namespace v8
OLDNEW
« no previous file with comments | « BUILD.gn ('k') | src/wasm/switch-logic.h » ('j') | src/wasm/switch-logic.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698