TCG 中间表示

简介

TCG(Tiny Code Generator,微型代码生成器)最初是 C 编译器的通用后端,经过简化后用于 QEMU。它也源自 Paul Brook 编写的 QOP 代码生成器。

定义

TCG 的 目标 是生成代码所针对的架构,与 QEMU 中表示被模拟架构的“目标”不同。TCG 最初是用于交叉编译的通用 C 后端,因此假定 TCG 目标可能与主机不同,尽管在 QEMU 中从不会出现这种情况。

本文使用 客户机 指被模拟的架构;目标 始终指 TCG 目标,即运行 QEMU 的机器。

具有 未定义行为 的操作可能导致崩溃。

具有 未指定行为 的操作不得崩溃,但结果可能是几种情况之一,因此可视为 未定义结果。

基本块

TCG 基本块 是单入口、多出口区域,对应一组由标签或任意分支指令终止的指令。

TCG 扩展基本块 是单入口、多出口区域,对应一组由标签或无条件分支终止的指令。具体而言,扩展基本块由一系列基本块组成,它们通过零个或多个条件分支指令的不跳转路径相连。

操作

TCG 指令或 操作 作用于 TCG 变量,两者均为强类型。每条指令具有固定数量的输出变量操作数、输入变量操作数和常量操作数。向量指令有一个字段指定向量内元素的大小。值得注意的例外是 call 指令,其输出和输入数量可变。

文本形式通常先列输出操作数,再列输入操作数,最后是常量操作数。指令名包含输出类型,常量以 '$' 为前缀。

add_i32 t0, t1, t2    /* (t0 <- t1 + t2) */

变量

  • TEMP_FIXED

    TCG 有一个 固定全局 变量 cpu_env,在所有翻译块中均存活,保存指向 CPUArchState 的指针。所有翻译块中,该变量始终保存在主机 CPU 寄存器中。

  • TEMP_GLOBAL

    TCG 全局变量 在所有翻译块中均存活,对应 CPUArchState 内的某个内存位置。可以用相对于 cpu_env 的偏移指定,此时称为 直接全局变量;也可以用相对于直接全局变量的偏移指定,此时称为 间接全局变量。即使间接全局变量,也应引用 CPUArchState 内的内存。所有 TCG 全局变量均在 TCGCPUOps.initialize 期间定义,此时尚未生成任何翻译块。

  • TEMP_CONST

    TCG 常量 是在整个翻译块中存活、包含常量值的变量。这些变量在翻译期间按需分配,并通过哈希保证每个给定值恰好由一个变量保存。

  • TEMP_TB

    TCG 翻译块临时变量 在整个翻译块中存活,但在任意出口失效。这些临时变量在翻译期间显式分配。

  • TEMP_EBB

    TCG 扩展基本块临时变量 在整个扩展基本块中存活,但在任意出口失效。这些临时变量在翻译期间显式分配。

类型

  • TCG_TYPE_I32

    32 位整数。

  • TCG_TYPE_I64

    64 位整数。在 32 位主机上,会拆分为一对 type=TCG_TYPE_I32、base_type=TCG_TYPE_I64 的变量。每个变量的 temp_subindex 表示它在主机字节序表示中的位置。

  • TCG_TYPE_PTR

    TCG_TYPE_I32 或 TCG_TYPE_I64 的别名,取决于主机指针大小。

  • TCG_TYPE_REG

    TCG_TYPE_I32 或 TCG_TYPE_I64 的别名,取决于主机整数寄存器大小。根据主机 ABI,它可能大于 TCG_TYPE_PTR。

  • TCG_TYPE_I128

    128 位整数。在所有主机上,都会拆分为若干 type=TCG_TYPE_REG、base_type=TCG_TYPE_I128 的变量。每个变量的 temp_subindex 表示它在主机字节序表示中的位置。

  • TCG_TYPE_V64

    64 位向量。只有 TCG 目标设置 TCG_TARGET_HAS_v64 时,此类型才有效。

  • TCG_TYPE_V128

    128 位向量。只有 TCG 目标设置 TCG_TARGET_HAS_v128 时,此类型才有效。

  • TCG_TYPE_V256

    256 位向量。只有 TCG 目标设置 TCG_TARGET_HAS_v256 时,此类型才有效。

