Content deleted Content added
m ref name fixed WP:REFNAME |
m Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags |
||
Line 52:
To save space, programmers squeezed the lists of subroutine calls into simple lists of subroutine addresses, and used a small loop to call each subroutine in turn. For example, the following pseudocode uses this technique to add two numbers A and B. In the example, the list is labeled '''thread''' and a variable '''ip''' (Instruction Pointer) tracks our place within the list. Another variable '''sp''' (Stack Pointer) contains an address elsewhere in memory that is available to hold a value temporarily.
<
start:
ip = &thread // points to the address '&pushA', not the textual label 'thread'
Line 72:
*sp++ = *--sp + addend // copy another value out of stack, add, copy sum into stack
jump top
</syntaxhighlight>
<!--In this case, decoding the [[bytecode]]s is performed once, during program compilation or program load, so it is not repeated each time an instruction is executed. This can save much time and space when decode and dispatch overhead is large compared to the execution cost.
Line 82:
The calling loop at <code>top</code> is so simple that it can be repeated inline at the end of each subroutine. Control now jumps once, from the end of a subroutine to the start of another, instead of jumping twice via <code>top</code>. For example:
<
start:
ip = &thread // ip points to &pushA (which points to the first instruction of pushA)
Line 101:
*sp++ = *--sp + addend // copy another value out of stack, add, copy sum into stack
jump *ip++
</syntaxhighlight>
This is called '''direct threaded code''' (DTC). Although the technique is older, the first widely circulated use of the term "threaded code" is probably James R. Bell's 1973 article "Threaded Code".<ref>{{cite journal|last=Bell|first=James R.|title=Threaded code|journal=Communications of the ACM|year=1973|volume=16|issue=6|pages=370–372|doi=10.1145/362248.362270}}</ref>
Line 117:
An example of a stack machine might execute the sequence "push A, push B, add". That might be translated to the following thread and routines, where <code>ip</code> is initialized to the address labeled <code>thread</code> (i.e., the address where <code>&pushA</code> is stored).
<
start:
ip = &thread // ip points to &pushA (which points to the first instruction of pushA)
Line 136:
*sp++ = *--sp + addend
jump *ip++
</syntaxhighlight>
Alternatively, operands may be included in the thread. This can remove some indirection needed above, but makes the thread larger:
<
start:
ip = &thread
Line 158:
*sp++ = *--sp + addend
jump *ip++
</syntaxhighlight>
===Indirect threading===
Line 165:
For example, if the goal is to execute "push A, push B, add", the following might be used. Here, <code>ip</code> is initialized to address <code>&thread</code>, each code fragment (<code>push</code>, <code>add</code>) is found by double-indirecting through <code>ip</code> and an indirect block; and any operands to the fragment are found in the indirect block following the fragment's address. This requires keeping the ''current'' subroutine in <code>ip</code>, unlike all previous examples where it contained the ''next'' subroutine to be called.
<
start:
ip = &thread // points to '&i_pushA'
Line 189:
*sp++ = *--sp + addend
jump *(*++ip)
</syntaxhighlight>
===Subroutine threading===
Line 198:
As an example of call threading for "push A, push B, add":
<
thread:
call pushA
Line 214:
*sp++ = *--sp + addend
ret
</syntaxhighlight>
===Token threading===
Line 221:
A common approach, historically, is bytecode, which uses 8-bit opcodes and, often, a stack-based virtual machine. A typical interpreter is known as a "[[decode and dispatch interpreter]]", and follows the form:
<
start:
vpc = &thread
Line 246:
*sp++ = *--sp + addend
jump top
</syntaxhighlight>
If the virtual machine uses only byte-size instructions, <code>decode()</code> is simply a fetch from <code>thread</code>, but often there are commonly used 1-byte instructions plus some less-common multibyte instructions (see [[complex instruction set computer]]), in which case <code>decode()</code> is more complex. The decoding of single byte opcodes can be very simply and efficiently handled by a branch table using the opcode directly as an index.
Line 298:
In all interpreters, a branch simply changes the thread pointer (<code>ip</code> above). A conditional branch, to jump if the top-of-stack value is zero, might be encoded as follows. Note that <code>&thread[123]</code> is the ___location to which to jump, not the address of a handler. So, it must be skipped (<code>ip++</code>) regardless of whether the branch is taken.
<
thread:
...
Line 309:
ip = tmp
jump *ip++
</syntaxhighlight>
==Common amenities==
Line 326:
In an indirect-threaded virtual machine, the one given here, the operations are:
<
next:
*ip++ -> w
Line 337:
*--rp -> ip
next
</syntaxhighlight>
This is perhaps{{citation needed|date=July 2016}} the simplest and fastest interpreter or virtual machine.
| |||