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

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
« no previous file with comments | « BUILD.gn ('k') | src/wasm/switch-logic.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 std::vector<uint8_t> count =
277 UnsignedLEB128From(node->end - node->begin + 1);
278 current_function_builder_->EmitCode(&count[0],
279 static_cast<uint32_t>(count.size()));
280 for (int v = node->begin; v <= node->end; v++) {
281 if (case_to_block.find(v) != case_to_block.end()) {
282 byte break_code[] = {BR_TARGET(case_to_block.at(v))};
283 current_function_builder_->EmitCode(break_code, sizeof(break_code));
284 } else {
285 byte break_code[] = {BR_TARGET(default_block)};
286 current_function_builder_->EmitCode(break_code, sizeof(break_code));
287 }
288 if (v == kMaxInt) {
289 break;
290 }
291 }
292 byte break_code[] = {BR_TARGET(default_block)};
293 current_function_builder_->EmitCode(break_code, sizeof(break_code));
294 // TODO(aseemgarg): remove the if once sub 0 is fixed
295 if (node->begin != 0) {
296 current_function_builder_->Emit(kExprI32Sub);
297 VisitVariableProxy(tag);
298 byte code[] = {WASM_I32V(node->begin)};
299 current_function_builder_->EmitCode(code, sizeof(code));
300 } else {
301 VisitVariableProxy(tag);
302 }
303 }
264 } 304 }
265 305
266 void VisitSwitchStatement(SwitchStatement* stmt) { 306 void VisitSwitchStatement(SwitchStatement* stmt) {
267 VariableProxy* tag = stmt->tag()->AsVariableProxy(); 307 VariableProxy* tag = stmt->tag()->AsVariableProxy();
268 DCHECK_NOT_NULL(tag); 308 DCHECK_NOT_NULL(tag);
309 ZoneList<CaseClause*>* clauses = stmt->cases();
310 int case_count = clauses->length();
311 if (case_count == 0) {
312 block_size_--;
313 return;
314 }
269 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false, 315 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprBlock, false,
270 0); 316 1);
271 uint16_t fall_through = current_function_builder_->AddLocal(kAstI32); 317 ZoneVector<BlockVisitor*> blocks(zone_);
272 SetLocalTo(fall_through, 0); 318 ZoneVector<int32_t> cases(zone_);
273 319 ZoneMap<int, unsigned int> case_to_block(zone_);
274 ZoneList<CaseClause*>* clauses = stmt->cases(); 320 bool has_default = false;
275 for (int i = 0; i < clauses->length(); ++i) { 321 for (int i = case_count - 1; i >= 0; i--) {
276 CaseClause* clause = clauses->at(i); 322 CaseClause* clause = clauses->at(i);
323 blocks.push_back(new BlockVisitor(this, nullptr, kExprBlock, false,
324 clause->statements()->length() + 1));
277 if (!clause->is_default()) { 325 if (!clause->is_default()) {
278 CompileCase(clause, fall_through, tag); 326 Literal* label = clause->label()->AsLiteral();
327 Handle<Object> value = label->value();
328 DCHECK(value->IsNumber() &&
329 label->bounds().upper->Is(cache_.kAsmSigned));
330 int32_t label_value;
331 if (!value->ToInt32(&label_value)) {
332 UNREACHABLE();
333 }
334 case_to_block[label_value] = i;
335 cases.push_back(label_value);
279 } else { 336 } else {
280 ZoneList<Statement*>* stmts = clause->statements(); 337 DCHECK_EQ(i, case_count - 1);
281 block_size_ += stmts->length(); 338 has_default = true;
282 RECURSE(VisitStatements(stmts));
283 } 339 }
284 } 340 }
341 if (!has_default || case_count > 1) {
342 int default_block = has_default ? case_count - 1 : case_count;
343 BlockVisitor switch_logic_block(this, nullptr, kExprBlock, false, 1);
344 CaseNode* root = OrderCases(&cases, zone_);
345 HandleCase(root, case_to_block, tag, default_block);
346 if (root->left != nullptr || root->right != nullptr ||
347 root->begin == root->end) {
348 block_size_++;
349 current_function_builder_->EmitWithVarInt(kExprBr, default_block);
350 current_function_builder_->Emit(kExprNop);
351 }
352 } else {
353 block_size_ = clauses->at(0)->statements()->length();
354 }
355 for (int i = 0; i < case_count; i++) {
356 CaseClause* clause = clauses->at(i);
357 RECURSE(VisitStatements(clause->statements()));
358 BlockVisitor* v = blocks.at(case_count - i - 1);
359 blocks.pop_back();
360 delete v;
361 }
285 } 362 }
286 363
287 void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); } 364 void VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
288 365
289 void VisitDoWhileStatement(DoWhileStatement* stmt) { 366 void VisitDoWhileStatement(DoWhileStatement* stmt) {
290 DCHECK(in_function_); 367 DCHECK(in_function_);
291 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true, 368 BlockVisitor visitor(this, stmt->AsBreakableStatement(), kExprLoop, true,
292 2); 369 2);
293 RECURSE(Visit(stmt->body())); 370 RECURSE(Visit(stmt->body()));
294 current_function_builder_->Emit(kExprIf); 371 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. 1610 // that zone in constructor may be thrown away once wasm module is written.
1534 WasmModuleIndex* AsmWasmBuilder::Run() { 1611 WasmModuleIndex* AsmWasmBuilder::Run() {
1535 AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_); 1612 AsmWasmBuilderImpl impl(isolate_, zone_, literal_, foreign_, typer_);
1536 impl.Compile(); 1613 impl.Compile();
1537 WasmModuleWriter* writer = impl.builder_->Build(zone_); 1614 WasmModuleWriter* writer = impl.builder_->Build(zone_);
1538 return writer->WriteTo(zone_); 1615 return writer->WriteTo(zone_);
1539 } 1616 }
1540 } // namespace wasm 1617 } // namespace wasm
1541 } // namespace internal 1618 } // namespace internal
1542 } // namespace v8 1619 } // namespace v8
OLDNEW
« no previous file with comments | « BUILD.gn ('k') | src/wasm/switch-logic.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698