辅助函数

辅助函数在客户机专用的 helper.h 中注册,经处理后生成 tcg_gen_helper_* 函数。通过这些函数,可以调用接受 i32、i64、i128 或指针类型参数的函数。

默认情况下,调用辅助函数之前,会将所有全局变量保存到各自的规范位置。默认允许辅助函数修改 CPU 状态(包括 TCG 全局变量表示的状态)或引发异常。以下函数修饰符可以覆盖这些默认行为:

  • TCG_CALL_NO_WRITE_GLOBALS

    辅助函数不修改任何全局变量,但可以读取它们。调用之前仍会保存全局变量到规范位置,不过之后无需重新加载。

  • TCG_CALL_NO_READ_GLOBALS

    辅助函数既不直接读取全局变量,也不通过异常读取。调用前无需将它们保存到规范位置。此标志隐含 TCG_CALL_NO_WRITE_GLOBALS。

  • TCG_CALL_NO_SIDE_EFFECTS

    如果返回值未使用,可以移除辅助函数调用。这意味着它不得修改任何 CPU 状态,也不得引发异常。

代码优化

生成指令时,至少可以依赖以下优化:

  • 单条指令会被简化,例如

    and_i32 t0, t0, $0xffffffff
    

    会被删除。

  • 在基本块级别进行活跃性分析,据此删除从已失效变量到其他变量的移动,也会移除计算结果不再使用的指令。后者对 QEMU 条件码优化尤其有用。

    在以下示例中:

    add_i32 t0, t1, t2
    add_i32 t0, t0, $1
    mov_i32 t0, $1
    

    只保留最后一条指令。

指令参考

函数调用

call <ret> <params> ptr

调用函数 'ptr'(指针类型)

<ret> 可选的 32 位或 64 位返回值
<params> 可选的 32 位或 64 位参数

跳转与标签

set_label $label

在当前程序位置定义标签 'label'。

br $label

跳转到标签。

brcond t0, t1, cond, label

当 t0 cond t1 为真时条件跳转。cond 可以是:

TCG_COND_EQ
TCG_COND_NE
TCG_COND_LT /* signed */
TCG_COND_GE /* signed */
TCG_COND_LE /* signed */
TCG_COND_GT /* signed */
TCG_COND_LTU /* unsigned */
TCG_COND_GEU /* unsigned */
TCG_COND_LEU /* unsigned */
TCG_COND_GTU /* unsigned */
TCG_COND_TSTEQ /* t1 & t2 == 0 */
TCG_COND_TSTNE /* t1 & t2 != 0 */

算术运算

add t0, t1, t2

t0 = t1 + t2

sub t0, t1, t2

t0 = t1 - t2

neg t0, t1

t0 = -t1 (二进制补码)

mul t0, t1, t2

t0 = t1 * t2

divs t0, t1, t2

t0 = t1 / t2 (有符号)
除零或溢出时行为未定义。

divu t0, t1, t2

t0 = t1 / t2 (无符号)
除零时行为未定义。

rems t0, t1, t2

t0 = t1 % t2 (有符号)
除零或溢出时行为未定义。

remu t0, t1, t2

t0 = t1 % t2 (无符号)
除零时行为未定义。

divs2 q, r, nl, nh, d

q = nh:nl / d (有符号)
r = nh:nl % d
除零,或双字被除数除以单字除数得到的商无法用单字容纳时,行为未定义。代码生成器会将 nl 的简单符号扩展作为 nh 传入,因此唯一可能的溢出应为 INT_MIN / -1。

divu2 q, r, nl, nh, d

q = nh:nl / d (无符号)
r = nh:nl % d
除零,或双字被除数除以单字除数得到的商无法用单字容纳时,行为未定义。代码生成器会向 nh 传入 0,构成 nl 的简单零扩展,因此不应发生溢出。

逻辑运算

and t0, t1, t2

t0 = t1 & t2

or t0, t1, t2

t0 = t1 | t2

xor t0, t1, t2

t0 = t1 ^ t2

not t0, t1

t0 = ~t1

andc t0, t1, t2

t0 = t1 & ~t2

eqv t0, t1, t2

