[Python-Dev] An obscene computed goto bytecode hack for "switch" :)
Phillip J. Eby
pje at telecommunity.com
Sat Jun 17 04:01:05 CEST 2006
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
So, taking the following example code as a basis for the input:
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 (...)
19 LOAD_CONST 3 (42)
23 JUMP_FORWARD 12 (to 38)
26 LOAD_CONST 4 ('foo')
30 JUMP_FORWARD 5 (to 38)
>> 33 POP_TOP
34 LOAD_CONST 5 (27)
>> 38 POP_BLOCK
>> 39 LOAD_CONST 0 (None)
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
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.
More information about the Python-Dev