1 |
<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 |
<b>GXemul:</b></font> |
8 |
<font color="#000000" size="6"><b>Dynamic Translation</b> |
9 |
</font></td></tr></table></td></tr></table><p> |
10 |
|
11 |
<!-- |
12 |
|
13 |
$Id: translation.html,v 1.4 2007/06/28 13:36:45 debug Exp $ |
14 |
|
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 |
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 |
|
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> |