t0 = ~(t1 ^ t2),等价于 t0 = t1 ^ ~t2

nand t0, t1, t2

t0 = ~(t1 & t2)

nor t0, t1, t2

t0 = ~(t1 | t2)

orc t0, t1, t2

t0 = t1 | ~t2

clz t0, t1, t2

t0 = t1 ? clz(t1) : t2

ctz t0, t1, t2

t0 = t1 ? ctz(t1) : t2

ctpop t0, t1

t0 = t1 中置位的位数

名称 ctpop 是 "count population" 的缩写,与 include/qemu/host-utils.h 中使用的函数名一致。

移位与循环移位

shl t0, t1, t2

t0 = t1 << t2
移位量为负数或超出范围时,行为未指定。

shr t0, t1, t2

t0 = t1 >> t2 (无符号)
移位量为负数或超出范围时,行为未指定。

sar t0, t1, t2

t0 = t1 >> t2 (有符号)
移位量为负数或超出范围时,行为未指定。

rotl t0, t1, t2

向左循环移位 t2 位
移位量为负数或超出范围时,行为未指定。

rotr t0, t1, t2

向右循环移位 t2 位。
移位量为负数或超出范围时,行为未指定。

其他

mov t0, t1

t0 = t1
将 t1 移动到 t0。

bswap16 t0, t1, flags

对 32/64 位输入的低 16 位执行字节交换。

如果 flags & TCG_BSWAP_IZ,则已知 t1 从位 15 向高位进行了零扩展。
如果 flags & TCG_BSWAP_OZ,则 t0 将从位 15 向高位进行零扩展。
如果 flags & TCG_BSWAP_OS,则 t0 将从位 15 向高位进行符号扩展。

如果既未设置 TCG_BSWAP_OZ 也未设置 TCG_BSWAP_OS,则 t0 中位 15 以上的位可以包含任意值。

bswap32 t0, t1, flags

32 位字节交换。标志与 bswap16 相同,但从位 31 而非位 15 开始应用。对于 TCG_TYPE_I32,标志应为零。

bswap64 t0, t1, flags

64 位字节交换。标志被忽略,但为与其他 bswap 操作码保持一致,仍保留该参数。为兼容未来实现,标志应为零。

discard_i32/i64 t0

表明 t0 的值以后不会使用,可用于强制消除死代码。

deposit dest, t1, t2, pos, len

将 t2 作为位域插入 t1,结果放入 dest。

位域由立即数 pos/len 描述:

len - 位域长度
pos - 从最低有效位开始计数的首位位置

例如,"deposit dest, t1, t2, 8, 4" 表示从位 8 开始的 4 位位域。在 TCG_TYPE_I32 上,此操作等价于

dest = (t1 & ~0x0f00) | ((t2 << 8) & 0x0f00)

。

extract dest, t1, pos, len

sextract dest, t1, pos, len

从 t1 提取位域,结果放入 dest。

与上述 deposit 一样,位域由立即数 pos/len 描述。对于 extract_*,结果向左零扩展;对于 sextract_*,则复制位于 pos + len - 1 的位域符号位向左扩展。

例如,"sextract dest, t1, 8, 4" 表示从位 8 开始的 4 位位域。此操作等价于

dest = (t1 << 20) >> 28

(在 TCG_TYPE_I32 上使用算术右移)。

extract2 dest, t1, t2, pos

对于 TCG_TYPE_I{N},从 t2:t1 的拼接结果中,自 pos 起提取 N 位值。tcg_gen_extract2_{i32,i64} 展开器接受 0 <= pos <= N 的输入。后端代码生成器不会收到这些操作码输入值为 0 或 N 的情况。

extrl_i64_i32 t0, t1

仅适用于 64 位主机,提取输入 t1 的低 32 位,放入 32 位输出 t0。根据主机不同,可能只需简单移动,也可能需要额外规范化。

extrh_i64_i32 t0, t1

仅适用于 64 位主机,提取输入 t1 的高 32 位,放入 32 位输出 t0。根据主机不同,可能只需简单移位,也可能需要额外规范化。

条件移动

setcond dest, t1, t2, cond

dest = (t1 cond t2)

如果 (t1 cond t2) 为真,将 dest 设为 1,否则设为 0。

