(if you don't believe me, go and take a good long hard look at the Intel
docs, and imagine how you would go about writing an interpreter for all
this stuff...).

I started initially trying this, but soon found it unworkable.

On Sun, 1 Nov 2009 12:59:06 -0700, "BGB / cr88192"
cr88192 at (no spam) hotmail.com> wrote:


"Richard Harter" <cri at (no spam) tiac.net> wrote in message
news:4aedcfb0.958856406 at (no spam) text.giganews.com...
On Sat, 31 Oct 2009 23:46:13 -0700, "BGB / cr88192"
cr88192 at (no spam) hotmail.com> wrote:
[snip]


Offhand the above sounds ugly. I don't know many op codes you
are using but I expect that it most it is a few hundred.

errm...

the x86 ISA has a bit more than this, closer to around 1,800 (core integer
ops, x87, SSE/SSE2/..., and partial AVX). full AVX and SSE5 might push it
a
bit over 2000.

note that this is actual opcodes, not nmonics, where x86 likes using a
number of different opcodes with the same nmonic, although in my list
there
are still around 800 nmonics...

as for there being only a few hundred opcodes, in nearly any other
bytecode
this would probably be the case, but is not so much the case with x86...

That's still not all that bad, but it is less than pleasant.

the interpreter does not at present handle the full set though...


but, the hash is not used for opcode lookup/decoding, rather it is used
for
grabbing already decoded instructions from a cache (which is based on
memory
address).

(this is because instruction decoding is fairly expensive, and so is not
done inline, and when instructions are actually decoded, they are
converted
from an in-memory opcode, to a struct-based representation, which is what
is
fetched here by the hash lookup).

so, it serves a role similar to that of the L1 cache.

I'm a little confused here. Are we just talking about opcodes
(decoded or not) or are we talking about full instructions. If
we are only talking about opcodes then everything can be
precomputed except an opcode->index mapping.

The
hash function you use is relatively expensive. Using a hash
table at all is relatively expensive. A trie might be cheaper or
possibly a perfect hash. Then there is the question of why you
are using a switch at all. If the op-code lookup yields an
index, why aren't you using it as an index into a table that
contains the pointer to the action function and the op-code
struct?


the hash table fetches the (already decoded) opcode struct, and the switch
is used to have the interpreter actually so something.

Step:
hash EIP address (actually: EIP+CS.Base);
try fetch decoded opcode:
ExecOpcode.
fail:
set up hash entry;
decode opcode at EIP into hash;
ExecOpcode.

ExecOpcode:
switch(op->type) //not exact, but close enough
case Basic: ExecOpcodeBasic(); break;
case Reg: ExecOpcodeReg(); break;
case RM: ExecOpcodeRM(); break;
case RegRM: ExecOpcodeRegRM(); break;
case RMReg: ExecOpcodeRMReg(); break;
case Imm: ExecOpcodeImm(); break;
case RegImm: ExecOpcodeRegImm(); break;
case RMImm: ExecOpcodeRMImm(); break;
...

...
ExecOpcodeRegRM:
resolve RM, ...
switch(op->opnum)
case ADC: ...
case ADD: ...
case AND: ...
case BSF: ...
case BSR: ...
...

Something isn't quite right here. In the switch ExecOpcodeRegRM
is a function; in the code immediately after it is a label.

One problem with your switches is that they are big. Now a good
compiler can and should optimize a compact set of cases into a
jump table. However all bets are off if there are holes or if
the cases are sequential. If doesn't produce a jump table it
probably defaults to sequential if/then/else chains which are
deadly for large switches. Thus in your ExecOpCode switch you
really want a table of function pointers indexed by op->type so
that the switch becomes something like

optypes[op->type]();

The op types you use for the table have to be approximately
sequential integers. If Intel doesn't give you the right kind of
numbers to use as an index, create an index field in your struct.
You can even have holes in the indexing - just fill the holes
with pointers to an error function.

All of this is fairly standard. There probably is some good
reason why you aren't doing this, but it isn't obvious.

in all, it is a fairly "heavyweight" interpreter, but alas, x86 is also a
fairly heavy ISA...


