Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1838973002:
optimized switch implementation (Closed)
Description[wasm] optimized switch implementation in asm.js to wasm builder
This change implements switch as a balanced if/else tree or break table or
hybrid. A lot of asm.js modules are expected to extensively use switch
alongside function tables that can benefit from a better implementation.
BUG=v8:4203
TEST=mjsunit/asm-wasm
R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org
LOG=N
Committed: https://crrev.com/1d37d4216b23bd54822ada4e92457291ad70829b
Cr-Commit-Position: refs/heads/master@{#35455}
Patch Set 1 #Patch Set 2 : unskip embenchen tests #
Total comments: 8
Patch Set 3 : #
Total comments: 4
Patch Set 4 : #
Total comments: 2
Patch Set 5 : #Patch Set 6 : #
Total comments: 2
Patch Set 7 : #Patch Set 8 : #Patch Set 9 : #
Total comments: 10
Patch Set 10 : #Patch Set 11 : #
Total comments: 7
Patch Set 12 : #
Total comments: 6
Patch Set 13 : #Patch Set 14 : #
Total comments: 4
Patch Set 15 : #
Depends on Patchset: Messages
Total messages: 69 (27 generated)
hey guys Please take a look. Seems like there was a bug earlier. Now the remaining two embenchen tests are also working on my machine. Enabled them and will see if they pass the bots. No tests added yet. Will add unit tests for the switch strategy and some JS tests that should result in all three - tree based switch, break table based switch, hybrid switch.
The CQ bit was checked by aseemgarg@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/20001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/20001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:302: int case_count = clauses->length(); You actually need to handle this, my read of the spec allows empty switches. https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:305: ZoneVector<int32_t> cases(zone_); So I was kind of hoping we could capture this algorithm in a way that's less intertwined with the builder. Something that doesn't know about emitting wasm ops, or the AST, but generates the right structure? Could we move this into table_switch.h with an interface like: class TableSwitchHelper { // something better named. public: void AddCase(int32_t value); void Run(); // Implemented in asm-wasm-builder void EmitIfForSwitch(int32_t value, int direction) = 0; void EmitBrForSwitch(int layers) = 0; void EmitBrTableForSwith() = 0; void EmitSwitchVariable(int minus) = 0; void EmitBlockBody(int index) = 0; }; This would let you write a proper set of unittests for it separate for everything else. WDYT? https://codereview.chromium.org/1838973002/diff/20001/src/wasm/switch-logic.h File src/wasm/switch-logic.h (right): https://codereview.chromium.org/1838973002/diff/20001/src/wasm/switch-logic.h... src/wasm/switch-logic.h:1: // Copyright 2015 the V8 project authors. All rights reserved. 2016 https://codereview.chromium.org/1838973002/diff/20001/test/mjsunit/mjsunit.st... File test/mjsunit/mjsunit.status (right): https://codereview.chromium.org/1838973002/diff/20001/test/mjsunit/mjsunit.st... test/mjsunit/mjsunit.status:282: #'wasm/embenchen/box2d': [SKIP], # hang Delete entirely. Sorry the one below too.
As we'd said offline, that other interface might be hard to test.
It feels like this is a pure computation, so testing it that way seems
desirable.
Better interface for testing might be something like:
class SwitchOp {
enum {
kIfLess,
kIfGreater,
kIfEq,
kBrTable,
kBreak,
kBeginBlock,
kEndBlock,
} kind;
int32_t value1;
int32_t value2;
};
ZoneVector<SwitchOp>*
ComputeSwitch(Zone* z, ZoneVector<int32_t> cases);
This will take the set of case labels, and compute a wasm order (pre for now,
post/in-order later) walk of the operations to emit:
BeginBlock
BeginBlock
IfLess 123
Break 2
...
BrTable [base]
etc.
EndBlock
EndBlock
For now BeginBlock + EndBlock can keep implemented in asm-wasm-builder with the
stack of BlockVisitors you have, but this will be much simpler after we switch
to post+in-order blocks.
This would let you have tests that enumerate the trees of control structures you
want to get for particular sets of case values.
On the other hand, I suppose what we really want to test is that the control
structure is valid (does what it should).
Though I can't think of a way to do this directly that doesn't devolve into
interpreting a mini-expression tree.
Am I correct that you're generating overall this?
{
{
{
{
if + brswitch to L1-3 ***
}
L1:
[Code region 1]
}
L2:
[Code region 2]
}
L3:
[Code region 3]
}
Hmmn, I guess you've more or less moved out the *** part.
The outer block structure is hard to change and gets simpler after we have
in-order block ops. That will make VisitSwitch simpler after the post-order
stuff lands.
HandleCase is more or less just capturing how to emit wasm specific ops.
Maybe this is ok, assuming unittests for OrderCases.
Ben / Andreas you guys have any ideas?
DBC: - The change description lacks a [wasm] tag; labeling makes scanning through regression ranges so much easier. - Descriptive commit messages are considered good in general. Is there any detail/rationale/background beyond "optimized" that's worth documenting? - The right format for the BUG lines is BUG=v8:4203
Added [wasm] to commit message and put a little more explanation in commit message. https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:302: int case_count = clauses->length(); On 2016/03/29 19:38:45, bradnelson wrote: > You actually need to handle this, my read of the spec allows empty switches. Done. https://codereview.chromium.org/1838973002/diff/20001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:305: ZoneVector<int32_t> cases(zone_); On 2016/03/29 19:38:45, bradnelson wrote: > So I was kind of hoping we could capture this algorithm in a way that's less > intertwined with the builder. Something that doesn't know about emitting wasm > ops, or the AST, but generates the right structure? > Could we move this into table_switch.h with an interface like: > > class TableSwitchHelper { // something better named. > public: > void AddCase(int32_t value); > void Run(); > > // Implemented in asm-wasm-builder > void EmitIfForSwitch(int32_t value, int direction) = 0; > void EmitBrForSwitch(int layers) = 0; > void EmitBrTableForSwith() = 0; > void EmitSwitchVariable(int minus) = 0; > void EmitBlockBody(int index) = 0; > }; > > This would let you write a proper set of unittests for it separate for > everything else. > > WDYT? Done as discussed https://codereview.chromium.org/1838973002/diff/20001/src/wasm/switch-logic.h File src/wasm/switch-logic.h (right): https://codereview.chromium.org/1838973002/diff/20001/src/wasm/switch-logic.h... src/wasm/switch-logic.h:1: // Copyright 2015 the V8 project authors. All rights reserved. On 2016/03/29 19:38:45, bradnelson wrote: > 2016 Done. https://codereview.chromium.org/1838973002/diff/20001/test/mjsunit/mjsunit.st... File test/mjsunit/mjsunit.status (right): https://codereview.chromium.org/1838973002/diff/20001/test/mjsunit/mjsunit.st... test/mjsunit/mjsunit.status:282: #'wasm/embenchen/box2d': [SKIP], # hang On 2016/03/29 19:38:45, bradnelson wrote: > Delete entirely. Sorry the one below too. Done.
bradnelson@google.com changed reviewers: + bradnelson@google.com
Can you edit the issue and post your updated commit message (it doesn't automatically get uploaded after the initial upload).
Description was changed from ========== optimized switch implementation BUG= https://code.google.com/p/v8/issues/detail?id=4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ========== to ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. This also fixes the two embenchen tests - lua_binarytrees and box2d BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ==========
Description was changed from ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. This also fixes the two embenchen tests - lua_binarytrees and box2d BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ========== to ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. This also fixes the two embenchen tests - lua_binarytrees and box2d BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ==========
On 2016/03/31 21:16:32, bradn wrote: > Can you edit the issue and post your updated commit message (it doesn't > automatically get uploaded after the initial upload). done
Actually can you split out enabling those two testing into a separate CL? I'm concerned something platform specific might crop up that's not covered by the trybots. That way you can hopefully land this cleanly even if something comes up with those two tests. https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:353: delete (v); drop the parens.
Description was changed from ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. This also fixes the two embenchen tests - lua_binarytrees and box2d BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ========== to ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ==========
On 2016/03/31 21:24:31, bradn wrote: > Actually can you split out enabling those two testing into a separate CL? > I'm concerned something platform specific might crop up that's not covered by > the trybots. That way you can hopefully land this cleanly even if something > comes up with those two tests. > > https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... > File src/wasm/asm-wasm-builder.cc (right): > > https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... > src/wasm/asm-wasm-builder.cc:353: delete (v); > drop the parens. done
https://codereview.chromium.org/1838973002/diff/40001/src/wasm/switch-logic.h File src/wasm/switch-logic.h (right): https://codereview.chromium.org/1838973002/diff/40001/src/wasm/switch-logic.h... src/wasm/switch-logic.h:17: int begin_; Since you're using this as a struct, the style guide calls for it to be declared that way, and the _ is for private member variables. Or I suppose you could keep it a class with accessors, as begin + end are immutable one created? https://codereview.chromium.org/1838973002/diff/60001/src/wasm/switch-logic.cc File src/wasm/switch-logic.cc (right): https://codereview.chromium.org/1838973002/diff/60001/src/wasm/switch-logic.c... src/wasm/switch-logic.cc:11: CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) { Put this in an anonymous namespace.
https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/40001/src/wasm/asm-wasm-build... src/wasm/asm-wasm-builder.cc:353: delete (v); On 2016/03/31 21:24:31, bradn wrote: > drop the parens. Done. https://codereview.chromium.org/1838973002/diff/40001/src/wasm/switch-logic.h File src/wasm/switch-logic.h (right): https://codereview.chromium.org/1838973002/diff/40001/src/wasm/switch-logic.h... src/wasm/switch-logic.h:17: int begin_; On 2016/03/31 21:39:09, bradn wrote: > Since you're using this as a struct, the style guide calls for it to be declared > that way, and the _ is for private member variables. > > Or I suppose you could keep it a class with accessors, as begin + end are > immutable one created? Done. https://codereview.chromium.org/1838973002/diff/60001/src/wasm/switch-logic.cc File src/wasm/switch-logic.cc (right): https://codereview.chromium.org/1838973002/diff/60001/src/wasm/switch-logic.c... src/wasm/switch-logic.cc:11: CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) { On 2016/03/31 21:39:09, bradn wrote: > Put this in an anonymous namespace. Done.
lgtm with two more suggested tests. https://codereview.chromium.org/1838973002/diff/100001/test/unittests/wasm/sw... File test/unittests/wasm/switch-logic-unittest.cc (right): https://codereview.chromium.org/1838973002/diff/100001/test/unittests/wasm/sw... test/unittests/wasm/switch-logic-unittest.cc:75: TEST_F(SwitchLogicTest, Single_Case) { Maybe an empty + single item tests at this level?
https://codereview.chromium.org/1838973002/diff/100001/test/unittests/wasm/sw... File test/unittests/wasm/switch-logic-unittest.cc (right): https://codereview.chromium.org/1838973002/diff/100001/test/unittests/wasm/sw... test/unittests/wasm/switch-logic-unittest.cc:75: TEST_F(SwitchLogicTest, Single_Case) { On 2016/04/01 00:14:50, bradnelson wrote: > Maybe an empty + single item tests at this level? Single item test already present. This function can't deal with empty case (doesn't get called in that case). But will fix that sake of a sane API.
The CQ bit was checked by aseemgarg@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bradnelson@chromium.org Link to the patchset: https://codereview.chromium.org/1838973002/#ps120001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/120001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/120001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: v8_linux64_avx2_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel/builds/...) v8_linux_arm64_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel/builds/1...) v8_linux_arm_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm_rel/builds/16073) v8_linux_dbg_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg_ng/builds/3665) v8_linux_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng/builds/3665)
The CQ bit was checked by aseemgarg@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bradnelson@chromium.org Link to the patchset: https://codereview.chromium.org/1838973002/#ps140001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/140001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/140001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: v8_linux64_avx2_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel/builds/...) v8_linux64_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_rel_ng/builds/3654) v8_linux_arm64_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel/builds/1...) v8_linux_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng/builds/3666)
The CQ bit was checked by aseemgarg@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/160001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/160001
The CQ bit was unchecked by aseemgarg@chromium.org
The CQ bit was checked by aseemgarg@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bradnelson@chromium.org Link to the patchset: https://codereview.chromium.org/1838973002/#ps160001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/160001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/160001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: v8_presubmit on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/13100)
https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:256: if (node->left != nullptr) { I kind of doubt that a binary search tree is worth it. Either a flat dense table or a series of if's will probably suffice. https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:348: for (int i = 0; i < case_count; i++) { I'm not sure if the block depths are right here; we need a lot more tests for this. https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm.js (right): https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1497: (function TestSwitchWithBrTable() { Please pull these out into a new test file: test/mjsunit/wasm/asm-wasm-switch.js https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1527: (function TestSwitchWithBalancedTree() { There need to be a lot more tests, e.g. with break and fall through, the default case in the middle, and many other permutations.
Oops, thought I sent this out a last week. https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:256: if (node->left != nullptr) { On 2016/04/01 09:22:45, titzer wrote: > I kind of doubt that a binary search tree is worth it. Either a flat dense table > or a series of if's will probably suffice. FWIW, a survey of module suggests these are fairly sparse. Are you concerned about negative consequences of the tree? Something we should measure? https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm.js (right): https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1626: })(); Yeah actually what would be really nice to vet tables larger than 256 don't blow up. How about an mjsunit test that: Uses strings to build of the body of an asm module that does a large random remapping with random fall-thrus like: switch(x|0) { case 11: case 7: return 5; case 9: case 10: return 6; ... } And then check all the values in some range.
https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/160001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:348: for (int i = 0; i < case_count; i++) { On 2016/04/01 09:22:45, titzer wrote: > I'm not sure if the block depths are right here; we need a lot more tests for > this. Re-read. Seems to be fine and working. https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm.js (right): https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1497: (function TestSwitchWithBrTable() { On 2016/04/01 09:22:45, titzer wrote: > Please pull these out into a new test file: test/mjsunit/wasm/asm-wasm-switch.js Done. https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1527: (function TestSwitchWithBalancedTree() { On 2016/04/01 09:22:45, titzer wrote: > There need to be a lot more tests, e.g. with break and fall through, the default > case in the middle, and many other permutations. Some of the tests were there before. Added some more. https://codereview.chromium.org/1838973002/diff/160001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm.js:1626: })(); On 2016/04/04 22:31:12, bradn wrote: > Yeah actually what would be really nice to vet tables larger than 256 don't blow > up. > > How about an mjsunit test that: > Uses strings to build of the body of an asm module that does a large random > remapping with random fall-thrus like: > switch(x|0) { > case 11: > case 7: > return 5; > case 9: > case 10: > return 6; > ... > } > > And then check all the values in some range. Done.
https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:291: if (node->begin != 0) { Can you add a TODO / comment that this is required due to the issue you isolated and link to that. https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:365: str = str.concat("case ", i.toString(), ": return ", i.toString(), ";"); Can you set this and the one below it up as a function to call to get the module (with a gap value between items?) generateSwitchModule(gap, size); Then test more than one size (maybe some non-powers of 2). Then also add a parameter to it to emit something else at certain values. generateSwitchModule(gap, size, handle_case) That would be something like this normally: generateSwitchModule(3, 512, function(i) { return 'return ' + i ';'; }); But could also be used like: generateSwitchModule(3, 512, function(i) { if (i % 7 == 0) { return 'break;'; } else { return 'return ' + i + ';';}) That way you can have tests that the right thing happens if you have breaks in some of the cases or even fall thrus: generateSwitchModule(3, 512, function(i) { if (i % 7 == 0) { return 'return ' + i + ';'; } else { return ''; }) You might also want to have a value map function parameter instead of the gap: generateSwitchModule(size, order_func, case_func) i.e. generateSwitchModule(512, function(i) { return i * 3; }, function(i) { return 'return ' + i + ';' }) Using the above check: breaking every nth item. fall thru for a large number of items. conditionally breaking inside each case. emitting a small switch inside each case. https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:387: str = str.concat("case ", (3*i).toString(), ": return ", (3*i).toString(), ";"); use string concat to wrap this to 80 columns
https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:291: if (node->begin != 0) { On 2016/04/07 23:46:59, bradn wrote: > Can you add a TODO / comment that this is required due to the issue you isolated > and link to that. problem fixed now https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:365: str = str.concat("case ", i.toString(), ": return ", i.toString(), ";"); On 2016/04/07 23:46:59, bradn wrote: > Can you set this and the one below it up as a function to call to get the module > (with a gap value between items?) > generateSwitchModule(gap, size); > Then test more than one size (maybe some non-powers of 2). > > Then also add a parameter to it to emit something else at certain values. > generateSwitchModule(gap, size, handle_case) > That would be something like this normally: > generateSwitchModule(3, 512, function(i) { return 'return ' + i ';'; }); > But could also be used like: > generateSwitchModule(3, 512, function(i) { if (i % 7 == 0) { return 'break;'; } > else { return 'return ' + i + ';';}) > > That way you can have tests that the right thing happens if you have breaks in > some of the cases or even fall thrus: > generateSwitchModule(3, 512, function(i) { if (i % 7 == 0) { return 'return ' + > i + ';'; } else { return ''; }) > > You might also want to have a value map function parameter instead of the gap: > generateSwitchModule(size, order_func, case_func) > i.e. > generateSwitchModule(512, function(i) { return i * 3; }, > function(i) { return 'return ' + i + ';' }) > > Using the above check: > breaking every nth item. > fall thru for a large number of items. > conditionally breaking inside each case. > emitting a small switch inside each case. Added some cases that I think should stress the implementation (in terms of properly using LEBs instead of single bytes). These plus the other tests should be covering most corner cases. https://codereview.chromium.org/1838973002/diff/200001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:387: str = str.concat("case ", (3*i).toString(), ": return ", (3*i).toString(), ";"); On 2016/04/07 23:46:59, bradn wrote: > use string concat to wrap this to 80 columns Done.
https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/200001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:291: if (node->begin != 0) { On 2016/04/11 20:59:19, aseemgarg wrote: > On 2016/04/07 23:46:59, bradn wrote: > > Can you add a TODO / comment that this is required due to the issue you > isolated > > and link to that. > > problem fixed now Problem wasn't fixed. So, put the if back in with a todo
lgtm (if you add the a couple tests with case values around MIN/MAX_INT). https://codereview.chromium.org/1838973002/diff/220001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/220001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:280: for (int v = node->begin; v <= node->end; v++) { You should add one more class of test cases: variants with MIN_INT, MAX_INT (ie make sure you got all the sign / <= etc right). https://codereview.chromium.org/1838973002/diff/220001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/220001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:379: return "return ".concat(k, ";"); Tabbing is a little weird on this, I usually do just 2 for a nested function (but consult the style guide to be sure).
https://codereview.chromium.org/1838973002/diff/220001/test/unittests/wasm/sw... File test/unittests/wasm/switch-logic-unittest.cc (right): https://codereview.chromium.org/1838973002/diff/220001/test/unittests/wasm/sw... test/unittests/wasm/switch-logic-unittest.cc:20: ZoneVector<int> values(&zone); Actually this doesn't merge anymore. Since you're using a TestWithZone, you can pass zone() for these instead, which will work with the new change to zone (and worked before).
https://codereview.chromium.org/1838973002/diff/220001/src/wasm/asm-wasm-buil... File src/wasm/asm-wasm-builder.cc (right): https://codereview.chromium.org/1838973002/diff/220001/src/wasm/asm-wasm-buil... src/wasm/asm-wasm-builder.cc:280: for (int v = node->begin; v <= node->end; v++) { On 2016/04/12 20:36:09, bradn wrote: > You should add one more class of test cases: > variants with MIN_INT, MAX_INT (ie make sure you got all the sign / <= etc > right). Done. https://codereview.chromium.org/1838973002/diff/220001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/220001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:379: return "return ".concat(k, ";"); On 2016/04/12 20:36:10, bradn wrote: > Tabbing is a little weird on this, I usually do just 2 for a nested function > (but consult the style guide to be sure). Changed to using variable. Much cleaner. https://codereview.chromium.org/1838973002/diff/220001/test/unittests/wasm/sw... File test/unittests/wasm/switch-logic-unittest.cc (right): https://codereview.chromium.org/1838973002/diff/220001/test/unittests/wasm/sw... test/unittests/wasm/switch-logic-unittest.cc:20: ZoneVector<int> values(&zone); On 2016/04/12 20:46:47, bradn wrote: > Actually this doesn't merge anymore. > Since you're using a TestWithZone, you can pass zone() for these instead, which > will work with the new change to zone (and worked before). Done.
lgtm
aseemgarg@chromium.org changed reviewers: + mtrofin@chromium.org
The CQ bit was checked by aseemgarg@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bradnelson@chromium.org Link to the patchset: https://codereview.chromium.org/1838973002/#ps260001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/260001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/260001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: v8_linux_arm64_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel_ng/build...)
The CQ bit was checked by aseemgarg@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/260001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/260001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
rubber stamp lgtm https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:110: switch(x|0) { Is there a reason why you do "x|0" twice? https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:128: case 14: return 14; Could you return different values than x, so that you can differentiate the test function from function main(x) { return x; }
https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... File test/mjsunit/wasm/asm-wasm-switch.js (right): https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:110: switch(x|0) { On 2016/04/13 16:27:47, ahaas wrote: > Is there a reason why you do "x|0" twice? This is as per spec. The first x|0 specifies that x is an int type. The second one coerces it to signed type that is input for switch. https://codereview.chromium.org/1838973002/diff/260001/test/mjsunit/wasm/asm-... test/mjsunit/wasm/asm-wasm-switch.js:128: case 14: return 14; On 2016/04/13 16:27:47, ahaas wrote: > Could you return different values than x, so that you can differentiate the test > function from > function main(x) { return x; } Done.
The CQ bit was checked by aseemgarg@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bradnelson@chromium.org, ahaas@chromium.org, bradnelson@google.com Link to the patchset: https://codereview.chromium.org/1838973002/#ps280001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1838973002/280001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1838973002/280001
Message was sent while issue was closed.
Description was changed from ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ========== to ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ==========
Message was sent while issue was closed.
Committed patchset #15 (id:280001)
Message was sent while issue was closed.
Description was changed from ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N ========== to ========== [wasm] optimized switch implementation in asm.js to wasm builder This change implements switch as a balanced if/else tree or break table or hybrid. A lot of asm.js modules are expected to extensively use switch alongside function tables that can benefit from a better implementation. BUG=v8:4203 TEST=mjsunit/asm-wasm R=titzer@chromium.org,bradnelson@chromium.org,ahaas@chromium.org LOG=N Committed: https://crrev.com/1d37d4216b23bd54822ada4e92457291ad70829b Cr-Commit-Position: refs/heads/master@{#35455} ==========
Message was sent while issue was closed.
Patchset 15 (id:??) landed as https://crrev.com/1d37d4216b23bd54822ada4e92457291ad70829b Cr-Commit-Position: refs/heads/master@{#35455} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