negsetcond dest, t1, t2, cond

dest = -(t1 cond t2)

如果 (t1 cond t2) 为真,将 dest 设为 -1,否则设为 0。

movcond dest, c1, c2, v1, v2, cond

dest = (c1 cond c2 ? v1 : v2)

如果 (c1 cond c2) 为真,将 dest 设为 v1,否则设为 v2。

类型转换

ext_i32_i64 t0, t1

将 t1 (32 位)转换为 t0 (64 位),并进行符号扩展。

extu_i32_i64 t0, t1

将 t1 (32 位)转换为 t0 (64 位),并进行零扩展。

trunc_i64_i32 t0, t1

将 t1 (64 位)截断为 t0 (32 位)。

concat_i32_i64 t0, t1, t2

构造 t0 (64 位),低半部分取自 t1 (32 位),高半部分取自 t2 (32 位)。

concat32_i64 t0, t1, t2

构造 t0 (64 位),低半部分取自 t1 (64 位),高半部分取自 t2 (64 位)。

加载与存储

ld_i32/i64 t0, t1, offset

ld8s_i32/i64 t0, t1, offset

ld8u_i32/i64 t0, t1, offset

ld16s_i32/i64 t0, t1, offset

ld16u_i32/i64 t0, t1, offset

ld32s_i64 t0, t1, offset

ld32u_i64 t0, t1, offset

t0 = read(t1 + offset)

从主机内存加载 8、16、32 或 64 位数据,可带或不带符号扩展。offset 必须是常量。

st_i32/i64 t0, t1, offset

st8_i32/i64 t0, t1, offset

st16_i32/i64 t0, t1, offset

st32_i64 t0, t1, offset

write(t0, t1 + offset)

向主机内存写入 8、16、32 或 64 位数据。

所有这些操作码均假定所指主机内存不对应全局变量,否则行为不可预测。

多字算术支持

addco t0, t1, t2

计算 t0 = t1 + t2,并向主机架构提供的进位位输出结果。

addci t0, t1, t2

计算 t0 = t1 + t2 + C,其中 C 为主机架构提供的输入进位位。无需计算输出进位位。

addcio t0, t1, t2

计算 t0 = t1 + t2 + C,其中 C 为主机架构提供的输入进位位,同时计算输出进位位。

addc1o t0, t1, t2

计算 t0 = t1 + t2 + 1,并向主机架构提供的进位位输出结果,类似于输入进位固定为 1 的 addcio。
它供优化过程使用,作为加法链完全折叠前的中间形式。有时无法完全折叠,此操作码会保留到输出阶段。此时,代码生成器先使用 tcg_out_set_carry,再使用 addcio 的输出例程。

subbo t0, t1, t2

计算 t0 = t1 - t2,并向主机架构提供的借位位输出结果。
根据主机架构不同,进位位可能与借位位相同,也可能不同。因此不得混用 addc* 与 subb* 操作码。

subbi t0, t1, t2

计算 t0 = t1 - t2 - B,其中 B 为主机架构提供的输入借位位。无需计算输出借位位。

subbio t0, t1, t2

计算 t0 = t1 - t2 - B,其中 B 为主机架构提供的输入借位位,同时计算输出借位位。

subb1o t0, t1, t2

计算 t0 = t1 - t2 - 1,并向主机架构提供的借位位输出结果,类似于输入借位固定为 1 的 subbio。
它供优化过程使用,作为减法链完全折叠前的中间形式。有时无法完全折叠,此操作码会保留到输出阶段。此时,代码生成器先使用 tcg_out_set_borrow,再使用 subbio 的输出例程。

mulu2 t0_low, t0_high, t1, t2

类似 mul,但两个无符号输入 t1 和 t2 产生完整双字乘积 t0,通过两个单字输出返回。

muls2 t0_low, t0_high, t1, t2

类似 mulu2,但两个输入 t1 和 t2 为有符号值。

mulsh t0, t1, t2

muluh t0, t1, t2

分别提供有符号或无符号乘法结果的高半部分。

如果后端未提供 mulu2/muls2,tcg-op 生成器可以发出一对操作码 mul + muluh/mulsh,得到相同结果。

内存屏障支持