Mind you, there might be very good reasons for doing what you are
doing. I don't have access to your code. Still, it sounds as
though your code is cumbersome.


kind of, but it could be a whole lot worse...


how would you approach something like x86?...

hopefully not by suggesting a huge switch to dispatch for every possible
opcode byte/prefix/... and then re-enter for following bytes. many opcodes
are long (2/3 bytes for just the 'opcode' part, or 4/5 for many SSE
opcodes), and then there is the Mod/RM field, which itself is an issue to
decode.

Shudder. If in fact there are only a couple of thousand op codes
then 2/3 is plausible for organizational reasons. However 4/5
sounds a little fishy. Are there really only a couple of
thousand when you take everything into account.

But no, if there only a few thousand opcodes in 2/3 bytes a
specialized trie should do quite nicely. I like to do
precomputed magic tables myself, but it may turn out that a hash
function will do fine. You aren't by any chance using a prime
number size table are you? The modulo operation could be the
bulk of your time in the hash table.

(if you don't believe me, go and take a good long hard look at the Intel
docs, and imagine how you would go about writing an interpreter for all
this
stuff...).

Thanks but no thanks. Looking at the Intel docs is very low on
my list of priorities.

ok, I was using the term to 'opcode' to refer to the entire instruction
(including arguments, ...).

so, in this case the 'opcode' structure contains:
opnum, which is an internal opcode number, which idendifies the nmonic;
opidx, which is an internal opcode index, which identifies the binary
representation of said imstruction;
width, which identifies the bit-width of integer ops;
reg, a register;
op_sz, cached in-memory size of opcode/instruction (used mostly to step
to the next EIP);
rm_base, memory base register, or another data register;
rm_idx, index register;
rm_sc, register scale;
rm_disp, an offset added to memory ops;
rm_fl, which holds flags;
imm, for holding an immediate;
reg2/reg3, for AVX (because we really need 4-register opcodes...);
...

the opcode decoder recognizes the pattern, and fills in all the fields in
the struct as appropriate.
in this way, the main interpreter just grabs the fields from the structure
it needs, without having to fiddle with its serialized form.


these structures are keyed by memory address, which is where the hash
table comes in.

"BGB / cr88192" <cr88192 at (no spam) hotmail.com> wrote in message
news:hcl4ot$sia$1 at (no spam) news.albasani.net...

ok, I was using the term to 'opcode' to refer to the entire instruction
(including arguments, ...).

so, in this case the 'opcode' structure contains:
opnum, which is an internal opcode number, which idendifies the
nmonic;
opidx, which is an internal opcode index, which identifies the binary
representation of said imstruction;
width, which identifies the bit-width of integer ops;
reg, a register;
op_sz, cached in-memory size of opcode/instruction (used mostly to
step to the next EIP);
rm_base, memory base register, or another data register;
rm_idx, index register;
rm_sc, register scale;
rm_disp, an offset added to memory ops;
rm_fl, which holds flags;
imm, for holding an immediate;
reg2/reg3, for AVX (because we really need 4-register opcodes...);
...

the opcode decoder recognizes the pattern, and fills in all the fields in
the struct as appropriate.
in this way, the main interpreter just grabs the fields from the
structure it needs, without having to fiddle with its serialized form.


these structures are keyed by memory address, which is where the hash
table comes in.

It looks like you're translating from the conventional packed form of the
instruction, to an unpacked form that your code finds it easier to deal
with.

In that case why not complete the process and just run this code directly
and forget the original? You will need to change all references to code
(jumps and calls) to addresses within this new block of code.

Then the hashing disappears and you can use whatever switch index you
like. (Although you are now no longer emulating x86 but interpreting
something different.)

(I understood anyway that your 'x86' code was not exactly x86, but only
similar. This means you might be able to directly generate the simpler,
unpacked form, and not bother with any decoding at all.)

On Sun, Nov 01, 2009 at 12:59:06PM -0700, BGB / cr88192 wrote:

but, the hash is not used for opcode lookup/decoding, rather it is used
for
grabbing already decoded instructions from a cache (which is based on
memory
address).

You could extend this to work on blocks of instructions rather than on
single
instructions, where blocks start at places that are jumped to by the
program.

