Deoptimize non-smi switch cases if they are reached.

Deoptimize non-smi switch cases if they are reached.

This way if the type oracle says an unreachable clause has a non-smi
type, we can still emit optimized code instead of doing an early
bailout.

This change depends of Florian's r5970.

Committed: http://code.google.com/p/v8/source/detail?r=6037

[fschneider, 2010-12-14 16:03:17]

It already looks pretty good - the only issue I have is that it is maybe too
restrictive (see comments below). How hard would it be to combine it with a more
generic fall-back?

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

http://codereview.chromium.org/5812005/diff/1/src/hydrogen.cc#newcode2656
src/hydrogen.cc:2656: last_false_block->Finish(new HDeoptimize);
It is safe to deoptimize after the last smi-compare, but it seems overly
restricting, if there are reachable smi-compares afterwards. e.g.

switch(x) {
  case 0: A(); break;
  case 1: B(); break;
  default: C(); break;  
}

If the inputs are only 0 and 2 we would deoptimize after the first smi-compare
with 0, and not optimize the default-clause.

http://codereview.chromium.org/5812005/diff/1/src/hydrogen.cc#newcode2681
src/hydrogen.cc:2681:
compare_graphs.at(i)->exit_block()->end()->FirstSuccessor();
My suggestion would be to insert HDeoptimize in the empty-block here for all
non-smi-compares. It's not as compact as your approach, but it handles all
cases.

Maybe you can fall back to the more generic solution if the smi-compares are not
a prefix-set.

[Vitaly Repeshko, 2010-12-14 19:16:58]

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

http://codereview.chromium.org/5812005/diff/1/src/hydrogen.cc#newcode2656
src/hydrogen.cc:2656: last_false_block->Finish(new HDeoptimize);
On 2010/12/14 16:03:17, fschneider wrote:
> It is safe to deoptimize after the last smi-compare, but it seems overly
> restricting, if there are reachable smi-compares afterwards. e.g.
> 
> switch(x) {
>   case 0: A(); break;
>   case 1: B(); break;
>   default: C(); break;  
> }
> 
> If the inputs are only 0 and 2 we would deoptimize after the first smi-compare
> with 0, and not optimize the default-clause.

When 2 is given we have to test all comparisons so they all will be reached
(provided your type feedback change is in), and we'll get the expected optimized
code. As long as the full codegen emits case comparisons in sequence without
trying to be smart, we won't get into the situation you describe.

[fschneider, 2010-12-15 12:10:16]

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

http://codereview.chromium.org/5812005/diff/1/src/hydrogen.cc#newcode2577
src/hydrogen.cc:2577: AddSimulate(stmt->tag()->id());
I think that if the stmt->tag() expression has a side effect VisitForValue will
insert a simulate already, and we should avoid having  two simulates with the
same id.

Maybe we can avoid explicitly calling AddSimulate here, since we would just
deoptimize to the last instruction that has a side effect.

[Vitaly Repeshko, 2010-12-15 15:22:16]

Please take another look.


Thanks,
Vitaly

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

http://codereview.chromium.org/5812005/diff/1/src/hydrogen.cc#newcode2577
src/hydrogen.cc:2577: AddSimulate(stmt->tag()->id());
On 2010/12/15 12:10:16, fschneider wrote:
> I think that if the stmt->tag() expression has a side effect VisitForValue
will
> insert a simulate already, and we should avoid having  two simulates with the
> same id.
> 
> Maybe we can avoid explicitly calling AddSimulate here, since we would just
> deoptimize to the last instruction that has a side effect.

As discussed by IM an extra simulate is needed here because of dead phi
elimination. Added a todo.

[fschneider, 2010-12-15 16:12:13]

LGTM.

Maybe we can avoid the problem with OSR by checking all clauses if are able to
compile them (only SmiLiterals as labels) earlier. See my comment below -
Otherwise lgtm!

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

http://codereview.chromium.org/5812005/diff/11001/src/hydrogen.cc#newcode2595
src/hydrogen.cc:2595: }
Does it make sense to check if all clauses have a SmiLiteral as the clause-label
before this loop? Otherwise we may optimize a function where we will
unconditionally deoptimize every time.

Maybe this would also avoid the problem with OSR?

[Vitaly Repeshko, 2010-12-15 17:14:39]

Landed with an extra check on the number of smi compares. We can't completely
avoid the OSR issue, but we can avoid generating totally useless switch
statements.

Thanks for the review!


-- Vitaly