mb <$arg>

生成目标内存屏障指令,保证对应客户机内存屏障指令所要求的内存顺序。

后端保证的顺序可以比客户机要求更严格,但不能更弱。此操作码接受一个常量参数,用于生成相应屏障指令。后端应仅在必要时发出目标屏障指令,即客户机为 SMP 且启用 MTTCG 时。

客户机翻译器应为所有具有顺序副作用的客户机指令生成此操作码。

内存屏障的更多信息见 QEMU 中的原子操作。

QEMU 专用操作

exit_tb t0

退出当前 TB 并返回值 t0 (字类型)。

goto_tb index

如果当前 TB 已链接到索引 index (常量)指定的 TB,则退出当前 TB 并跳转到该 TB,否则执行后续指令。只有索引 0 和 1 有效;每个 TB 中,对每个槽位索引最多发出一次 tcg_gen_goto_tb。

lookup_and_goto_ptr tb_addr

查找 TB 地址 tb_addr,有效则跳转过去,否则跳转到 TCG 尾声代码,返回执行循环。

此操作可选。如果 TCG 后端未实现 goto_ptr 操作码,发出此操作等价于发出 exit_tb(0)。

qemu_ld_i32/i64/i128 t0, t1, flags, memidx

qemu_st_i32/i64/i128 t0, t1, flags, memidx

将客户机地址 t1 处的数据加载到 t0,或将 t0 的数据存储到客户机地址 t1。_i32/_i64/_i128 仅描述输入/输出寄存器 t0 的大小。地址 t1 的大小始终由客户机决定,内存操作宽度由 flags 控制。

在 32 位主机处理 64 位值,或在 64 位主机处理 128 位值时,t0 和 t1 都可能拆分成按小端顺序排列的寄存器对。

memidx 选择要使用的 QEMU TLB 索引,例如用户态或内核态访问。标志为 MemOp 位,选择内存访问的符号性、宽度和字节序。

对于 32 位主机,保证 qemu_ld/st_i64 仅用于 flags 指定的 64 位内存访问。

qemu_ld/st_i128 仅在 64 位主机上受支持。

主机向量操作

所有向量操作都有 TCGOP_TYPE 和 TCGOP_VECE 两个参数。前者以 TCGType 指定向量长度;后者在适用时指定元素长度,即以 8 位为单位的长度的 log2。

mov_vec v0, v1

ld_vec v0, t1

st_vec v0, t1

移动、加载和存储。

dup_vec v0, r1

将 r1 的低 N 位复制为 TYPE/VECE 份,填满 v0。

dupi_vec v0, c

同样的操作,但用于常量。
展开器会重复较小的值,使其达到主机寄存器大小。

add_vec v0, v1, v2

对整个向量逐元素执行 v0 = v1 + v2。

sub_vec v0, v1, v2

同样,v0 = v1 - v2。

mul_vec v0, v1, v2

同样,v0 = v1 * v2。

neg_vec v0, v1

同样,v0 = -v1。

abs_vec v0, v1

同样,对整个向量逐元素执行 v0 = v1 < 0 ? -v1 : v1。

smin_vec v0, v1, v2

umin_vec v0, v1, v2

同样,v0 = MIN(v1, v2),分别用于有符号和无符号元素类型。

smax_vec v0, v1, v2

umax_vec v0, v1, v2

同样,v0 = MAX(v1, v2),分别用于有符号和无符号元素类型。

ssadd_vec v0, v1, v2

sssub_vec v0, v1, v2

usadd_vec v0, v1, v2

ussub_vec v0, v1, v2

有符号和无符号饱和加法、减法。

如果真实结果超出元素类型的表示范围,就将元素设为该类型的最小值或最大值。

and_vec v0, v1, v2

nand_vec v0, v1, v2

or_vec v0, v1, v2

nor_vec v0, v1, v2

xor_vec v0, v1, v2

eqv_vec v0, v1, v2

andc_vec v0, v1, v2

orc_vec v0, v1, v2

not_vec v0, v1

同样,执行带取反或不带取反的逻辑运算。

注意,未使用 VECE。

shli_vec v0, v1, i2

shls_vec v0, v1, s2

