程序的机器级表示

clownote

2021-10-09 (Updated: 2022-12-01)

==考研==，==408==，==组成原理==，==程序的机器级表示==

考研 408 大纲《计算机组成原理》指令系统部分新增的 高级语言程序于机器级代码直接的对应 考点：

选择结构语句的机器级表示
循环结构语句的机器级表示
过程（函数）调用对应的机器基本表示

主要看 CSAPP 整理了一下。

流程控制

if-else

csapp2e.Zh_CN P130: 3.6.4

C 语言模版：

if (test_expr)
    then_statement
else
    else_statement

Goto 版本：

  t = test_expr;
  if (!t)
      goto FALSE;
  then_statement
  goto DONE;
FALSE:
  else_statement
DONE:

注意这里的 FALSE 是个标签，不是 0.

如果思路反过来，测试 t 为真时 goto 跳转到 TRUE 去跑 then_statement，虽然也可以，但对于没有 else 的 if 就会很诡异。

汇编（ATT 风格 MOV S, D 表示 S -> D）：

  [test_expr]        # 测试语句:        e.g. cmp
  jnc FALSE          # 不满足条件时跳转: e.g. je
  [then_statement]
  jmp DONE
FALSE:
  [else_statement]
DONE:

约定：我们用 jc、jnc 来代表某个“条件跳转”指令，具体可能是 je，jg，jl 等等。

jc：满足条件时跳转，对应 if (test_expr) goto L;；
jnc：不满足条件时跳转，对应 if (!t) goto L;。

我们在汇编里用 [test_expr] 这种表示实现 C 中的 test_expr 的一块代码。

e.g. if-else

int absdiff(int x, int y) {
    if (x < y)
        return y - x;
    else
        return x - y;
}

goto:

int absdiff_goto(int x, int y) {
    int result;
    if (x >= y)
        goto x_ge_y;
    result = y - x;
    goto done;
  x_ge_y:
    result = x - y;
  done:
    return result;
}

asm:

  movl 8(%ebp), %edx    # x
  movl 12(%ebp), %eax   # y
  cmpl %eax, %edx       # x:y 做 x-y 来比较
  jge  X_GE_Y            # x >= y 则跳转
  subl %edx, %eax       # y-x
  jmp  DONE
X_GE_Y:
  subl %eax, %edx       # x-y
  movl %edx, %eax
DONE:

[补充]条件传送

对于用三目运算符完成的简单的条件，例如 min = (x < y ? x : y); 把这个翻译成 if-else，用上面的那种手法去翻译，其实对流水线并不友好。控制冒险如果错了惩罚时间相当长。

现代机器上有「条件传送」指令：cmov。就是类似于条件跳转 jc，cmov 在满足条件的时候做 mov。

具体的 cmov 族也是有 cmove、cmovl、cmovge 等等这些。

利用这个指令，可以把两个分支全算了，最后利用 cmov 来选一个结果。就不用去控制冒险了：

v = test_expr ? then_expr : else_expr;

/* ⬇️ */

vt = then_expr;
v  = else_expr;
t  = test_expr;
if (t) v = vt;    // 用 cmov 实现

但注意，这个不是通用的！！不是所有三目运算都可以这么翻译，一般只有这种纯运算、没有副作用的才能这么搞。

do-while

csapp2e.Zh_CN P130: 3.6.5

1
2
3

do
    body_statement
while (test_expr);

goto:

LOOP:
  body_statement
  t = test_expr;
  if (t)
      goto LOOP;

其实 do-while 和汇编是自然对应的：do 换成 loop 标签，while 就是 if 条件 goto. 非常简单。其他的循环都可以先翻译成 do-while 循环，再写成汇编。

asm:

LOOP:
  [body_statement]
  [test_expr]
  jc LOOP     # 满足 test_expr 则跳转

e.g. do-while

计算 n 的阶乘：

int fact(int n) {
    int result = 1;
    do {
        result *= n;
        n = n-1;
    } while (n > 1);
    return result;
}

asm:

  movl  8(%ebp), %edx   # n
  movl  $1, %eax        # result
LOOP:
  imull %edx, %eax      # result *= n
  subl  $1, %edx        # n = n-1
  cmpl  $1, %edx        # cmp: n-1
  jg    LOOP            # if (n>1) goto LOOP

while

csapp2e.Zh_CN P134

1 2	while (test_expr) body_statement

其实 while 就是在 do-while 开始之前多一个入口检测 if 检测。

翻译成 do-while 循环:

  if (!text_expr)
      goto DONE;
  do
      body_statement
      while (text_expr);
DONE:

再展开 do-while，得到纯粹的 goto 版本：

  t = test_expr;
  if (!t)
      goto DONE;
LOOP:
  body_statement
  t = text_expr;
  if (t)
      goto LOOP;
DONE:

asm：

  [test_expr]
  jnc DONE   # 不满足 test_expr 则跳转
