Re: Emulator Project Question

[Colin Klipsch <klipsch@mail630.gsfc.nasa.gov>]

Paul Schlyter wrote:

> In article <EjUP7.441$n%2.201954@news.uswest.net>,
> Steve Mentzer <steve@crackershack.com> wrote:
> 
> > If you could clearly define which bytes were "code" and which were "Data",
> > performing assembly conversion at runtime wouldn't be so difficult.
> >
> > The problem is that you cannot "translate as you go",
> 
> Why not?

Self-modifying code is the biggest headache, which you yourself hint
at later by calling it "tricky".  (Quite an understatement!)

Steve M. also notes programs that implement their own "virtual memory"
(swapping in chunks of code on demand), which further spoils, or at
least complicates, any proposed JITC algorithm in an Apple II
emulator.  What do you do with a block of bytes just loaded from disk?
 Always translate it, assuming it might be executed?  Or just
sometimes translate it?  There's no general way to know whether the
block holds executable code or data: not by its content, not by the
file it comes from, not by the position in that file, and not by the
block's location in memory.

Furthermore, newly arrived blocks might be a mixture of code and data,
and there's no good way to know where one ends and the other begins. 
(Example: the ProDOS boot block is loaded into the address range
$800-9FF, but the code is entered at location $801.  Many of the
block's bytes are also data, like character strings, sprinkled in
between sections of code.)

Another lesser headache is that the Apple II has multiple physical
banks of memory that can (at different times) be mapped to the same
physical addresses -- and in fact, the mapping for memory reads is in
general distinct from the mapping for writes.  The read-mapping is the
one that matters for execution, of course.

This means for example that a simple-looking "JMP $E000" might jump to
any one of several different physical locations, depending on the
current states of the memory banks, states which in general won't be
known until the JMP instruction is executed (though in many specific
cases they might be).

Presumably you could handle this by keeping your caches of translated
instructions in some sort of data structure that mimics the Apple II's
memory banks.  Then, when you hit that "JMP $E000", you'll know the
right destination in your trasnlated code.

But then, when an instruction later writes to $E000, how do you know
whether to care?  (How do you know whether code or data was written there?)

> Some Java interpreters do precisely that: they translate
> the J-code into native machine instructions as they go (it's called
> JIT compilation where JIT means "Just In Time").  With linear code
> this will of course yield no gain in execution speed at all, but if
> you enter a loop there'll be a tremendeous gain: the loop is
> translated once, and then the loop is executed in native code.

There seems little advantage in Java's JITC unless the compiled
routine is likely to be executed more than once, regardless of any
loops.  After all, the cost of translating the bytecodes, and saving
the translated version, is approximately the cost of interpreting the
bytecodes directly.  This is my impression at least, having just
scanned the JVM architecture specs; the bytecodes represent very
simple operations on a stack-based machine.  (True?)

> So why can't this technique be applied to 6502 machine code as well?
> BTW it would probably be the only secure way to distinguish code
> from data: what's executed is, by definition, code.

You don't know which memory bytes count as opcodes until the CPU finds
itself at a particular address.  You could perhaps then try to scan
for "basic blocks" (in the sense of what a compiler analyzes); but
self-modifying code can invalidate your translated instructions, over
and over again, sometimes inside a tight loop.  Unfortunately, many
Apple II programs were written in this way, enough that the phenomenon
cannot be dismissed as a "perverse" case to be ignored.

> > and you have no guaranteed method of identifying which is code
> > and which is data.

> Yes you have - by "following the code" so to say.  But it'll be tricky
> if some bytes are used for code *and* data, particularly if the "data"
> is changed, i.e. self-modifying code.

That probably doesn't happen much inside real-world Apple II programs,
admittedly.  The normal case -- normal anyway among programs that
modify their own code, but are otherwise sensible -- is that some of
their instructions modify other instructions to become yet other
instructions.  (Ya follow that?)  So, addresses that contain code (or
data) at one point are often still holding code (or data) after an
instruction-modifying-instruction, or indeed after most memory writes.

Often, that is, but not always.  Eventually, for any address in the
Apple II's memory, this will likely change.

Eventually, the CPU will start writing bytes to various addresses --
bytes computed inline, or bytes read in from disk, or from elsewhere
-- and there is no easy way to tell whether those bytes represent
instructions that the CPU will later find itself executing, or whether
they are just data bytes.  You won't really know until the CPU finds
itself among them, trying to execute them.

> > The fastest method so far has been a simple jump table. Define an
> > array of function pointers that is 255 bytes long.
> 
> I think you mean 256, not 255: remember that the 1-byte opcode of the
> 6502 has 256 possible values.

I'll bet Steve is kicking himself over that typo.

> > Each element points to a function that handles that particular opcode.
> > Simply do a array[opcodenumber]; and you can call the emulated CPU.

Actually, I recommend using a dense "switch" statement, not a function
pointer table.  A *dense* (all case values from 0 and N are present,
even if some of them do nothing) and *large* (N is at least ten or so;
256 is certainly plenty) switch statement will be optimized into a
relative branch using an inline lookup table, indexed by the switch
expression.  Any C/C++ compiler with the sense that God gave a kitten
will do this, and you can avoid the function call overhead that you
are otherwise *very* likely to incur.

What specifically do I mean by function call overhead?  On most
architectures, a function call involves the pushing of several
registers onto the stack, the preparation of the activation record and
return address, and then the actual jump.  Either the caller or the
callee or both might save and restore registers on entry and exit. 
Some of these steps might be omitted, if the compiler can determine it
doesn't need them -- if the called function is a "leaf" function for
example, or if it takes no parameters, or uses no local variables. 
However, calling a function through a lookup table defeats many of
these insights, and the compiler will default to the safe, but more
costly, behavior.  (The compiler won't be aware that each function,
pointed to by FuncTable[i], is a leaf function, even if you wrote them
all that way.  Therefore, it will generate code for a fully general
function call on the pointer.  It has to treat every FuncTable[i]
entry the same, after all.)

Usually no one cares about all this, because in typical programs a
function's overhead cost is negligible compared to the cost of the
function's body.  But here, we're discussing the writing of an
emulator in C/C++, and the "functions" are implementations of
individual 6502 opcodes.  Most opcodes, such as INX, involve little
more than a read, an easy computation, and a write or two.  (In
addition to the new X value, you have to adjust the P register, or
some representation of it.)  Invoking a function to accomplish this
tiny operation will probably at least double the time cost of the
opcode.  Do this for all your opcodes, and your emulator is wasting a
lot of run-time.

Mind you, on today's processors, which are so much faster than the
1-MHz 6502 inside the Apple II, you can get away with a lot of casual
attitude.  For that very reason however, I wouldn't bother with (A)
writing any part of the emulator in host-native machine language, if
your host is any computer made since 1995, or (B) writing a JIT
compiler for 6502-to-native machine code.

The gains are little; the headaches, enormous.


-- Colin K.
  (author of Catakig, an Apple II emulator)