re: Threaded code

Another method for obtaining threaded byte code for an interpreter
is to edit the assembler output of a big switch
rather than editing the prologue and epilogue off functions calls.


You don't need gcc, global vars in registers, works with smart and
dumb compilers, and all optimization can be turned on.


For example:


This C routine executes (unthreaded) byte code for an interpreter
that can add, subtract and print.


#define HALT 0
#define PUSH 1
#define ADD 2
#define SUB 3
#define PRINT 4


static int stack[32] ;


void execute(code_ptr)
    register int *code_ptr ;
{
    register int *stack_ptr = stack - 1 ;




    while ( 1 )
    {
        switch( *code_ptr++ )
        {
            case HALT : return ;
            case PUSH :
* ++ stack_ptr = *code_ptr++ ;
break ;


            case ADD :
stack_ptr-- ;
*stack_ptr += stack_ptr[1] ;
break ;


            case SUB :
stack_ptr-- ;
*stack_ptr -= stack_ptr[1] ;
break ;


            case PRINT :
                          printf("%d\n", *stack_ptr--);
break ;
          }
    }
}


-------------------------------------------------------


to interpret 2 + (3 - 4)


the front end "compiles" in int code[]


PUSH, 2, PUSH, 3, PUSH, 4, SUB, ADD, PRINT, HALT


and calls execute(code).


------------------------------------------------------


The difference between this and the threaded code discussed over
the last few weeks is the switch gets compiled as


            jmp TABLE[ *code_ptr++ ]


where TABLE is the jump table generated by the compiler which holds
the addresses of the case labels.


With threading, the transitions between functions become


            jmp *code_ptr++




but this is easy to get by editing the assembler output to
export the case label and recode the switch.


--------------------------------------------------


For example on a SPARC:


code_ptr is %o0
stack_ptr is %i5




.....
! case PUSH
L77004:
ld [%i0],%o1
inc 4,%i5
inc 4,%i0
b L77008
st %o1,[%i5]


.....


! the switch, doesn't change structure
! as you add new op codes


L77008:
mov %i0,%i4
ld [%i4],%i4
inc 4,%i0
cmp %i4,4
bgu L77008
sll %i4,2,%i4
sethi %hi(L2000000),%o1
or %o1,%lo(L2000000),%o1 ! [internal]
ld [%i4+%o1],%o0
jmp %o0
nop
L2000000: ! the jump TABLE
.word L77003 ! HALT etc
.word L77004
.word L77005
.word L77006
.word L77007




-------------------------------------------
modify by adding global labels and edit the switch






.....
! case PUSH
_push :
L77004:
ld [%i0],%o1
inc 4,%i5
inc 4,%i0
b L77008
st %o1,[%i5]


.....


! the edited switch
L77008:
mov %i0,%i4
ld [%i4],%i4
inc 4,%i0
jmp %i4
nop
                     ! remove TABLE


-------------------------------------------


For another example on an Intel 8088


stack_ptr is si
code_ptr is di


      ; while ( 1 )
      ; {
      ; switch( *code_ptr++ )
      ;
@1@50:
mov bx,di
inc di
inc di
mov bx,word ptr [bx]
cmp bx,3
ja short @1@50
shl bx,1
jmp word ptr cs:@1@C738[bx]




@1@122:
      ;
      ; case PUSH :
      ; * ++ stack_ptr = *code_ptr++ ;
      ;
inc si
inc si
mov ax,word ptr [di]
mov word ptr [si],ax
inc di
inc di
      ;
      ; break ;
      ;
jmp short @1@50
      ;


....


@1@C738 label word ; jump TABLE
dw @1@194 ; HALT
dw @1@122 ; PUSH etc
dw @1@146


....


------------------------------------------------


edited the jump can be computed inline


      ; while ( 1 )
      ; {
      ; switch( *code_ptr++ )
      ;
@1@50: ; switch code is replaced by code only executed once


inc di
inc di
jmp [di-2]


.....


_push :
@1@122:
      ;
      ; case PUSH :
      ; * ++ stack_ptr = *code_ptr++ ;
      ;
inc si
inc si
mov ax,word ptr [di]
mov word ptr [si],ax
inc di
inc di
      ;
      ; break ;
      ;
inc di ; jmp to *code_ptr++ inline
inc di
jmp [di-2]
      ;
....


----------------------------------------------


the "front end" has defines


typedef void (*TCODE)() ;


extern void halt(), push(), add(), sub(), print() ;


TCODE code[CODESIZE] ;


in the array code[], the front end compiles




push, 2, push, 3, push, 4, sub, add, print, halt


and calls execute(code).




--
Mike Brennan
brennan@bcsaic.boeing.com
--

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