[hydrogen] optimize switch with string clauses

[hydrogen] optimize switch with string clauses

Hydrogen should optimize not only SMI clauses, but clauses with string literals
too.

Patch from fedor.indutny <fedor.indutny@gmail.com>;.

R=vegorov@chromium.org
BUG=
TEST=
Committed: http://code.google.com/p/v8/source/detail?r=9901
Committed: http://code.google.com/p/v8/source/detail?r=10019

[indutny, 2011-10-24 05:59:36]

Base URL is incorrect, please update it if it's possible:
https://github.com/indutny/v8/tree/feature-switch-string-literal-opt

[Vyacheslav Egorov (Chromium), 2011-10-24 09:37:19]

I think it makes sense to distinguish between fully smi and fully string literal
cases and do not compile mixed switches.

When switch is fully string literal you can emit symbol check before all
comparisons (GVN will eliminate redundant checks automatically but why leave it
to GVN if we can do it easily manually).

http://codereview.chromium.org/8373029/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/1/src/hydrogen.cc#newcode2726
src/hydrogen.cc:2726: compare->SetSuccessorAt(0, body_block);
Can be moved outside of the if to avoid code duplication.

[indutny, 2011-10-24 10:14:47]

Updated.

[Vyacheslav Egorov (Chromium), 2011-10-24 10:56:26]

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2693
src/hydrogen.cc:2693: enum {
We don't use anonymous enums

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2694
src/hydrogen.cc:2694: none, smi, string
use either 

kSmiSwitch

or 

SMI_SWITCH

naming for enum-members.

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2703
src/hydrogen.cc:2703: if (clause_type == none) {
I would suggest extracting loop part that computes switch type into a separate
method just to make it cleaner.

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2711
src/hydrogen.cc:2711: } else if (clause->label()->IsSmiLiteral() && clause_type
== string ||
clause can be neither smi nor string literal.

I think what you want here is 

(clause_type == kSmiSwitch && !clause->label()->IsSmiLiteral()) || ...

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2741
src/hydrogen.cc:2741: compare =
reinterpret_cast<HControlInstruction*>(compare_);
I don't think you need reinterpret_cast here.

HCompareObjectEqAndBranch* should be assignable to HControlInstruction.

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2743
src/hydrogen.cc:2743: HCompareObjectEqAndBranch* compare_ =
I think you don't need this temp variable

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2744
src/hydrogen.cc:2744: new(zone()) HCompareObjectEqAndBranch(tag_value,
label_value);
Why not CompareIDAndBranch? Once loop that computes type is extracted you can
use computed type to emit is-symbol test before the switch.

http://codereview.chromium.org/8373029/diff/2002/src/hydrogen.cc#newcode2745
src/hydrogen.cc:2745: compare =
reinterpret_cast<HControlInstruction*>(compare_);
I don't think you need reinterpret_cast here.

HCompareObjectEqAndBranch* should be assignable to HControlInstruction.

[indutny, 2011-10-24 11:57:36]

Updated

[Vyacheslav Egorov (Chromium), 2011-10-24 12:12:00]

lgtm with comments addressed.

please address the comments and I will land.

http://codereview.chromium.org/8373029/diff/8001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/8001/src/hydrogen.cc#newcode2693
src/hydrogen.cc:2693: SwitchType switch_type = UNSUPPORTED_SWITCH;
UNSUPPORTED -> UNKNOWN?

http://codereview.chromium.org/8373029/diff/8001/src/hydrogen.cc#newcode2708
src/hydrogen.cc:2708: } else if (clause->label()->IsSmiLiteral() &&
labels can be neither smi nor strings. Correct condition would be:

(switch_type == STRING_SWITCH && !clause->label()->IsStringLiteral()) || 
(switch_type == SMI_SWITCH && !clause->label()->IsSmiLiteral())

http://codereview.chromium.org/8373029/diff/8001/src/hydrogen.cc#newcode2718
src/hydrogen.cc:2718:
AddInstruction(HCheckInstanceType::NewIsSymbol(tag_value));
You also need HCheckNonSmi(tag_value) otherwise it IsSymbolCheck will segfault
when you have a smi as a tag value

[indutny, 2011-10-24 12:18:37]

Updated

[Vyacheslav Egorov (Chromium), 2011-10-24 12:27:29]

additional comment.

I'll fix it myself and also add tests before landing.

http://codereview.chromium.org/8373029/diff/11001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/11001/src/hydrogen.cc#newcode2719
src/hydrogen.cc:2719: AddInstruction(new(zone()) HCheckNonSmi(tag_value));
Checking that tag_value is non-smi after is-symbol already segfaulted is not
very helpful. 

Usually you want to check for something before you segfault.

[indutny, 2011-10-26 20:29:21]

Can you please benchmark this branch. It's faster on jslint for me.

[Vyacheslav Egorov (Chromium), 2011-10-28 12:39:05]

Adding Florian as a reviewer to have more eyes on graph construction.

[indutny, 2011-10-28 22:24:02]

Finally, this thing works w/o segfaults and assertions.
On my machine jslint is about 5% faster on patched d8 than on bleeding_edge.

Added x64 instruction, but can't test it (only have 32bit mbpro right now).

[fschneider, 2011-11-01 09:26:19]

Here are my comments: I'd like to see the code simpler if possible. Also
lazy-deoptimization is a major concern.

http://codereview.chromium.org/8373029/diff/32026/src/ast.h
File src/ast.h (right):

http://codereview.chromium.org/8373029/diff/32026/src/ast.h#newcode713
src/ast.h:713: bool IsSymbolCompare() { return compare_type_ == SYMBOL_ONLY; }
You introduce IsSymbolCompare, but it does not seem to be used anywhere. Can you
use it in the same way we use the type feedback for smis?

http://codereview.chromium.org/8373029/diff/32026/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/32026/src/hydrogen.cc#newcode2786
src/hydrogen.cc:2786: compare = new(zone()) HCompareGenericAndBranch(context,
tag_value,
Not sure this works: If you pass an object as tag value, we may get a
lazy-deoptimization at this instruction: The generic compare may invoke other JS
code through valueOf method.

The problem is that we can't insert a LLazyBailout instruction for the
lazy-deopt after a branch. That's why we only had CompareGeneric (without
branch).

How about only handling the string-cases, and deoptimize on others? I think the
code would get a lot simpler, too.

http://codereview.chromium.org/8373029/diff/32026/src/hydrogen.cc#newcode2804
src/hydrogen.cc:2804: if (last_block != NULL) {
Can it happen at all that we deoptimize (and last_block == NULL) if there are
only string-literals? last_block should be never NULL in this case, shouldn't
it?

http://codereview.chromium.org/8373029/diff/32026/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/32026/src/ia32/lithium-ia32.cc#ne...
src/ia32/lithium-ia32.cc:1464: return
AssignEnvironment(MarkAsCall(DefineFixed(result, eax), instr));
MarkAsCall should already assign environments if necessary, so no need to
explicitly do it here.

[indutny, 2011-11-01 09:31:07]

http://codereview.chromium.org/8373029/diff/32026/src/ast.h
File src/ast.h (right):

http://codereview.chromium.org/8373029/diff/32026/src/ast.h#newcode713
src/ast.h:713: bool IsSymbolCompare() { return compare_type_ == SYMBOL_ONLY; }
On 2011/11/01 09:26:19, fschneider wrote:
> You introduce IsSymbolCompare, but it does not seem to be used anywhere. Can
you
> use it in the same way we use the type feedback for smis?

Probably, better remove it, as I can't see any use for it in current version of
code (because of oddball checks)

http://codereview.chromium.org/8373029/diff/32026/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/32026/src/hydrogen.cc#newcode2786
src/hydrogen.cc:2786: compare = new(zone()) HCompareGenericAndBranch(context,
tag_value,
On 2011/11/01 09:26:19, fschneider wrote:
> Not sure this works: If you pass an object as tag value, we may get a
> lazy-deoptimization at this instruction: The generic compare may invoke other
JS
> code through valueOf method.
> 
> The problem is that we can't insert a LLazyBailout instruction for the
> lazy-deopt after a branch. That's why we only had CompareGeneric (without
> branch).
> 
> How about only handling the string-cases, and deoptimize on others? I think
the
> code would get a lot simpler, too.

tag_value can't be object, as we have oddball check above

http://codereview.chromium.org/8373029/diff/32026/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/32026/src/ia32/lithium-ia32.cc#ne...
src/ia32/lithium-ia32.cc:1464: return
AssignEnvironment(MarkAsCall(DefineFixed(result, eax), instr));
On 2011/11/01 09:26:19, fschneider wrote:
> MarkAsCall should already assign environments if necessary, so no need to
> explicitly do it here.

It was segfaulting w/o that

[indutny, 2011-11-01 09:53:14]

btw, it fails sometimes when trying to apply uglifyjs on itself, and I don't
understand why (as it works in everything from jslint to my own custom apps)

[indutny, 2011-11-02 12:40:41]

Any news?

[fschneider, 2011-11-02 15:01:17]

The error in jsuglify seems unrelated to your change. I could also reproduce it
in bleeding_edge.

I did some benchmarking and according to our measurements jslint regressed
performance by 3% with the latest patchset. We need a significant win to land
it.

For example I noticed that function "advance" now takes almost twice as long
according to profiling.

http://codereview.chromium.org/8373029/diff/37002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/37002/src/hydrogen.cc#newcode2740
src/hydrogen.cc:2740: oddball_check = new(zone()) HIsStringAndBranch(tag_value);
oddball_check is really the wrong name, I'd suggest string_check since it tests
if tag_value is a string or not.

[indutny, 2011-11-02 16:28:46]

As I can see, problem comes from different place. `advance` was bailout'ed
because of switch clause type restrictions, my patch is removing those
restrictions and it's starting deoptimization on some smi checks (as I can see)
that wasn't introduced by my patch.

Even more, on previous revisions patched d8 was 5 % faster (than w/o switch
optimization).

[indutny, 2011-11-02 16:30:45]

So I guess that performance regression was caused by some v8 team's commits and
we should consider fixing that or at least reverting regression commit.

[indutny, 2011-11-02 18:35:09]

Renamed oddball_check.

Added type feedback check for bailouting switches that are taking non-symbol
strings as input.

[indutny, 2011-11-07 07:50:49]

Any updates?

[fschneider, 2011-11-07 08:27:18]

Sorry for the delay, but we're getting there. My main concern is still the
complexity which may be avoidable, so my comments are about making the code
simpler where possible.

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen-instructions.h...
src/hydrogen-instructions.h:2762: class HCompareGenericAndBranch: public
HTemplateControlInstruction<2, 3> {
This should rather be HStringCompareAndBranch. It can't be used for generic
compares in general due to deoptimization.

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc#newcode2762
src/hydrogen.cc:2762: iterations = iterations * 2;
If it does not yield a big improvement, I'd rather generate 1 pass in any case.
It seems there are 3 cases:
1. only symbols, 2. only strings, 3. generic other stuff (e.g. oddballs)

(1) uses CompareObjectEqAndBranch
(2), (3) use StringCompareAndBranch.

There would need to be imho a strong performance argument to justify generating
2 passes, because it makes the CFG larger and complicates the graph
construction.

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1798: Handle<Code> ic =
CompareIC::GetUninitialized(op);
Use StringCompareStub instead. StringCompareStub should also be fast for
symbols, so maybe it would be fine performance-wise to just do 1 pass of
comparisons using this stub.

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-ia32.cc#ne...
src/ia32/lithium-ia32.cc:1548: return AssignEnvironment(MarkAsCall(result,
instr));
This looks fishy. We should not need an environment if there is neither eager
nor lazy deoptimization.

[indutny, 2011-11-07 11:17:04]

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc#newcode2762
src/hydrogen.cc:2762: iterations = iterations * 2;
It yields a big improvement, as we usually don't know any type feedback for some
clauses and therefore can't use any type information here.

We can set clause count limit to 64 to preserve same maximum blocks count if you
want, but from my benchmarks having two passes of checks and oddball check
before them is most optimal solution for mutual switch tag's value.

[indutny, 2011-11-07 11:49:27]

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1798: Handle<Code> ic =
CompareIC::GetUninitialized(op);
Just benchmarked it, and found that StringCompareStub is slower for
string-to-string comparisons.

[indutny, 2011-11-07 11:53:46]

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-ia32.cc#ne...
src/ia32/lithium-ia32.cc:1548: return AssignEnvironment(MarkAsCall(result,
instr));
You're right. We don't need this anymore

[indutny, 2011-11-07 11:54:10]

Fixed all things you commented. ;)

[fschneider, 2011-11-07 15:33:59]

See my inlined comments.

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc#newcode2762
src/hydrogen.cc:2762: iterations = iterations * 2;
On 2011/11/07 11:17:04, indutny wrote:
> It yields a big improvement, as we usually don't know any type feedback for
some
> clauses and therefore can't use any type information here.
> 
> We can set clause count limit to 64 to preserve same maximum blocks count if
you
> want, but from my benchmarks having two passes of checks and oddball check
> before them is most optimal solution for mutual switch tag's value.

I'm still worried about quadratic size explosion because clause-blocks are not
shared between the two passes. In case of double-nested switch-statements you
get 4 copies of a clause. We need to share at least the clause bodies (as a
result the code for graph building will get even more complicated)

My suggestion: First land a simpler version that uses only 1 pass with
HStringCompareAndBranch. The graph construction would be much cleaner. Then
maybe try to tune it and improve it with concrete benchmark examples. It is
_much_ easier to review smaller chunks. The problem with huge changes is that it
takes forever to review and turnaround time will be long.

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1798: Handle<Code> ic =
CompareIC::GetUninitialized(op);
On 2011/11/07 11:49:28, indutny wrote:
> Just benchmarked it, and found that StringCompareStub is slower for
> string-to-string comparisons.
Ok, thanks for trying out. Stick to the faster version then.
It turns out that CompareIC has a couple of fast checks before going to
slow-compare like string length.

http://codereview.chromium.org/8373029/diff/50003/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

http://codereview.chromium.org/8373029/diff/50003/src/arm/lithium-arm.cc#newc...
src/arm/lithium-arm.cc:1418: return
AssignEnvironment(MarkAsCall(DefineFixed(result, r0), instr));
Unintended change? The call to AssignEnvironment seems unnecessary and does not
appear on the other platforms.

http://codereview.chromium.org/8373029/diff/50003/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/50003/src/hydrogen.cc#newcode2757
src/hydrogen.cc:2757: return Bailout("SwitchStatement: no symbol comparisons
expected");
I don't understand the reason for this bailout. I thought we want to handle
symbol- and non-symbol string comparisons?

[indutny, 2011-11-07 17:06:08]

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/43002/src/hydrogen.cc#newcode2762
src/hydrogen.cc:2762: iterations = iterations * 2;
I tried implementing graph structure like that:
      |
     /\
    /  \
   o    o
   |\  /|
   o  b o
    \ | /
     \|/
      e

But it was much slower, while not generating bodies twice.

Agreed, done

http://codereview.chromium.org/8373029/diff/50003/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

http://codereview.chromium.org/8373029/diff/50003/src/arm/lithium-arm.cc#newc...
src/arm/lithium-arm.cc:1418: return
AssignEnvironment(MarkAsCall(DefineFixed(result, r0), instr));
Sorry, fixed

http://codereview.chromium.org/8373029/diff/50003/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8373029/diff/50003/src/hydrogen.cc#newcode2757
src/hydrogen.cc:2757: return Bailout("SwitchStatement: no symbol comparisons
expected");
In many cases switch is used for parsing (like lex.token in jslint.js) and
cmp(tag_value, any_clause) is always string (non-symbol) comparison. So it's
faster to use full-codegen, rather doing two passes of checks

[fschneider, 2011-11-08 08:57:59]

LGTM.

I'll land it for you. Thanks for the patch!

[indutny, 2011-11-08 08:58:43]

Thanks for reviewing it! Should I open a new request with rest of the features
after you land it?

[fschneider, 2011-11-08 10:14:37]

http://codereview.chromium.org/8373029/diff/47027/src/x64/lithium-codegen-x64.cc
File src/x64/lithium-codegen-x64.cc (right):

http://codereview.chromium.org/8373029/diff/47027/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:1688: __ CmpObjectType(input,
FIRST_NONSTRING_TYPE, rcx);
Here you need to use a temp register like on the other platforms.

You could also use IsObjectTypeString like on ia32.

http://codereview.chromium.org/8373029/diff/47027/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

http://codereview.chromium.org/8373029/diff/47027/src/x64/lithium-x64.cc#newc...
src/x64/lithium-x64.cc:1410: return
AssignEnvironment(MarkAsCall(DefineFixed(result, rax), instr));
Remove this call to AssignEnvironment.

http://codereview.chromium.org/8373029/diff/47027/src/x64/lithium-x64.cc#newc...
src/x64/lithium-x64.cc:1469:
ASSERT(instr->value()->representation().IsTagged());
You need to allocate a temp register using TempRegister() like on the other
platforms.

[indutny, 2011-11-08 10:24:56]

Fixed, thanks

[fschneider, 2011-11-08 10:33:20]

http://codereview.chromium.org/8373029/diff/58004/src/x64/lithium-codegen-x64.cc
File src/x64/lithium-codegen-x64.cc (right):

http://codereview.chromium.org/8373029/diff/58004/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:1686: Label* is_string) {
Parameter is_string is not used. It can be removed. (also in ia32 and arm files)

[indutny, 2011-11-08 10:46:26]

fixed, thanks

[indutny, 2011-11-09 06:41:59]

(empty message, just to remind you about this issue)

[indutny, 2011-11-17 07:33:01]

Added comprehensive test for different type of clauses, tags, feedback and
optimizations.

[fschneider, 2011-11-17 10:05:32]

LGTM.

I like the new unit test! Thanks for adding it. I have one improvement so that
our type feedback guaranteed to be fresh for each test case. Other than that a
few minor comments. 

No need to upload a new version. I'll fix those before committing.

http://codereview.chromium.org/8373029/diff/55031/src/x64/lithium-codegen-x64.cc
File src/x64/lithium-codegen-x64.cc (right):

http://codereview.chromium.org/8373029/diff/55031/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:1686: 
Remove empty line to fix lint error.

http://codereview.chromium.org/8373029/diff/55031/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

http://codereview.chromium.org/8373029/diff/55031/src/x64/lithium-x64.cc#newc...
src/x64/lithium-x64.cc:1410: return
AssignEnvironment(MarkAsCall(DefineFixed(result, rax), instr));
Remove call to AssignEnvironment.

http://codereview.chromium.org/8373029/diff/63001/test/mjsunit/switch.js
File test/mjsunit/switch.js (right):

http://codereview.chromium.org/8373029/diff/63001/test/mjsunit/switch.js#newc...
test/mjsunit/switch.js:340: 
Global unique id for each generated test case needed:

var test_id = 0;

http://codereview.chromium.org/8373029/diff/63001/test/mjsunit/switch.js#newc...
test/mjsunit/switch.js:373: 'switch(tag) {' +
Here we need some kind of unique id so that the compilation cache does not
return a previous version of the unoptimized code and spoils our type feedback:

'"' + (test_id++) + '"; switch(tag) {' +

[indutny, 2011-11-17 10:29:04]

Thanks, fixed