[考研][计算机组成原理] 程序的机器级表示
考研，408，组成原理，程序的机器级表示
考研 408 大纲《计算机组成原理》指令系统部分新增的 高级语言程序于机器级代码直接的对应 考点：
- 选择结构语句的机器级表示
- 循环结构语句的机器级表示
- 过程（函数）调用对应的机器基本表示
主要看 CSAPP 整理了一下。
流程控制
if-else
csapp2e.Zh_CN P130: 3.6.4
C 语言模版：
if (test_expr)then_statement
elseelse_statement
Goto 版本：
t = test_expr;if (!t)goto FALSE;then_statementgoto DONE;
FALSE:else_statement
DONE:
注意这里的 FALSE 是个标签，不是 0.
如果思路反过来，测试 t 为真时 goto 跳转到 TRUE 去跑 then_statement，虽然也可以，但对于没有 else 的 if 就会很诡异。
汇编（ATT 风格 MOV S, D 表示 S -> D）：
[test_expr] # 测试语句: e.g. cmpjnc 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;elsereturn 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 # xmovl 12(%ebp), %eax # ycmpl %eax, %edx # x:y 做 x-y 来比较jge X_GE_Y # x >= y 则跳转subl %edx, %eax # y-xjmp DONE
X_GE_Y:subl %eax, %edx # x-ymovl %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
C:
dobody_statement
while (test_expr);
goto:
LOOP:body_statementt = 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 # nmovl $1, %eax # result
LOOP:imull %edx, %eax # result *= nsubl $1, %edx # n = n-1cmpl $1, %edx # cmp: n-1jg LOOP # if (n>1) goto LOOP
while
csapp2e.Zh_CN P134
C:
while (test_expr)body_statement
其实 while 就是在 do-while 开始之前多一个入口检测 if 检测。
翻译成 do-while 循环:
if (!text_expr)goto DONE;dobody_statementwhile (text_expr);
DONE:
再展开 do-while，得到纯粹的 goto 版本：
t = test_expr;if (!t)goto DONE;
LOOP:body_statementt = 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 # nmovl $1, %eax # resultcmpl $1, %edx # cmp: n-1jle DONE # if (n<=1) goto DONE
LOOP:imull %edx, %eax # result *= nsubl $1, %edx # n = n-1cmpl $1, %edx # cmp: n-1jg LOOP # if (n>1) goto LOOP
DONE:
for
csapp2e.Zh_CN P137
for (init_expr; test_expr; update_expr)body_statement
C 规定 for 等效于如下的 while ：（K&R 2e P60: 3.5）
init_expr;
while (test_expr) {body_statementupdate_expr;
}
也就是，在 while 的基础上，最前面（循环外面）加了一个 init_expr，循环体最后（循环里面）加了一个 update_expr。
进一步，翻译成 do-while 循环：
init_expr;if (!test_expr)goto DONE;do {body_statementupdate_expr;} while (test_expr);
DONE:
goto 版本：
init_expr;t = test_expr;if (!t)goto DONE;
LOOP:body_statementupdate_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) continuesum += 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 # nmovl 8(%esp), %edx # xsubl $100, %edxcmpl $6, %edxja .L8addl .L4@GOTOFF(%ecx,%edx,4), %ecxjmp *%ecx # 跳转到 ecx 里面的地址: *jt[n]
.L7: # loc_A: case 100leal (%eax,%eax,2), %edx # t = x*3leal (%eax,%edx,4), %eax # result = x + 4*tret
.L6: # loc_B: case 102addl $10, %eax# fall through
.L5: # rest: case 103addl $11, %eaxret
.L3: # loc_D: case 104, 106imull %eax, %eaxret
.L8: # defaultmovl $0, %eaxret
这个和书上不太一样，我自己编译出来的（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 子过程
- 被调用者：建栈，保存，执行，恢复，离开（退栈），返回调用者
过程调用步骤
-
调用者：
-
保存「调用者保存寄存器」：
%eax, %edx, %ecx -
参数逐个压入栈
-
call Q：「返回地址」压入栈，跳到Q处执行。
-
-
被调用者（子过程）：
-
建立：子过程一开始，先把 ebp 改成当前的（保存起调用者的）：
# 手动写这两行： pushl %ebp movl %esp, %ebp -
保存其他「被调用者保存」寄存器（可选）:
pushl reg # 可能是 %ebx, %esi, %edi -
执行子过程主体
-
恢复「被调用者保存」寄存器：一个个
pop出来。 -
leave：准备返回（还原栈和帧，把子过程的栈帧弹出来）：leave# ⬆️等价⬇️ #movl %ebp, %esp popl %ebp -
ret弹出「返回地址」，执行之：转回调用者
-
之所以分开几步，有的手动，有的自动，可以理解为是因为 call、leave、ret 这些指令偶尔也可以单用。比如下面的代码，通过 call 获取 PC 值，放到整数寄存器：
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.cGCC: (Homebrew GCC 10.2.0_3) 10.2.0
_add:# 建立pushl %ebpmovl %esp, %ebp# 执行movl 8(%ebp), %edxmovl 12(%ebp), %eaxaddl %edx, %eax# 离开, 返回popl %ebpret_caller:pushl %ebpmovl %esp, %ebpsubl $24, %esp # 新分配栈空间movl $1, -12(%ebp) # xmovl $2, -16(%ebp) # ypushl -16(%ebp) # 参数: b=ypushl -12(%ebp) # 参数: a=xcall _addaddl $8, %esp # 缩回放参数的栈空间movl %eax, -20(%ebp)movl -20(%ebp), %eaxleaveret
subl $24, %esp 是用来给栈帧分配空间。栈反向增长，所以是减。24 个字节里，8 个用来放局部变量，中间 8 个闲置，最后 8 个用来放给子过程的参数。
按照惯例，这里的 add 和 caller 都把自己的返回值放到了 %eax 中，给上一层调用者自行读取。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！