trunk/doc/translation.html

<html><head><title>Gavare's eXperimental Emulator:&nbsp;&nbsp;&nbsp;Dynamic Translation</title>
<meta name="robots" content="noarchive,nofollow,noindex"></head>
<body bgcolor="#f8f8f8" text="#000000" link="#4040f0" vlink="#404040" alink="#ff0000">
<table border=0 width=100% bgcolor="#d0d0d0"><tr>
<td width=100% align=center valign=center><table border=0 width=100%><tr>
<td align="left" valign=center bgcolor="#d0efff"><font color="#6060e0" size="6">
<b>GXemul:</b></font>&nbsp;&nbsp;
<font color="#000000" size="6"><b>Dynamic Translation</b>
</font></td></tr></table></td></tr></table><p>

<!--

$Id: translation.html,v 1.4 2007/06/28 13:36:45 debug Exp $

Copyright (C) 2005-2007  Anders Gavare.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.

-->

<a href="./">Back to the index</a>

<p><br>
<h2>Dynamic Translation</h2>

<p>
<ul>
  <li><a href="#staticvsdynamic">Static vs. dynamic</a>
  <li><a href="#ir">Executable Intermediate Representation</a>
  <li><a href="#performance">Performance</a>
  <li><a href="#instrcomb">Instruction Combinations</a>
  <li><a href="#native">Native Code Generation Back-ends</a>
</ul>


<p><br>
<a name="staticvsdynamic"></a>
<h3>Static vs. dynamic:</h3>

<p>In order to support guest operating systems, which can overwrite old 
code pages in memory with new code, it is necessary to translate code 
dynamically. It is not possible to do a "one-pass" (static) translation.
Self-modifying code and Just-in-Time compilers running inside 
the emulator are other things that would not work with a static 
translator. GXemul is a dynamic translator. However, it does not 
necessarily translate into native code, like many other emulators.


<p><br>
<a name="ir"></a>
<h3>Executable Intermediate Representation:</h3>

<p>Dynamic translators usually translate from the emulated architecture
(e.g. MIPS) into a kind of <i>intermediate representation</i> (IR), and then
to native code (e.g. AMD64 or x86 code). Since one of my main goals for
GXemul is to keep everything as portable as possible, I have tried to make
sure that the IR is something which can be executed regardless of whether 
the final step (translation from IR to native code) has been implemented
or not.

<p>The IR in GXemul consists of arrays of pointers to functions, and a few 
arguments which are passed along to those functions. The functions are 
implemented in either manually hand-coded C, or automatically generated C.
In any case, this is all statically linked into the GXemul binary at link 
time.

<p>Here is a simplified diagram of how these arrays work.

<p><center><img src="simplified_dyntrans.png"></center>

<p>There is one instruction call slot for every possible program counter
location. In the MIPS case, instruction words are 32 bits in length,
and pages are (usually) 4 KB large, resulting in 1024 instruction call
slots. After the last of these instruction calls, there is an additional
call to a special "end of page" function (which doesn't count as an executed
instruction). This function switches to the first instruction
on the next virtual page (which might cause exceptions, etc).

<p>The complexity of individual instructions vary. A simple example of
what an instruction can look like is the MIPS <tt>addiu</tt> instruction:
<pre>
        X(addiu)
        {
                reg(ic->arg[1]) = (int32_t)
                    ((int32_t)reg(ic->arg[0]) + (int32_t)ic->arg[2]);
        }
</pre>

<p>It stores the result of a 32-bit addition of the register at arg[0]
with the immediate value arg[2] (treating both as signed 32-bit
integers) into register arg[1]. If the emulated CPU is a 64-bit CPU,
then this will store a correctly sign-extended value into arg[1].
If it is a 32-bit CPU, then only the lowest 32 bits will be stored,
and the high part ignored. <tt>X(addiu)</tt> is expanded to
<tt>mips_instr_addiu</tt> in the 64-bit case, and <tt>mips32_instr_addiu</tt>
in the 32-bit case. Both are compiled into the GXemul executable; no code 
is created during run-time.


<p><br>
<a name="performance"></a>
<h3>Performance:</h3>

<p>The performance of using this kind of executable IR is obviously lower
than what can be achieved by emulators using native code generation, but
can be significantly higher than using a naive fetch-decode-execute
interpretation loop. In my opinion, using an executable IR is an interesting
compromise.

