root / tcg / README @ f53ec699
History | View | Annotate | Download (15.9 kB)
1 |
Tiny Code Generator - Fabrice Bellard. |
---|---|
2 |
|
3 |
1) Introduction |
4 |
|
5 |
TCG (Tiny Code Generator) began as a generic backend for a C |
6 |
compiler. It was simplified to be used in QEMU. It also has its roots |
7 |
in the QOP code generator written by Paul Brook. |
8 |
|
9 |
2) Definitions |
10 |
|
11 |
The TCG "target" is the architecture for which we generate the |
12 |
code. It is of course not the same as the "target" of QEMU which is |
13 |
the emulated architecture. As TCG started as a generic C backend used |
14 |
for cross compiling, it is assumed that the TCG target is different |
15 |
from the host, although it is never the case for QEMU. |
16 |
|
17 |
In this document, we use "guest" to specify what architecture we are |
18 |
emulating; "target" always means the TCG target, the machine on which |
19 |
we are running QEMU. |
20 |
|
21 |
A TCG "function" corresponds to a QEMU Translated Block (TB). |
22 |
|
23 |
A TCG "temporary" is a variable only live in a basic |
24 |
block. Temporaries are allocated explicitly in each function. |
25 |
|
26 |
A TCG "local temporary" is a variable only live in a function. Local |
27 |
temporaries are allocated explicitly in each function. |
28 |
|
29 |
A TCG "global" is a variable which is live in all the functions |
30 |
(equivalent of a C global variable). They are defined before the |
31 |
functions defined. A TCG global can be a memory location (e.g. a QEMU |
32 |
CPU register), a fixed host register (e.g. the QEMU CPU state pointer) |
33 |
or a memory location which is stored in a register outside QEMU TBs |
34 |
(not implemented yet). |
35 |
|
36 |
A TCG "basic block" corresponds to a list of instructions terminated |
37 |
by a branch instruction. |
38 |
|
39 |
3) Intermediate representation |
40 |
|
41 |
3.1) Introduction |
42 |
|
43 |
TCG instructions operate on variables which are temporaries, local |
44 |
temporaries or globals. TCG instructions and variables are strongly |
45 |
typed. Two types are supported: 32 bit integers and 64 bit |
46 |
integers. Pointers are defined as an alias to 32 bit or 64 bit |
47 |
integers depending on the TCG target word size. |
48 |
|
49 |
Each instruction has a fixed number of output variable operands, input |
50 |
variable operands and always constant operands. |
51 |
|
52 |
The notable exception is the call instruction which has a variable |
53 |
number of outputs and inputs. |
54 |
|
55 |
In the textual form, output operands usually come first, followed by |
56 |
input operands, followed by constant operands. The output type is |
57 |
included in the instruction name. Constants are prefixed with a '$'. |
58 |
|
59 |
add_i32 t0, t1, t2 (t0 <- t1 + t2) |
60 |
|
61 |
3.2) Assumptions |
62 |
|
63 |
* Basic blocks |
64 |
|
65 |
- Basic blocks end after branches (e.g. brcond_i32 instruction), |
66 |
goto_tb and exit_tb instructions. |
67 |
- Basic blocks start after the end of a previous basic block, or at a |
68 |
set_label instruction. |
69 |
|
70 |
After the end of a basic block, the content of temporaries is |
71 |
destroyed, but local temporaries and globals are preserved. |
72 |
|
73 |
* Floating point types are not supported yet |
74 |
|
75 |
* Pointers: depending on the TCG target, pointer size is 32 bit or 64 |
76 |
bit. The type TCG_TYPE_PTR is an alias to TCG_TYPE_I32 or |
77 |
TCG_TYPE_I64. |
78 |
|
79 |
* Helpers: |
80 |
|
81 |
Using the tcg_gen_helper_x_y it is possible to call any function |
82 |
taking i32, i64 or pointer types. By default, before calling a helper, |
83 |
all globals are stored at their canonical location and it is assumed |
84 |
that the function can modify them. By default, the helper is allowed to |
85 |
modify the CPU state or raise an exception. |
86 |
|
87 |
This can be overridden using the following function modifiers: |
88 |
- TCG_CALL_NO_READ_GLOBALS means that the helper does not read globals, |
89 |
either directly or via an exception. They will not be saved to their |
90 |
canonical locations before calling the helper. |
91 |
- TCG_CALL_NO_WRITE_GLOBALS means that the helper does not modify any globals. |
92 |
They will only be saved to their canonical location before calling helpers, |
93 |
but they won't be reloaded afterwise. |
94 |
- TCG_CALL_NO_SIDE_EFFECTS means that the call to the function is removed if |
95 |
the return value is not used. |
96 |
|
97 |
Note that TCG_CALL_NO_READ_GLOBALS implies TCG_CALL_NO_WRITE_GLOBALS. |
98 |
|
99 |
On some TCG targets (e.g. x86), several calling conventions are |
100 |
supported. |
101 |
|
102 |
* Branches: |
103 |
|
104 |
Use the instruction 'br' to jump to a label. |
105 |
|
106 |
3.3) Code Optimizations |
107 |
|
108 |
When generating instructions, you can count on at least the following |
109 |
optimizations: |
110 |
|
111 |
- Single instructions are simplified, e.g. |
112 |
|
113 |
and_i32 t0, t0, $0xffffffff |
114 |
|
115 |
is suppressed. |
116 |
|
117 |
- A liveness analysis is done at the basic block level. The |
118 |
information is used to suppress moves from a dead variable to |
119 |
another one. It is also used to remove instructions which compute |
120 |
dead results. The later is especially useful for condition code |
121 |
optimization in QEMU. |
122 |
|
123 |
In the following example: |
124 |
|
125 |
add_i32 t0, t1, t2 |
126 |
add_i32 t0, t0, $1 |
127 |
mov_i32 t0, $1 |
128 |
|
129 |
only the last instruction is kept. |
130 |
|
131 |
3.4) Instruction Reference |
132 |
|
133 |
********* Function call |
134 |
|
135 |
* call <ret> <params> ptr |
136 |
|
137 |
call function 'ptr' (pointer type) |
138 |
|
139 |
<ret> optional 32 bit or 64 bit return value |
140 |
<params> optional 32 bit or 64 bit parameters |
141 |
|
142 |
********* Jumps/Labels |
143 |
|
144 |
* set_label $label |
145 |
|
146 |
Define label 'label' at the current program point. |
147 |
|
148 |
* br $label |
149 |
|
150 |
Jump to label. |
151 |
|
152 |
* brcond_i32/i64 t0, t1, cond, label |
153 |
|
154 |
Conditional jump if t0 cond t1 is true. cond can be: |
155 |
TCG_COND_EQ |
156 |
TCG_COND_NE |
157 |
TCG_COND_LT /* signed */ |
158 |
TCG_COND_GE /* signed */ |
159 |
TCG_COND_LE /* signed */ |
160 |
TCG_COND_GT /* signed */ |
161 |
TCG_COND_LTU /* unsigned */ |
162 |
TCG_COND_GEU /* unsigned */ |
163 |
TCG_COND_LEU /* unsigned */ |
164 |
TCG_COND_GTU /* unsigned */ |
165 |
|
166 |
********* Arithmetic |
167 |
|
168 |
* add_i32/i64 t0, t1, t2 |
169 |
|
170 |
t0=t1+t2 |
171 |
|
172 |
* sub_i32/i64 t0, t1, t2 |
173 |
|
174 |
t0=t1-t2 |
175 |
|
176 |
* neg_i32/i64 t0, t1 |
177 |
|
178 |
t0=-t1 (two's complement) |
179 |
|
180 |
* mul_i32/i64 t0, t1, t2 |
181 |
|
182 |
t0=t1*t2 |
183 |
|
184 |
* div_i32/i64 t0, t1, t2 |
185 |
|
186 |
t0=t1/t2 (signed). Undefined behavior if division by zero or overflow. |
187 |
|
188 |
* divu_i32/i64 t0, t1, t2 |
189 |
|
190 |
t0=t1/t2 (unsigned). Undefined behavior if division by zero. |
191 |
|
192 |
* rem_i32/i64 t0, t1, t2 |
193 |
|
194 |
t0=t1%t2 (signed). Undefined behavior if division by zero or overflow. |
195 |
|
196 |
* remu_i32/i64 t0, t1, t2 |
197 |
|
198 |
t0=t1%t2 (unsigned). Undefined behavior if division by zero. |
199 |
|
200 |
********* Logical |
201 |
|
202 |
* and_i32/i64 t0, t1, t2 |
203 |
|
204 |
t0=t1&t2 |
205 |
|
206 |
* or_i32/i64 t0, t1, t2 |
207 |
|
208 |
t0=t1|t2 |
209 |
|
210 |
* xor_i32/i64 t0, t1, t2 |
211 |
|
212 |
t0=t1^t2 |
213 |
|
214 |
* not_i32/i64 t0, t1 |
215 |
|
216 |
t0=~t1 |
217 |
|
218 |
* andc_i32/i64 t0, t1, t2 |
219 |
|
220 |
t0=t1&~t2 |
221 |
|
222 |
* eqv_i32/i64 t0, t1, t2 |
223 |
|
224 |
t0=~(t1^t2), or equivalently, t0=t1^~t2 |
225 |
|
226 |
* nand_i32/i64 t0, t1, t2 |
227 |
|
228 |
t0=~(t1&t2) |
229 |
|
230 |
* nor_i32/i64 t0, t1, t2 |
231 |
|
232 |
t0=~(t1|t2) |
233 |
|
234 |
* orc_i32/i64 t0, t1, t2 |
235 |
|
236 |
t0=t1|~t2 |
237 |
|
238 |
********* Shifts/Rotates |
239 |
|
240 |
* shl_i32/i64 t0, t1, t2 |
241 |
|
242 |
t0=t1 << t2. Undefined behavior if t2 < 0 or t2 >= 32 (resp 64) |
243 |
|
244 |
* shr_i32/i64 t0, t1, t2 |
245 |
|
246 |
t0=t1 >> t2 (unsigned). Undefined behavior if t2 < 0 or t2 >= 32 (resp 64) |
247 |
|
248 |
* sar_i32/i64 t0, t1, t2 |
249 |
|
250 |
t0=t1 >> t2 (signed). Undefined behavior if t2 < 0 or t2 >= 32 (resp 64) |
251 |
|
252 |
* rotl_i32/i64 t0, t1, t2 |
253 |
|
254 |
Rotation of t2 bits to the left. Undefined behavior if t2 < 0 or t2 >= 32 (resp 64) |
255 |
|
256 |
* rotr_i32/i64 t0, t1, t2 |
257 |
|
258 |
Rotation of t2 bits to the right. Undefined behavior if t2 < 0 or t2 >= 32 (resp 64) |
259 |
|
260 |
********* Misc |
261 |
|
262 |
* mov_i32/i64 t0, t1 |
263 |
|
264 |
t0 = t1 |
265 |
|
266 |
Move t1 to t0 (both operands must have the same type). |
267 |
|
268 |
* ext8s_i32/i64 t0, t1 |
269 |
ext8u_i32/i64 t0, t1 |
270 |
ext16s_i32/i64 t0, t1 |
271 |
ext16u_i32/i64 t0, t1 |
272 |
ext32s_i64 t0, t1 |
273 |
ext32u_i64 t0, t1 |
274 |
|
275 |
8, 16 or 32 bit sign/zero extension (both operands must have the same type) |
276 |
|
277 |
* bswap16_i32/i64 t0, t1 |
278 |
|
279 |
16 bit byte swap on a 32/64 bit value. It assumes that the two/six high order |
280 |
bytes are set to zero. |
281 |
|
282 |
* bswap32_i32/i64 t0, t1 |
283 |
|
284 |
32 bit byte swap on a 32/64 bit value. With a 64 bit value, it assumes that |
285 |
the four high order bytes are set to zero. |
286 |
|
287 |
* bswap64_i64 t0, t1 |
288 |
|
289 |
64 bit byte swap |
290 |
|
291 |
* discard_i32/i64 t0 |
292 |
|
293 |
Indicate that the value of t0 won't be used later. It is useful to |
294 |
force dead code elimination. |
295 |
|
296 |
* deposit_i32/i64 dest, t1, t2, pos, len |
297 |
|
298 |
Deposit T2 as a bitfield into T1, placing the result in DEST. |
299 |
The bitfield is described by POS/LEN, which are immediate values: |
300 |
|
301 |
LEN - the length of the bitfield |
302 |
POS - the position of the first bit, counting from the LSB |
303 |
|
304 |
For example, pos=8, len=4 indicates a 4-bit field at bit 8. |
305 |
This operation would be equivalent to |
306 |
|
307 |
dest = (t1 & ~0x0f00) | ((t2 << 8) & 0x0f00) |
308 |
|
309 |
|
310 |
********* Conditional moves |
311 |
|
312 |
* setcond_i32/i64 dest, t1, t2, cond |
313 |
|
314 |
dest = (t1 cond t2) |
315 |
|
316 |
Set DEST to 1 if (T1 cond T2) is true, otherwise set to 0. |
317 |
|
318 |
* movcond_i32/i64 dest, c1, c2, v1, v2, cond |
319 |
|
320 |
dest = (c1 cond c2 ? v1 : v2) |
321 |
|
322 |
Set DEST to V1 if (C1 cond C2) is true, otherwise set to V2. |
323 |
|
324 |
********* Type conversions |
325 |
|
326 |
* ext_i32_i64 t0, t1 |
327 |
Convert t1 (32 bit) to t0 (64 bit) and does sign extension |
328 |
|
329 |
* extu_i32_i64 t0, t1 |
330 |
Convert t1 (32 bit) to t0 (64 bit) and does zero extension |
331 |
|
332 |
* trunc_i64_i32 t0, t1 |
333 |
Truncate t1 (64 bit) to t0 (32 bit) |
334 |
|
335 |
* concat_i32_i64 t0, t1, t2 |
336 |
Construct t0 (64-bit) taking the low half from t1 (32 bit) and the high half |
337 |
from t2 (32 bit). |
338 |
|
339 |
* concat32_i64 t0, t1, t2 |
340 |
Construct t0 (64-bit) taking the low half from t1 (64 bit) and the high half |
341 |
from t2 (64 bit). |
342 |
|
343 |
********* Load/Store |
344 |
|
345 |
* ld_i32/i64 t0, t1, offset |
346 |
ld8s_i32/i64 t0, t1, offset |
347 |
ld8u_i32/i64 t0, t1, offset |
348 |
ld16s_i32/i64 t0, t1, offset |
349 |
ld16u_i32/i64 t0, t1, offset |
350 |
ld32s_i64 t0, t1, offset |
351 |
ld32u_i64 t0, t1, offset |
352 |
|
353 |
t0 = read(t1 + offset) |
354 |
Load 8, 16, 32 or 64 bits with or without sign extension from host memory. |
355 |
offset must be a constant. |
356 |
|
357 |
* st_i32/i64 t0, t1, offset |
358 |
st8_i32/i64 t0, t1, offset |
359 |
st16_i32/i64 t0, t1, offset |
360 |
st32_i64 t0, t1, offset |
361 |
|
362 |
write(t0, t1 + offset) |
363 |
Write 8, 16, 32 or 64 bits to host memory. |
364 |
|
365 |
All this opcodes assume that the pointed host memory doesn't correspond |
366 |
to a global. In the latter case the behaviour is unpredictable. |
367 |
|
368 |
********* Multiword arithmetic support |
369 |
|
370 |
* add2_i32/i64 t0_low, t0_high, t1_low, t1_high, t2_low, t2_high |
371 |
* sub2_i32/i64 t0_low, t0_high, t1_low, t1_high, t2_low, t2_high |
372 |
|
373 |
Similar to add/sub, except that the double-word inputs T1 and T2 are |
374 |
formed from two single-word arguments, and the double-word output T0 |
375 |
is returned in two single-word outputs. |
376 |
|
377 |
* mulu2_i32/i64 t0_low, t0_high, t1, t2 |
378 |
|
379 |
Similar to mul, except two unsigned inputs T1 and T2 yielding the full |
380 |
double-word product T0. The later is returned in two single-word outputs. |
381 |
|
382 |
* muls2_i32/i64 t0_low, t0_high, t1, t2 |
383 |
|
384 |
Similar to mulu2, except the two inputs T1 and T2 are signed. |
385 |
|
386 |
********* 64-bit guest on 32-bit host support |
387 |
|
388 |
The following opcodes are internal to TCG. Thus they are to be implemented by |
389 |
32-bit host code generators, but are not to be emitted by guest translators. |
390 |
They are emitted as needed by inline functions within "tcg-op.h". |
391 |
|
392 |
* brcond2_i32 t0_low, t0_high, t1_low, t1_high, cond, label |
393 |
|
394 |
Similar to brcond, except that the 64-bit values T0 and T1 |
395 |
are formed from two 32-bit arguments. |
396 |
|
397 |
* setcond2_i32 dest, t1_low, t1_high, t2_low, t2_high, cond |
398 |
|
399 |
Similar to setcond, except that the 64-bit values T1 and T2 are |
400 |
formed from two 32-bit arguments. The result is a 32-bit value. |
401 |
|
402 |
********* QEMU specific operations |
403 |
|
404 |
* exit_tb t0 |
405 |
|
406 |
Exit the current TB and return the value t0 (word type). |
407 |
|
408 |
* goto_tb index |
409 |
|
410 |
Exit the current TB and jump to the TB index 'index' (constant) if the |
411 |
current TB was linked to this TB. Otherwise execute the next |
412 |
instructions. Only indices 0 and 1 are valid and tcg_gen_goto_tb may be issued |
413 |
at most once with each slot index per TB. |
414 |
|
415 |
* qemu_ld8u t0, t1, flags |
416 |
qemu_ld8s t0, t1, flags |
417 |
qemu_ld16u t0, t1, flags |
418 |
qemu_ld16s t0, t1, flags |
419 |
qemu_ld32 t0, t1, flags |
420 |
qemu_ld32u t0, t1, flags |
421 |
qemu_ld32s t0, t1, flags |
422 |
qemu_ld64 t0, t1, flags |
423 |
|
424 |
Load data at the QEMU CPU address t1 into t0. t1 has the QEMU CPU address |
425 |
type. 'flags' contains the QEMU memory index (selects user or kernel access) |
426 |
for example. |
427 |
|
428 |
Note that "qemu_ld32" implies a 32-bit result, while "qemu_ld32u" and |
429 |
"qemu_ld32s" imply a 64-bit result appropriately extended from 32 bits. |
430 |
|
431 |
* qemu_st8 t0, t1, flags |
432 |
qemu_st16 t0, t1, flags |
433 |
qemu_st32 t0, t1, flags |
434 |
qemu_st64 t0, t1, flags |
435 |
|
436 |
Store the data t0 at the QEMU CPU Address t1. t1 has the QEMU CPU |
437 |
address type. 'flags' contains the QEMU memory index (selects user or |
438 |
kernel access) for example. |
439 |
|
440 |
Note 1: Some shortcuts are defined when the last operand is known to be |
441 |
a constant (e.g. addi for add, movi for mov). |
442 |
|
443 |
Note 2: When using TCG, the opcodes must never be generated directly |
444 |
as some of them may not be available as "real" opcodes. Always use the |
445 |
function tcg_gen_xxx(args). |
446 |
|
447 |
4) Backend |
448 |
|
449 |
tcg-target.h contains the target specific definitions. tcg-target.c |
450 |
contains the target specific code. |
451 |
|
452 |
4.1) Assumptions |
453 |
|
454 |
The target word size (TCG_TARGET_REG_BITS) is expected to be 32 bit or |
455 |
64 bit. It is expected that the pointer has the same size as the word. |
456 |
|
457 |
On a 32 bit target, all 64 bit operations are converted to 32 bits. A |
458 |
few specific operations must be implemented to allow it (see add2_i32, |
459 |
sub2_i32, brcond2_i32). |
460 |
|
461 |
Floating point operations are not supported in this version. A |
462 |
previous incarnation of the code generator had full support of them, |
463 |
but it is better to concentrate on integer operations first. |
464 |
|
465 |
On a 64 bit target, no assumption is made in TCG about the storage of |
466 |
the 32 bit values in 64 bit registers. |
467 |
|
468 |
4.2) Constraints |
469 |
|
470 |
GCC like constraints are used to define the constraints of every |
471 |
instruction. Memory constraints are not supported in this |
472 |
version. Aliases are specified in the input operands as for GCC. |
473 |
|
474 |
The same register may be used for both an input and an output, even when |
475 |
they are not explicitly aliased. If an op expands to multiple target |
476 |
instructions then care must be taken to avoid clobbering input values. |
477 |
GCC style "early clobber" outputs are not currently supported. |
478 |
|
479 |
A target can define specific register or constant constraints. If an |
480 |
operation uses a constant input constraint which does not allow all |
481 |
constants, it must also accept registers in order to have a fallback. |
482 |
|
483 |
The movi_i32 and movi_i64 operations must accept any constants. |
484 |
|
485 |
The mov_i32 and mov_i64 operations must accept any registers of the |
486 |
same type. |
487 |
|
488 |
The ld/st instructions must accept signed 32 bit constant offsets. It |
489 |
can be implemented by reserving a specific register to compute the |
490 |
address if the offset is too big. |
491 |
|
492 |
The ld/st instructions must accept any destination (ld) or source (st) |
493 |
register. |
494 |
|
495 |
4.3) Function call assumptions |
496 |
|
497 |
- The only supported types for parameters and return value are: 32 and |
498 |
64 bit integers and pointer. |
499 |
- The stack grows downwards. |
500 |
- The first N parameters are passed in registers. |
501 |
- The next parameters are passed on the stack by storing them as words. |
502 |
- Some registers are clobbered during the call. |
503 |
- The function can return 0 or 1 value in registers. On a 32 bit |
504 |
target, functions must be able to return 2 values in registers for |
505 |
64 bit return type. |
506 |
|
507 |
5) Recommended coding rules for best performance |
508 |
|
509 |
- Use globals to represent the parts of the QEMU CPU state which are |
510 |
often modified, e.g. the integer registers and the condition |
511 |
codes. TCG will be able to use host registers to store them. |
512 |
|
513 |
- Avoid globals stored in fixed registers. They must be used only to |
514 |
store the pointer to the CPU state and possibly to store a pointer |
515 |
to a register window. |
516 |
|
517 |
- Use temporaries. Use local temporaries only when really needed, |
518 |
e.g. when you need to use a value after a jump. Local temporaries |
519 |
introduce a performance hit in the current TCG implementation: their |
520 |
content is saved to memory at end of each basic block. |
521 |
|
522 |
- Free temporaries and local temporaries when they are no longer used |
523 |
(tcg_temp_free). Since tcg_const_x() also creates a temporary, you |
524 |
should free it after it is used. Freeing temporaries does not yield |
525 |
a better generated code, but it reduces the memory usage of TCG and |
526 |
the speed of the translation. |
527 |
|
528 |
- Don't hesitate to use helpers for complicated or seldom used guest |
529 |
instructions. There is little performance advantage in using TCG to |
530 |
implement guest instructions taking more than about twenty TCG |
531 |
instructions. Note that this rule of thumb is more applicable to |
532 |
helpers doing complex logic or arithmetic, where the C compiler has |
533 |
scope to do a good job of optimisation; it is less relevant where |
534 |
the instruction is mostly doing loads and stores, and in those cases |
535 |
inline TCG may still be faster for longer sequences. |
536 |
|
537 |
- The hard limit on the number of TCG instructions you can generate |
538 |
per guest instruction is set by MAX_OP_PER_INSTR in exec-all.h -- |
539 |
you cannot exceed this without risking a buffer overrun. |
540 |
|
541 |
- Use the 'discard' instruction if you know that TCG won't be able to |
542 |
prove that a given global is "dead" at a given program point. The |
543 |
x86 guest uses it to improve the condition codes optimisation. |