Re: Threaded Interpreter

Optimizing Direct Threaded Code By Selective Inlining by Ian Piumarta,
Fabio Riccardi (1998 -
http://citeseer.ist.psu.edu/piumarta98optimizing.html) is a good
reference on threaded interpretation. The implementation described there
is heavily used by QEMU (http://fabrice.bellard.free.fr/qemu/) a popular
emulator. However, the tricks used to make QEMU work with GCC have
stopped working in GCC version 4.0+.


When implementing threaded interpreters you sometimes need to do it in a
type safe language such as Java. Obviously the goto *ip++ trick isn't
going to work. What you can do is take advantage of the compilation system:


class Interpreter {
        static Interpreter interpreters[NUM_INSTRUCTIONS];
        static {
                interpreters[NOP] = new Interpreter() {
                    Interpreter execute() {
                        IP += 4;
                        return interpreters[memory[IP]];
                      }
                };
                interpreters[ADD] = new Interpreter() {
                    Interpreter execute() {
                        IP += 4;
                        // do add...
                        return interpreters[memory[IP]];
                      }
                };
                // ...
          }
          // ...
          static void execute(Address IP) {
              Interpeter currentInterpreter = interpreters[memory[IP]];
              while(true) {
                  currentInterpreter = currentInterpreter.execute();
              }
          }
}


the idea behind threaded interpreters is that certain sequences of
instructions are more common. For example a compare is usual before a
branch. The threaded interpreter beats regular interpretation with a
switch statement as the branch predictor can predict where the next
instruction will be (there are lots of local de-multiplexes rather than
a big global de-multiplex at the head of the switch statement). With the
code above the result of the load at the end of the execute is
predictable and local to the current instruction - so the compilation
system can predict in the interpreter that branches will more often than
not come after compares. The net effect of this in a JVM system like
HotSpot or IBM's J9 is that the threaded implementation above will be
about 10% faster than a switch based implementation.


Regards,


Dr. Ian Rogers
The University of Manchester, UK

Return to the comp.compilers page.
Search the comp.compilers archives again.