[Webkit-unassigned] [Bug 104638] Support op_switch_imm bytecode on DFG.

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=104638





--- Comment #6 from Filip Pizlo <fpizlo at apple.com>  2012-12-12 13:03:58 PST ---
(In reply to comment #5)
> (In reply to comment #2)
> Certainly, many comparisons for large switch statements perform slower then jump table. ​I don't like the idea of additional phase which will only expand switch into blocks. This will at least perform slower then processing op_switch in DFGBytecodeParser.

This is a blanket assertion with zero evidence.  We don't tend to make architectural decisions based on zero evidence.

Also, we rarely use compilation speed as the primary guide for deciding how to implement optimizations.  There are three considerations when writing a compiler:

1) How fast the code that it generates runs.

2) How maintainable to compiler is.

3) How fast the compiler runs.

We prioritize in exactly that order: speed of generated code comes first, maintainability second, and compiler run-time third.  The idea that you should cram everything into the bytecode parser makes sense only if you cared more about (3) than (2).

But wait, that's not all.  Doing all Switch lowering in the bytecode parser prevents you from being able to choose between a lookup switch (i.e. decompose to branches) and a table switch (i.e. use a jump table) based on information gleaned from prior optimizations.  Remember, the bytecode parser has close to zero knowledge about the behavior of the program beyond just "peephole" profiling on a few key ops (heap accesses and calls mainly).  But later in the compiler we aggregate the profiling data to generate much more information, and we also at that point generate much stronger proofs about the nature of values.  Hence leaving a Switch alone until more information is available is generally a good long-term architectural strategy.

> Speaking about using Switch DFG node all the way through to the backend — it seems complicated to implement processing such a node in all other phases. I see a lot of code that assumes each basic block in control-flow graph have edges to one or two other blocks (jump or branch).

Then you should fix that code as part of your patch.

> Basic block with switch node may have up to 1000 outgoing edges. Is it possible to implement such support or there is any logic which prevents creating blocks with more than two exits?

The only reason why we have logic that assumes that blocks have at most two outgoing edges is that currently our only true "control" construct is Branch.  But there isn't any code that really relies on this property.  In particular, if you took all of the places that switch on the NodeType of a block terminal and do different things for Jump and Branch, and added a Switch case, then you wouldn't really be breaking anything.

This of course assumes that you're not going to be implementing sparse conditional constant propagation on Switch statements in the first go.  That's a sensible thing to not do, since the sparse conditional component is really only there for conditional loop branches.  You're unlikely to have a Switch statement where one of the cases acts as a loop back-edge while the other cases act as fall-through forward edges.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.