<p>The overhead per emulated instruction is usually around or below
approximately 10 host instructions. This is very much dependent on your
host architecture and what compiler and compiler switches you are using.
Added to this instruction count is (of course) also the C code used to
implement each specific instruction.


<p><br>
<a name="instrcomb"></a>
<h3>Instruction Combinations:</h3>

<p>Short, common instruction sequences can sometimes be replaced by a 
"compound" instruction. An example could be a compare instruction followed 
by a conditional branch instruction. The advantages of instruction 
combinations are that
<ul>
  <li>the amortized overhead per instruction is slightly reduced, and
  <p>
  <li>the host's compiler can make a good job at optimizing the common
        instruction sequence.
</ul>

<p>The special cases where instruction combinations give the most gain
are in the cores of string/memory manipulation functions such as 
<tt>memset()</tt> or <tt>strlen()</tt>. The core loop can then (at least
to some extent) be replaced by a native call to the equivalent function.

<p>The implementations of compound instructions still keep track of the
number of executed instructions, etc. When single-stepping, these
translations are invalidated, and replaced by normal instruction calls
(one per emulated instruction).


<p><br>
<a name="native"></a>
<h3>Native Code Generation Back-ends:</h3>

<p>In theory, it will be possible to implement native code generation,
similar to what is used in high-performance emulators such as <a
href="http://www.qemu.com/">QEMU</a>, as long as that generated code
abides to the C ABI on the host.

<p>However, since I wanted to make sure that GXemul works without such 
native code back-ends, there are no implemented backends in this release.


