[Python-Dev] An obscene computed goto bytecode hack for "switch" :)

[Phillip J. Eby]

For folks contemplating what opcodes might need to be added to implement a 
"switch" statement, it turns out that there is a "clever way" (i.e. a 
filthy hack) to implement computed jumps in Python bytecode, using 
WHY_CONTINUE and END_FINALLY.

I discovered this rather by accident, while working on my BytecodeAssembler 
package: I was adding validation code to minimize the likelihood of 
generating incorrect code for blocks and loops, and so I was reading 
ceval.c to make sure I knew how those bytecodes worked.

And at some point it dawned on me that an END_FINALLY opcode that sees 
WHY_FINALLY on top of the stack *is actually a computed goto*!  It has to 
be inside a SETUP_LOOP/POP_BLOCK pair, but apart from that it's quite 
straightforward.

So, taking the following example code as a basis for the input:

     def foo(x):
         switch x:
             case 1: return 42
             case 2: return 'foo'
             else:   return 27

I created a proof-of-concept implementation that generated the following 
bytecode for the function:

       0           0 SETUP_LOOP              36 (to 39)
                   3 LOAD_CONST               1 (<...method get of dict...>)
                   6 LOAD_FAST                0 (x)
                   9 CALL_FUNCTION            1

                  12 JUMP_IF_FALSE           18 (to 33)
                  15 LOAD_CONST               2 (...)
                  18 END_FINALLY

                  19 LOAD_CONST               3 (42)
                  22 RETURN_VALUE
                  23 JUMP_FORWARD            12 (to 38)

                  26 LOAD_CONST               4 ('foo')
                  29 RETURN_VALUE
                  30 JUMP_FORWARD             5 (to 38)

             >>   33 POP_TOP
                  34 LOAD_CONST               5 (27)
                  37 RETURN_VALUE

             >>   38 POP_BLOCK

             >>   39 LOAD_CONST               0 (None)
                  42 RETURN_VALUE

The code begins with a SETUP_LOOP, so that our pseudo-continues will 
work.  As a pleasant side-effect, any BREAK_LOOP operations in any of the 
suites will exit the entire switch block, jumping to offset 39 and the 
function exit.

At offset 3, I load the 'get' method of the switching dictionary as a 
constant -- this was simpler for my proof-of-concept, but a production 
version should probably load the dictionary and then get its 'get' method, 
because methods aren't marshallable and the above code therefore can't be 
saved in a .pyc file.  The remaining code up to offset 12 does a dictionary 
lookup, defaulting to None if the value of the switch expression isn't found.

At offset 12, I check if the jump target is false, and if so I assume it's 
None, and  jump ahead to the "else" suite.  If it's true, I load a constant 
value equal to the correct value of WHY_CONTINUE for the current Python 
version and fall through to the END_FINALLY.  So the END_FINALLY then pops 
WHY_CONTINUE and the jump target, jumping forward to the correct "case" branch.

The code that follows is then a series of "case" suites, each ending with a 
JUMP_FORWARD to the POP_BLOCK that ends the "loop".  In this case, however, 
those jumps are never actually taken, but if execution "fell out" of any of 
the cases, they would proceed to the end this way.

Anyway, the above function actually *runs* in any version of Python back to 
2.3, as long as the LOAD_CONST at offset 15 uses the right value of 
WHY_CONTINUE for that Python version.  Older Python versions are of course 
not going to have a "switch" statement, but the reason I'm excited about 
this is that I've been wishing for some way to branch within a function in 
order to create fast jump tables for generic functions.  This is pretty 
much what the doctor ordered.

One thing I'm curious about, if there are any PyPy folks listening: will 
tricks like this drive PyPy or Psyco insane?  :)  It's more than idle 
curiosity, as one of my goals for my next generic function system is that 
it should generate bytecode that's usable by PyPy and Psyco for 
optimization or translation purposes.