LOOP:
  [body_statement]
  [test_expr]
  jc LOOP    # 满足 test_expr 则跳转
DONE:

其实在 do-while 的基础上，加了最前面的一个测试条件跳转，还有最后的 DONE 标签。

注意入口测试的 jnc 和 LOOP 里的 jc 刚好是反的。

e.g. while

还是刚才的阶乘，改成 while 入口循环：

int fact(int n) {
    int result = 1;
    while (n > 1) {
        result *= n;
        n = n-1;
    };
    return result;
}

asm:

  movl  8(%ebp), %edx   # n
  movl  $1, %eax        # result
  cmpl  $1, %edx        # cmp: n-1
  jle   DONE            # if (n<=1) goto DONE 
LOOP:
  imull %edx, %eax      # result *= n
  subl  $1, %edx        # n = n-1
  cmpl  $1, %edx        # cmp: n-1
  jg    LOOP            # if (n>1) goto LOOP
DONE:

for

csapp2e.Zh_CN P137

1 2	for (init_expr; test_expr; update_expr) body_statement

C 规定 for 等效于如下的 while ：（K&R 2e P60: 3.5）

init_expr;
while (test_expr) {
    body_statement
    update_expr;
}

也就是，在 while 的基础上，最前面（循环外面）加了一个 init_expr，循环体最后（循环里面）加了一个 update_expr。

进一步，翻译成 do-while 循环：

  init_expr;
  if (!test_expr)
      goto DONE;
  do {
      body_statement
      update_expr;
  } while (test_expr);
DONE:

goto 版本：

  init_expr;
  t = test_expr;
  if (!t)
      goto DONE;
LOOP:
  body_statement
  update_expr;
  t = test_expr;
  if (t)
      goto LOOP;
DONE:

asm:

  [init_expr]
  [test_expr]
  jnc DONE   # 不满足 test_expr 则跳转
LOOP:
  [body_statement]
  [update_expr]
  [test_expr]
  jc LOOP    # 满足 test_expr 则跳转
DONE:

（只是在 while 的基础上加了 2、7 两行）

特例：带continue的for

csapp2e.Zh_CN P139: 练习题3.24 （答案P219）

带 continue 的 for 直接翻译成 while 就炸了，更新表达式执行不到，导致无限循环：

for (i = 0; i < 10; i++) {
    if (i % 1) continue
    sum += i;
}

/* ⬇️ */

while (i < 10) {    // ❌
    if (i % 1) {
        continue;
    }
    sum += i;
    i++;
}

正确的做法，把 continue 改成一组 goto-label：

while (i < 10) {
    if (i % 1) {
        goto UPDATE;
    }
    sum += i;
UPDATE:
    i++;
}

switch

csapp2e.Zh_CN P144: 3.6.7

switch 才是最麻烦的。

switch 在分支多、值范围跨度小时可以用「跳转表」来实现。

int switch_eg(int x, int n)
{
    int result = x;
    switch (n) {
        case 100:
            result *= 13;
            break;
        case 102:
            result += 10;
            /* Fall through */
        case 103:
            result += 11;
            break;
        case 104:
        case 106:
            result *= result;
            break;
        default:
            result = 0;
    }
    return result;
}

这个东西 GCC 用拓展的 C 语言来实现：用 && 运算符取一个 label 的位置。（GCC Extensions: Labels as Values）


int
switch_eg_impl(int x, int n)
{
    /* Table of code pointers */
    static void* jt[7] = { 
        &&loc_A, &&loc_def, &&loc_B, 
        &&loc_C, &&loc_D, &&loc_def, 
        &&loc_D 
    };

    unsigned index = n - 100;
    int result;

    if (index > 6)
        goto loc_def;

    /* Multiway branch */
    goto* jt[index];

loc_def: /* Default case*/
    result = O;
    goto done;

loc_C:
    /*Case103*/
    result = x;
    goto rest;

loc_A: /*Case100*/
    result = x * 13;
    goto done;

loc_B:
    /* Case 102 */
    result = x + 10;
    /* Fall through */

rest:
    /* Fínish case 103 */
    result += 11;
    goto done;
loc_D:
    /* Cases 104, 106 */
    result = x * x;
/*. Fall through */
done:
    return result;
}

就是顺序穷举，把每个 case 的 label 地址放到跳转表 jt 中。然后根据 switch 变量 n，从顺序的跳转表中取出对应下标处的 label 来执行。

编译成汇编：

跳转表（数据部分）：

	.section	.rodata
.L4:
	.long	.L7@GOTOFF
	.long	.L8@GOTOFF
	.long	.L6@GOTOFF
	.long	.L5@GOTOFF
	.long	.L3@GOTOFF
	.long	.L8@GOTOFF
	.long	.L3@GOTOFF

switch_eg 函数：

	movl	4(%esp), %eax   # n
	movl	8(%esp), %edx   # x
	subl	$100, %edx
	cmpl	$6, %edx
	ja	.L8
	addl	.L4@GOTOFF(%ecx,%edx,4), %ecx
	jmp	*%ecx   # 跳转到 ecx 里面的地址: *jt[n]