</body>
</html>
1	dpavlin	38	<html><head><title>Gavare's eXperimental Emulator:   Dynamic Translation</title>
2			<meta name="robots" content="noarchive,nofollow,noindex"></head>
3			<body bgcolor="#f8f8f8" text="#000000" link="#4040f0" vlink="#404040" alink="#ff0000">
4			<table border=0 width=100% bgcolor="#d0d0d0"><tr>
5			<td width=100% align=center valign=center><table border=0 width=100%><tr>
6			<td align="left" valign=center bgcolor="#d0efff"><font color="#6060e0" size="6">
7	dpavlin	44	<b>GXemul:</b></font>
8	dpavlin	38	<font color="#000000" size="6"><b>Dynamic Translation</b>
9			</font></td></tr></table></td></tr></table><p>
10
11			<!--
12
13	dpavlin	44	$Id: translation.html,v 1.4 2007/06/28 13:36:45 debug Exp $
14	dpavlin	38
15			Copyright (C) 2005-2007 Anders Gavare. All rights reserved.
16
17			Redistribution and use in source and binary forms, with or without
18			modification, are permitted provided that the following conditions are met:
19
20			1. Redistributions of source code must retain the above copyright
21			notice, this list of conditions and the following disclaimer.
22			2. Redistributions in binary form must reproduce the above copyright
23			notice, this list of conditions and the following disclaimer in the
24			documentation and/or other materials provided with the distribution.
25			3. The name of the author may not be used to endorse or promote products
26			derived from this software without specific prior written permission.
27
28			THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
29			ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30			IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31			ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
32			FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33			DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34			OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35			HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36			LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37			OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38			SUCH DAMAGE.
39
40			-->
41
42			<a href="./">Back to the index</a>
43
44			<p><br>
45			<h2>Dynamic Translation</h2>
46
47			<p>
48			<ul>
49			<li><a href="#staticvsdynamic">Static vs. dynamic</a>
50			<li><a href="#ir">Executable Intermediate Representation</a>
51			<li><a href="#performance">Performance</a>
52			<li><a href="#instrcomb">Instruction Combinations</a>
53			<li><a href="#native">Native Code Generation Back-ends</a>
54			</ul>
55
56
57
58
59			<p><br>
60			<a name="staticvsdynamic"></a>
61			<h3>Static vs. dynamic:</h3>
62
63			<p>In order to support guest operating systems, which can overwrite old
64			code pages in memory with new code, it is necessary to translate code
65			dynamically. It is not possible to do a "one-pass" (static) translation.
66			Self-modifying code and Just-in-Time compilers running inside
67			the emulator are other things that would not work with a static
68			translator. GXemul is a dynamic translator. However, it does not
69			necessarily translate into native code, like many other emulators.
70
71
72			<p><br>
73			<a name="ir"></a>
74			<h3>Executable Intermediate Representation:</h3>
75
76			<p>Dynamic translators usually translate from the emulated architecture
77			(e.g. MIPS) into a kind of <i>intermediate representation</i> (IR), and then
78			to native code (e.g. AMD64 or x86 code). Since one of my main goals for
79			GXemul is to keep everything as portable as possible, I have tried to make
80			sure that the IR is something which can be executed regardless of whether
81			the final step (translation from IR to native code) has been implemented
82			or not.
83
84			<p>The IR in GXemul consists of arrays of pointers to functions, and a few
85			arguments which are passed along to those functions. The functions are
86			implemented in either manually hand-coded C, or automatically generated C.
87			In any case, this is all statically linked into the GXemul binary at link
88			time.
89
90			<p>Here is a simplified diagram of how these arrays work.
91
92			<p><center><img src="simplified_dyntrans.png"></center>
93
94			<p>There is one instruction call slot for every possible program counter
95			location. In the MIPS case, instruction words are 32 bits in length,
96			and pages are (usually) 4 KB large, resulting in 1024 instruction call
97			slots. After the last of these instruction calls, there is an additional
98			call to a special "end of page" function (which doesn't count as an executed
99			instruction). This function switches to the first instruction
100			on the next virtual page (which might cause exceptions, etc).
101
102			<p>The complexity of individual instructions vary. A simple example of
103			what an instruction can look like is the MIPS <tt>addiu</tt> instruction:
104			<pre>
105			X(addiu)
106			{
107			reg(ic->arg[1]) = (int32_t)
108			((int32_t)reg(ic->arg[0]) + (int32_t)ic->arg[2]);
109			}
110			</pre>
111
112			<p>It stores the result of a 32-bit addition of the register at arg[0]
113			with the immediate value arg[2] (treating both as signed 32-bit
114			integers) into register arg[1]. If the emulated CPU is a 64-bit CPU,
115			then this will store a correctly sign-extended value into arg[1].
116			If it is a 32-bit CPU, then only the lowest 32 bits will be stored,
117			and the high part ignored. <tt>X(addiu)</tt> is expanded to
118			<tt>mips_instr_addiu</tt> in the 64-bit case, and <tt>mips32_instr_addiu</tt>
119			in the 32-bit case. Both are compiled into the GXemul executable; no code
120			is created during run-time.
121
122
123			<p><br>
124			<a name="performance"></a>
125			<h3>Performance:</h3>
126
127			<p>The performance of using this kind of executable IR is obviously lower
128			than what can be achieved by emulators using native code generation, but
129			can be significantly higher than using a naive fetch-decode-execute
130			interpretation loop. In my opinion, using an executable IR is an interesting
131			compromise.
132
133			<p>The overhead per emulated instruction is usually around or below
134			approximately 10 host instructions. This is very much dependent on your
135			host architecture and what compiler and compiler switches you are using.
136			Added to this instruction count is (of course) also the C code used to
137			implement each specific instruction.
138
139
140			<p><br>
141			<a name="instrcomb"></a>
142			<h3>Instruction Combinations:</h3>
143
144			<p>Short, common instruction sequences can sometimes be replaced by a
145			"compound" instruction. An example could be a compare instruction followed
146			by a conditional branch instruction. The advantages of instruction
147			combinations are that
148			<ul>
149			<li>the amortized overhead per instruction is slightly reduced, and
150			<p>
151			<li>the host's compiler can make a good job at optimizing the common
152			instruction sequence.
153			</ul>
154
155			<p>The special cases where instruction combinations give the most gain
156			are in the cores of string/memory manipulation functions such as
157			<tt>memset()</tt> or <tt>strlen()</tt>. The core loop can then (at least
158			to some extent) be replaced by a native call to the equivalent function.
159
160			<p>The implementations of compound instructions still keep track of the
161			number of executed instructions, etc. When single-stepping, these
162			translations are invalidated, and replaced by normal instruction calls
163			(one per emulated instruction).
164
165
166			<p><br>
167			<a name="native"></a>
168			<h3>Native Code Generation Back-ends:</h3>
169
170			<p>In theory, it will be possible to implement native code generation,
171	dpavlin	44	similar to what is used in high-performance emulators such as <a
172			href="http://www.qemu.com/">QEMU</a>, as long as that generated code
173			abides to the C ABI on the host.
174	dpavlin	38
175			<p>However, since I wanted to make sure that GXemul works without such
176			native code back-ends, there are no implemented backends in this release.
177
178
179
180
181
182
183
184			</body>
185			</html>