If you do that, you will have to do the decoding of x86 code and the hash
table lookups far less often. I believe this is what QEMU does (they call
it "dynamic translation").

Regards,

Bob

--
Whenever people say "I thought", they were usually wrong.

"BGB / cr88192" <cr88192 at (no spam) hotmail.com> wrote in message
news:hckpa8$aj2$1 at (no spam) news.albasani.net...


(if you don't believe me, go and take a good long hard look at the Intel
docs, and imagine how you would go about writing an interpreter for all
this stuff...).

I think emulator would be a better name. Interpreter has other
connotations.

I started initially trying this, but soon found it unworkable.

I have a feeling that that would still be the best approach, as I guess
that's how actual processors have to decode this stuff.

But I haven't tried it myself and it's too big a task to have a quick go
(I
haven't even been able to find any opcode maps anywhere).

--
Bartc

"Pascal J. Bourguignon" <p... at (no spam) informatimago.com> wrote in messagenews:87y6mqgot3.fsf at (no spam) galatea.local...

"BGB / cr88192" <cr88... at (no spam) hotmail.com> writes:

"Pascal J. Bourguignon" <p... at (no spam) informatimago.com> wrote in message
news:877huaihe4.fsf at (no spam) galatea.local...
"BGB / cr88192" <cr88... at (no spam) hotmail.com> writes:
note: I have plenty of past experience with both ASM and JIT, but at
the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

Modify the C compiler so that it generates optimized code for your
specific case (ie. hide your specific assembly in the C compiler).

I am using MSVC on x64 for this...

So unless you're rich enough to buy the sources of MSVC, forget it.

yep.

I can't even do stupid inline assembly, as MS removed this feature for
x64...

May I suggest you to switch to an open source compiler (such as gcc)?
Or just write your own compiler?

GCC on Win64 was very unreliable last I checked (occasionally generating bad
code, ...), but it may have improved since then.

my compiler works, just I similarly don't trust it that well to produce good
code, and using it for compiling much of anything "non-trivial" is likely to
leave bugs all over the place which would be rather difficult to track down
(I leave it mostly for compiling smaller code fragments at runtime, since a
failure here is at least usually obvious and nearly not so difficult to
track down and fix...).

"BGB / cr88192" <cr88192 at (no spam) hotmail.com> wrote in message
news:hcjarj$vro$1 at (no spam) news.albasani.net...

but, then again, there may still be a little tweaking left, as said
switch has not gained 1st place (it is 2nd), and holds approx 12% of the
total running time.

1st place, at 15%, is the hash-table for fetching instructions (and,
sadly, is not really optimizable unless I discover some way to 'optimize'
basic arithmetic expressions, which FWIW is about as productive as trying
to optimize a switch...).

this means: 27% of time:
hash EIP (currently: "((EIP*65521)>>16)&65535");
fetch opcode-struct from hash-table (the hash-fail rate is apparently
very low);
switch on opcode info (branches to functions containing further dispatch
and logic code).

(well, all this, as well as a few arithmetic ops, such as adding the
opcode size to EIP, ...).

previously I had an opcode decoder which was not super fast (approx 60%
of runtime if sequential decoding is used), but the hash seems to have
largely eliminated it (since most of the time, pre-decoded opcodes are
used from the hash).

Forget C for the crucial dispatch code. If you don't have inline asm, use
a separate linked function.

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten the
intricacies of intel opcode decodes. If ebx points to the next instruction
of 32-bit code:

movzx eax,byte [ebx]
inc ebx
jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a different
table.

And after successfully dealing with an opcode, repeat those initial three
lines (no need to return to a common loop point).

Some experience of creating a disassembler (which is not speed critical)
would be needed to help plan the best approach, but I would still go for
asm code like this rather than C (especially if having trouble getting
reasonable code out of it).

(I had my own hll which also had trouble generating decent code in cases
like this, insisting on range checking that I didn't need:

do
switch x
when a then...
....
end switch
od

I made a couple of language/compiler mods which allowed me to write:

doswitch
asm .....
when a then
...
end switch

Ie. I could write my own switch jump code in asm! And automatically looped
back to the start, although quite often I just repeated the switch code at
the end of some handlers)

note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

What slowdown are you getting compared with a real machine?

--
Bartc

"bartc" <ba... at (no spam) freeuk.com> wrote in message

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten the
intricacies of intel opcode decodes. If ebx points to the next instruction
of 32-bit code:

   movzx eax,byte [ebx]
   inc ebx
   jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a different
table.

And after successfully dealing with an opcode, repeat those initial three
lines (no need to return to a common loop point).

what is to say that the main interpreter switch is dealing with matters of
decoding?...
what is to say that this would actually be any faster than having it NOT
deal with matters of decoding?...
...

apart from needing it to calculate jump targets, the main interpreter almost
does not need to even keep track of EIP...

the decoder is fairly directly based on a disassembler, and yeah, switches
on some of the opcode bytes are used to assist in speeding up the decode
logic.

however, I was able to mostly eliminate instruction decoding from the
runtime overhead via the use of the hash.

also, there are reasons I am using C here...
what is to say an interpreter for x86 will necessarily run ON x86?...

as for doing interpreter logic partly in ASM, I had partly considered this
as well, but for now am sticking with C for other reasons (mostly that, at
the moment, ASM would add more complexities than are worthwhile...).

What slowdown are you getting compared with a real machine?

currently, by simplistic tests, around 170x at present...

so, it is not great, but it could be worse...

On 2 Nov, 06:50, "BGB / cr88192" <cr88... at (no spam) hotmail.com> wrote:

"bartc" <ba... at (no spam) freeuk.com> wrote in message

...

I'll add my comments here as they are similar to bartc's.

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten the
intricacies of intel opcode decodes. If ebx points to the next instruction
of 32-bit code:

   movzx eax,byte [ebx]
   inc ebx
   jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a different
table.

And after successfully dealing with an opcode, repeat those initial three
lines (no need to return to a common loop point).

what is to say that the main interpreter switch is dealing with matters of
decoding?...
what is to say that this would actually be any faster than having it NOT
deal with matters of decoding?...
...

apart from needing it to calculate jump targets, the main interpreter almost
does not need to even keep track of EIP...

As I understand it your hash function looks up instructions that you
have already decoded. That's quite sophisticated and I infer from that
that your decoding is expensive. Whether that's the case or not I
would think that it's likely to be fastest to decode by simple lookup
tables.

"bartc" <bartc at (no spam) freeuk.com> wrote in message
news:xxnHm.748$Ym4.334 at (no spam) text.news.virginmedia.com...


What slowdown are you getting compared with a real machine?


currently, by simplistic tests, around 170x at present...

so, it is not great, but it could be worse...

On 2 Nov., 14:26, James Harris <james.harri... at (no spam) googlemail.com> wrote:



On 2 Nov, 06:50, "BGB / cr88192" <cr88... at (no spam) hotmail.com> wrote:

"bartc" <ba... at (no spam) freeuk.com> wrote in message

...

I'll add my comments here as they are similar to bartc's.

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten the
intricacies of intel opcode decodes. If ebx points to the next instruction
of 32-bit code:

   movzx eax,byte [ebx]
   inc ebx
   jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a different
table.

And after successfully dealing with an opcode, repeat those initial three
lines (no need to return to a common loop point).

what is to say that the main interpreter switch is dealing with matters of
decoding?...
what is to say that this would actually be any faster than having it NOT
deal with matters of decoding?...
...

apart from needing it to calculate jump targets, the main interpreter almost
does not need to even keep track of EIP...

As I understand it your hash function looks up instructions that you
have already decoded. That's quite sophisticated and I infer from that
that your decoding is expensive. Whether that's the case or not I
would think that it's likely to be fastest to decode by simple lookup
tables.

Do I understand this correctly?
The instructions are already decoded and when they
are executed a second decode (switch) is necessary.

This sounds very strange for me, but maybe I just
misunderstand the problem.

I have a question:
Why don't you decode to function pointers instead
of integers (which need to be decoded again)?

Function pointers would even be faster than a
lookup table.

The Seed7 interpreter (hi) works with function
pointers. That way no switch is necessary when
a program is executed.

On 1 Nov., 20:16, "BGB / cr88192" <cr88... at (no spam) hotmail.com> wrote:
"Pascal J. Bourguignon" <p... at (no spam) informatimago.com> wrote in
messagenews:87y6mqgot3.fsf at (no spam) galatea.local...

"BGB / cr88192" <cr88... at (no spam) hotmail.com> writes:

"Pascal J. Bourguignon" <p... at (no spam) informatimago.com> wrote in message
news:877huaihe4.fsf at (no spam) galatea.local...
"BGB / cr88192" <cr88... at (no spam) hotmail.com> writes:
note: I have plenty of past experience with both ASM and JIT, but at
the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

Modify the C compiler so that it generates optimized code for your
specific case (ie. hide your specific assembly in the C compiler).

I am using MSVC on x64 for this...

So unless you're rich enough to buy the sources of MSVC, forget it.

yep.

I can't even do stupid inline assembly, as MS removed this feature for
x64...

May I suggest you to switch to an open source compiler (such as gcc)?
Or just write your own compiler?

GCC on Win64 was very unreliable last I checked (occasionally generating
bad
code, ...), but it may have improved since then.

Did you tell them about the errors you found?

my compiler works, just I similarly don't trust it that well to produce
good
code, and using it for compiling much of anything "non-trivial" is likely
to
leave bugs all over the place which would be rather difficult to track
down
(I leave it mostly for compiling smaller code fragments at runtime, since
a
failure here is at least usually obvious and nearly not so difficult to
track down and fix...).

When you think that GCC and MSVC are not okay you should
definitely use your own C compiler. When there are bugs in it
create a test suite of C programs. That way you can reduce the
number of errors.

You seem to write programs in many areas. But to get this
programs finished with good quality I can only suggest:
Eat your own dogfood.

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

"bartc" <ba... at (no spam) freeuk.com> wrote in message

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten
the
intricacies of intel opcode decodes. If ebx points to the next
instruction
of 32-bit code:

movzx eax,byte [ebx]
inc ebx
jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a
different
table.

And after successfully dealing with an opcode, repeat those initial
three
lines (no need to return to a common loop point).

what is to say that the main interpreter switch is dealing with matters of
decoding?...
what is to say that this would actually be any faster than having it NOT
deal with matters of decoding?...
...

apart from needing it to calculate jump targets, the main interpreter
almost
does not need to even keep track of EIP...

the decoder is fairly directly based on a disassembler, and yeah, switches
on some of the opcode bytes are used to assist in speeding up the decode
logic.

however, I was able to mostly eliminate instruction decoding from the
runtime overhead via the use of the hash.

also, there are reasons I am using C here...
what is to say an interpreter for x86 will necessarily run ON x86?...

as for doing interpreter logic partly in ASM, I had partly considered this
as well, but for now am sticking with C for other reasons (mostly that, at
the moment, ASM would add more complexities than are worthwhile...).

What slowdown are you getting compared with a real machine?

currently, by simplistic tests, around 170x at present...

so, it is not great, but it could be worse...

On 2 Nov, 06:50, "BGB / cr88192" <cr88... at (no spam) hotmail.com> wrote:

"bartc" <ba... at (no spam) freeuk.com> wrote in message

...

I'll add my comments here as they are similar to bartc's.

I don't understand your hash technique. I would just have decoded an
opcode at a time (ie. 8-bits at a time), although I've long forgotten
the
intricacies of intel opcode decodes. If ebx points to the next
instruction
of 32-bit code:

movzx eax,byte [ebx]
inc ebx
jmp [eax*4 + mainopcode_jumptable]

When further decodes are required, a similar 3 lines but with a
different
table.

And after successfully dealing with an opcode, repeat those initial
three
lines (no need to return to a common loop point).

what is to say that the main interpreter switch is dealing with matters
of
decoding?...
what is to say that this would actually be any faster than having it NOT
deal with matters of decoding?...
...

apart from needing it to calculate jump targets, the main interpreter
almost
does not need to even keep track of EIP...

As I understand it your hash function looks up instructions that you
have already decoded. That's quite sophisticated and I infer from that
that your decoding is expensive. Whether that's the case or not I
would think that it's likely to be fastest to decode by simple lookup
tables.