.L7:  # loc_A: case 100
	leal	(%eax,%eax,2), %edx  # t = x*3
	leal	(%eax,%edx,4), %eax  # result = x + 4*t
	ret
.L6:  # loc_B: case 102
	addl	$10, %eax
	# fall through
.L5:  # rest: case 103
	addl	$11, %eax
	ret
.L3:  # loc_D: case 104, 106
	imull	%eax, %eax
	ret
.L8:  # default
	movl	$0, %eax
	ret

这个和书上不太一样，我自己编译出来的（gcc -O1 -m32 -S switch.c，GCC: (Debian 8.3.0-6) 8.3.0）我这个把 ret 提进去了，区别不大。（用 -O0 能编译出那种最后跳转到 .L8 的，但局部实现比较可怕，所以这里没有采用）

过程调用

csapp2e.Zh_CN P149: 3.7

过程依赖于栈：

栈帧示意图

%ebp 指向当前过程的栈帧(底)，%esp 指向当前过程的栈顶。

调用者 P 调用被调用者 Q，Q 的参数、返回地址（就是 call 指令之后的下一条指令地址）放在 P 的栈帧中。

一个过程调用的步骤如下：

调用者：保存，压参，call 子过程
被调用者：建栈，保存，执行，恢复，离开（退栈），返回调用者

过程调用步骤

调用者：
- 保存「调用者保存寄存器」：
  1
  %eax, %edx, %ecx
- 参数逐个压入栈
- call Q：「返回地址」压入栈，跳到 Q 处执行。
被调用者（子过程）：
- 建立：子过程一开始，先把 ebp 改成当前的（保存起调用者的）：
  1
  2
  3
  # 手动写这两行：
  pushl %ebp
  movl %esp, %ebp
- 保存其他「被调用者保存」寄存器（可选）:
  1
  pushl reg # 可能是 %ebx, %esi, %edi
- 执行子过程主体
- 恢复「被调用者保存」寄存器：一个个 pop 出来。
- leave：准备返回（还原栈和帧，把子过程的栈帧弹出来）：
  1
  2
  3
  4
  5
  6
  leave
  
  # ⬆️等价⬇️ #
  
  movl %ebp, %esp
  popl %ebp
- ret 弹出「返回地址」，执行之：转回调用者

之所以分开几步，有的手动，有的自动，可以理解为是因为 call、leave、ret 这些指令偶尔也可以单用。比如下面的代码，通过 call 获取 PC 值，放到整数寄存器：

1
2
3

  call next
next:
  popl %eax

这里用了 call，但不是过程调用，还是顺序执行的，这只是个获取 PC 的小技巧。

一定要上了那完整的一套才是个过程调用。

e.g. 过程调用

int
add(int a, int b)
{
    return a + b;
}

int
caller()
{
    int x = 1;
    int y = 2;

    int z = add(x, y);

    return z;
}

编译出来：

$ gcc -m32 -O0 -S call.c

GCC: (Homebrew GCC 10.2.0_3) 10.2.0

_add:
	# 建立
	pushl	%ebp
	movl	%esp, %ebp
	
	# 执行
	movl	8(%ebp), %edx
	movl	12(%ebp), %eax
	addl	%edx, %eax
	
	# 离开, 返回
	popl	%ebp
	ret


_caller:
	pushl	%ebp
	movl	%esp, %ebp
	
	subl	$24, %esp     # 新分配栈空间
	
	movl	$1, -12(%ebp) # x
	movl	$2, -16(%ebp) # y
	
	pushl	-16(%ebp)     # 参数: b=y
	pushl	-12(%ebp)     # 参数: a=x
	call	_add
	
	addl	$8, %esp      # 缩回放参数的栈空间
	
	movl	%eax, -20(%ebp)
	movl	-20(%ebp), %eax
	
	leave
	ret

subl $24, %esp 是用来给栈帧分配空间。栈反向增长，所以是减。24 个字节里，8 个用来放局部变量，中间 8 个闲置，最后 8 个用来放给子过程的参数。

按照惯例，这里的 add 和 caller 都把自己的返回值放到了 %eax 中，给上一层调用者自行读取。

-12(%ebp) # x
movl $2, -16(%ebp) # y

pushl    -16(%ebp)     # 参数: b=y
pushl    -12(%ebp)     # 参数: a=x
call    _add

addl    $8, %esp      # 缩回放参数的栈空间

movl    %eax, -20(%ebp)
movl    -20(%ebp), %eax

leave
ret


`subl $24, %esp` 是用来给栈帧分配空间。栈反向增长，所以是减。24 个字节里，8 个用来放局部变量，中间 8 个闲置，最后 8 个用来放给子过程的参数。

按照惯例，这里的 add 和 caller 都把自己的返回值放到了 `%eax` 中，给上一层调用者自行读取。