Updated 2012-01-19 03:01:57 by RLE

George Peter Staplin: Jan 29, 2005 - As an experiment I decided to try to build a prototype for a Tcl VM that uses threaded code. Threaded code is an interesting concept that is fairly well documented on the web. Threaded code has been used in Ken Thompson's original B language, and Charles Moore's Forth.

This prototype converts a series of bytecodes into addresses. The addresses are then used to jump around in the threaded code.

Note: this is not related to POSIX threads, or concurrent programming techniques.

 #define TCL_TYPE_STRING 2
 #define TCL_TYPE_INT 4
 #define TCL_TYPE_DOUBLE 8

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

 #include "Tcl_Types.h"

 /* We define an operator table that is used with the symbols for bytecodes to lookup code addresses.
 struct {
  void *code;
 } ops[3];

 /* These are our bytecodes: */
 enum {

 /* These must match the .equ in vm.S */
 typedef struct {
  int type;
  int ref; /* 4 */
  int i; /* 8 */
  char *s; /* 12 */
 } Tcl_Obj;

 /* This is our execution token.  It stores a linear series of addresses. */
 typedef struct {
  caddr_t *start;
  /* Our cursor is the current position after the last address was appended. */
  caddr_t *cursor;
  size_t remaining;
  size_t total;
 } Tcl_Xt;

 extern void Tcl_InitOperators ();
 extern Tcl_Obj *Tcl_Run ();
 extern void Tcl_SetStringObj (Tcl_Obj *obj, char *str);

 /* bytecode to address */
 #define BCTOA(bc) ops[bc].code

 /* append code to xt */
 #define ACTOXT(xt,sym) \
  *(xt->cursor) = sym; \
  xt->cursor += 1

 void *Tcl_Alloc (size_t s) {
  void *r = malloc (s);

  if (NULL == r) {
   perror ("malloc");
   exit (EXIT_FAILURE);
  return r;

 void Tcl_Free (void *p) {
  free (p);

 void *Tcl_Realloc (void *old, size_t s) {
  void *new;

  new = realloc (old, s);

  if (NULL == new) {
   perror ("realloc");
   exit (EXIT_FAILURE);

  return new;

 void Tcl_EnlargeXt (Tcl_Xt *xt) {
  size_t new_size;
  size_t used;
  void *p;

  new_size = (xt->total * 2);

  used = (xt->remaining - xt->total);

  p = Tcl_Realloc (xt->start, new_size);

  xt->remaining = (new_size - used);
  xt->total = new_size;
  xt->cursor = (p + (xt->cursor - xt->start));
  xt->start = p;

 void Tcl_CompileExampleAdd (Tcl_Obj *objv[], Tcl_Xt *xt) {

  if ((sizeof (void *) * 7) < xt->remaining) {
   Tcl_EnlargeXt (xt);

  ACTOXT (xt, (caddr_t)objv[0]);
  ACTOXT (xt, (caddr_t)objv[1]);

  xt->remaining -= (sizeof (void *) * 7);

 Tcl_Obj *Tcl_NewObj (void) {
  Tcl_Obj *obj = Tcl_Alloc (sizeof (Tcl_Obj));

  obj->type = TCL_TYPE_STRING;
  obj->ref = 0;

  return obj;

 Tcl_Xt *Tcl_NewXt (void) {
  Tcl_Xt *xt = Tcl_Alloc (sizeof (Tcl_Xt));

  xt->total = xt->remaining = 2000;
  xt->cursor = xt->start = Tcl_Alloc (xt->remaining);

  return xt;

 void Tcl_SetStringObj (Tcl_Obj *obj, char *str) {
  obj->type = TCL_TYPE_STRING;
  obj->s = str;

 extern void test_convert (Tcl_Obj *obj);

 int main () {
  Tcl_Obj **objv;
  Tcl_Obj *result;
  Tcl_Xt *xt;

  Tcl_InitOperators (

  printf ("add_op code is %p\n", ops[TCL_ADD].code);
  printf ("push_op code is %p\n", ops[TCL_PUSH].code);
  printf ("return code is %p\n", ops[TCL_RETURN].code);

  objv = Tcl_Alloc (sizeof (Tcl_Obj *) * 2);
  objv[0] = Tcl_NewObj ();
  objv[1] = Tcl_NewObj ();

  Tcl_SetStringObj (objv[0], "255");
  Tcl_SetStringObj (objv[1], "456");

  xt = Tcl_NewXt ();

  Tcl_CompileExampleAdd (objv, xt);

 #if 0
  printf ("type before %d\n", objv[0]->type);
  test_convert (objv[1]);
  printf ("type after %d i %d\n", objv[0]->type, objv[0]->i);

  test_convert (objv[1]);
  return 0;

  result = Tcl_Run (xt->start);

  printf ("RESULT is %d\n", result->i);

  printf ("after return from Tcl_Run\n");

  return EXIT_SUCCESS;

 /* We may need to change the register allocation in the future, so we use these macros.

 #define ops esi

 #define tos edi

 #define vip edx

 #include "registers.h"
 #include "Tcl_Types.h"

 /* We cache the top-of-stack (TOS) in a register.
  * This is a technique that can result in better performance.

 .macro NEXT
  movl (%vip),%eax
  jmp *%eax

 .macro POP_INTO reg
  movl %tos,\reg
  movl (%ops),%tos
  addl $4,%ops

 .macro PUSH reg
  subl $4,%ops
  movl %tos,(%ops)
  movl \reg,%tos

  movl (%ops),%tos
  addl $4,%ops

 .macro SAVE_TOS
  subl $4,%ops
  movl %tos,(%ops)

 .macro VM_WORD word
  addl $4,%vip

 /* our Tcl_Obj structure layout */
 .equ type_offset, 0
 .equ ref_offset, 4
 .equ int_offset, 8
 .equ string_offset, 12

 .global Tcl_InitOperators
 .global Tcl_Run


  .comm operand_stack,2000

 .section .rodata
  emit_hex_fmt: .string "HEX 0x%x\n"
  emit_invalid_integer: .string "This isn't an integer string.\n"
  emit_string_fmt: .string "DEBUG STRING %s\n"
  emit_ptr_fmt: .string "ptr %p\n"
  emit_internal_error: .string "internal error\n"

 /**** UTILITY CODE ****/

 /* convert the integer in the Tcl_Obj stored in %eax
  (saving any registers that could be clobbered)

  We use:

   %eax result
   %cl low bits for the character
   %esi our offset into the string
   %edi our Tcl_Obj (after we move it from %eax)
   %edx for multiplication

  pushl %edi
  pushl %esi
  pushl %ecx
  pushl %edx

  movl %eax,%edi
  movl string_offset(%eax),%esi

  /* our initial value */
  movl $0,%eax

   /* clear our temporary register's high bits */
   movl $0,%ecx
   movb (%esi),%cl

   cmpb $0,%cl
   je got_zero_byte

   /* %eax * 10 */
   movl $10,%edx
   mull %edx

   cmpb $'0',%cl
   jl not_integer
   cmpb $'9',%cl
   jg not_integer

   subb $'0',%cl
   addl %ecx,%eax

   /* advance to the next char */
   addl $1,%esi
   jmp repeat


   /* save the result in our Tcl_Obj's memory */
   movl $TCL_TYPE_INT,type_offset(%edi)
   movl %eax,int_offset(%edi)
   movl %edi,%eax

   /* now restore the registers in reverse order */
   popl %edx
   popl %ecx
   popl %esi
   popl %edi

   pushl $emit_invalid_integer
   call printf
   addl $4,%esp
   /* XXX lovely error handling.  I think in the final version we will use a longjmp. */
   call abort

 /**** ENTRY POINTS ****/

  movl 4(%esp),%eax
  movl $add_op,(%eax)

  movl 8(%esp),%eax
  movl $push_op,(%eax)

  movl 12(%esp),%eax
  movl $exit_Tcl_Run,(%eax)


 /* Tcl_Run (start)
  movl 4(%esp),%vip
  movl $operand_stack,%ops
  /* our stack grows downward */
  addl $2000,%ops



   /* return our Tcl_Obj result in %eax */
   POP_INTO %eax

 .global test_convert
  movl 4(%esp),%eax
  call convert_to_int

  pushl int_offset(%eax)
  pushl $emit_hex_fmt
  call printf
  addl $8,%esp


  pushl %eax
  pushl $emit_hex_fmt
  call printf
  addl $8,%esp

 /**** OPERATORS ****/

 /* The idea is that we have various VM words that get threaded together.
  * Each word ends with a NEXT macro that expands to jump to the next address.

 /* add $a $b */
 VM_WORD add_op
  /* convert object $b to int if needed */
  POP_INTO %eax
  cmpl $TCL_TYPE_INT,type_offset(%eax)
  je 1f
   call convert_to_int

  /* save the Tcl_Obj for $b */
  pushl %eax

  POP_INTO %eax
  cmpl $TCL_TYPE_INT,type_offset(%eax)
  je 1f
   call convert_to_int

  movl int_offset(%eax),%ecx
  popl %eax
  addl int_offset(%eax),%ecx

  /* Now we save the critical registers that the C code will possibly clobber. */
  pushl %ecx
  pushl %tos
  pushl %vip
  pushl %ops

  call Tcl_NewObj

  popl %ops
  popl %vip
  popl %tos
  popl %ecx

  movl %ecx,int_offset(%eax)
  movl $TCL_TYPE_INT,type_offset(%eax)

  PUSH %eax


 VM_WORD push_op
  /* set TOS to the Tcl_Obj */
  movl (%vip),%tos
  addl $4,%vip



1. Ken Thompson's B language (the precursor to C): http://cm.bell-labs.com/cm/cs/who/dmr/kbman.html

2. Threaded Code Definition at FOLDOC: http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?query=threaded+code

3. My revisions of this code (tcltcvm): http://www.xmission.com/~georgeps/engineering/prototype/

PWQ 31 Jan 05, If the bytecode interpreter was implemented with call threading then it would be easier to add new byte codes. From C it is not easy to implement direct or indirect threading, I wonder how many takers there will be to reimplement the interpreter for new CPU's in assembly.

George Peter Staplin: Jan 30, 2005 - I've examined several implementations of high performance threaded code that are mainly written in C. Some rely on allocating a global register as a virtual instruction pointer (which may not always work with every library, unless the libraries are compiled for this, and the compiler supports this). Others use the gcc feature of labels as values (&& on a label to get a void * for goto *ptr;).

I've been pondering doing an experiment with the Tcl sources. It would consist of implementing enough of the VM instructions in threaded code (written in assembly) to run small test programs. I would like to retain the bytecode code branch for platforms that don't have the assembly.

PWQ, Ideally the functions would call NEXT rather than returning to a main loop, gcc supports function attributes such as naked and noreturn but they are not supported on all targets. The scoping rules for C don't allow functions direct access to their caller variables even if called via goto *ptr (no uplevel equiv). This means passing around a structure pointer for all the state information.

Still this technique may be more efficient than the massive switch statement approach. Plus it can be extended by adding more function pointers to the jump table.

atp: According to the papers by M. Anton Ertl and David Gregg, e.g., "The Structure and Performance of EFFICIENT Interpreters", "switch threading" - aka, the "massive switch statement approach" - is pretty much always slower than direct or indirect threading.

The advantage of the switch statment approach is that it is portable across non-gcc compilers, while doing direct or indirect threading typically means either using gcc's "C Labels as Values" extension to Standard C, or some lower level technique, like assembler.

http://www.complang.tuwien.ac.at/forth/threaded-code.html http://www.complang.tuwien.ac.at/projects/interpreters.html

The Tcl Core Team appears to be aware of this, as this 2002 paper does discuss threaded code as a future possibility for Tcl:

"Tcl bytecode optimization: some experiences" by Kevin Kenny, Miguel Sofer, Jeffrey Hobbs http://aspn.activestate.com/ASPN/Tcl/TclConferencePapers2002/Tcl2002papers/kenny-bytecode/paperKBK.html