将 v1 的所有元素按标量 i2/s2 移位,即
for (i = 0; i < TYPE/VECE; ++i) {
    v0[i] = v1[i] << s2;
}

shri_vec v0, v1, i2

sari_vec v0, v1, i2

rotli_vec v0, v1, i2

shrs_vec v0, v1, s2

sars_vec v0, v1, s2

rotls_vec v0, v1, s2

逻辑右移、算术右移和循环左移同理。

shlv_vec v0, v1, v2

将 v1 的元素按 v2 对应元素指定的量移位,即
for (i = 0; i < TYPE/VECE; ++i) {
    v0[i] = v1[i] << v2[i];
}

shrv_vec v0, v1, v2

sarv_vec v0, v1, v2

rotlv_vec v0, v1, v2

rotrv_vec v0, v1, v2

逻辑右移、算术右移和循环移位同理。

cmp_vec v0, v1, v2, cond

逐元素比较向量,真则保存 -1,假则保存 0。

bitsel_vec v0, v1, v2, v3

对整个向量按位选择:v0 = (v2 & v1) | (v3 & ~v1)。

cmpsel_vec v0, c1, c2, v3, v4, cond

根据比较结果选择元素:
for (i = 0; i < n; ++i) {
    v0[i] = (c1[i] cond c2[i]) ? v3[i] : v4[i].
}

注 1:当已知最后一个操作数为常量时,提供一些便捷形式,例如 add 对应 addi,mov 对应 movi。

注 2:使用 TCG 时,绝不能直接生成操作码,因为其中某些可能并不是可用的“真实”操作码。始终使用 tcg_gen_xxx(args) 函数。

后端

tcg-target.h 包含目标专用定义。tcg-target.c.inc 包含目标专用代码,由 tcg/tcg.c 通过 #include 引入,并非独立的 C 文件。

假设

目标字长(TCG_TARGET_REG_BITS)预期为 64 位,指针大小预期与字长相同。

使用以下操作在 32 位与 64 位寄存器之间传递值:

  • extrl_i64_i32

  • extrh_i64_i32

  • ext_i32_i64

  • extu_i32_i64

它们保证值在 32 位与 64 位寄存器之间移动时正确截断或扩展。extrl_i64_i32 和 extrh_i64_i32 为可选操作,若满足以下所有条件,就无需实现:

  • 64 位寄存器可以保存 32 位值。

  • 64 位寄存器中的 32 位值无需保持零扩展或符号扩展。

  • 所有 32 位 TCG 操作均忽略 64 位寄存器的高半部分。

此版本不支持浮点运算。代码生成器以前的版本曾完整支持浮点,但目前最好先集中处理整数运算。

约束

每条指令使用类似 GCC 的约束定义。此版本不支持内存约束。与 GCC 一样,在输入操作数中指定别名。

即使未显式指定别名,输入和输出也可能使用同一个寄存器。如果某操作展开成多条目标指令,必须注意避免覆盖输入值。支持通过 & 指定 GCC 风格的“提前覆盖”(early clobber)输出。

目标可以定义专用的寄存器或常量约束。如果某操作采用的常量输入约束不允许所有常量,就必须同时接受寄存器作为后备方案。通用约束 i 接受任意常量。r 没有通用定义,但各后端一致用它表示所有寄存器。如果后端定义了 TCG_REG_ZERO,则通用约束 z 将常量 0 映射到硬件零寄存器。

movi_i32 和 movi_i64 操作必须接受任意常量。

mov_i32 和 mov_i64 操作必须接受相同类型的任意寄存器。

ld/st/sti 指令必须接受有符号 32 位常量偏移。可以预留特定寄存器,在偏移过大时用它计算地址。

ld/st 指令必须接受任意目标寄存器(ld)或源寄存器(st)。

如果无法存储给定常量,sti 指令可以失败。

函数调用假设

  • 参数和返回值仅支持 32 位整数、64 位整数和指针。

  • 栈向下增长。

  • 前 N 个参数通过寄存器传递。

  • 后续参数按字存储到栈上传递。

  • 调用会覆盖某些寄存器。

  • 函数可通过寄存器返回 0 或 1 个值。在 32 位目标上,对于 64 位返回类型,函数必须能通过寄存器返回 2 个值。