CMU 15-213 Intro to Computer Systems Lecture 6

课程主页:http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料:https://github.com/EugeneLiu/translationCSAPP

课程视频:https://www.bilibili.com/video/av31289365/

这一讲介绍了机器级编程2:控制。

控制:条件码

条件码(隐式设置)

  • 单比特寄存器

    • CF:进位标志(无符号)
    • SF:符号标志(有符号)
    • ZF:零标记
    • OF:溢出标志(有符号)
  • 通过算术运算隐式设置

    • 例如:addq Src, Dest $ \leftrightarrow t = a + b $

    • 如果最高有效位进位,则CF置为1(无符号溢出)

    • 如果$ t == 0 $,则ZF置为1

    • 如果$ t <0 $,则SF置为1

    • 如果

      则OF置为1

  • leaq指令不会改变条件码

条件码(显式设置)

  • 通过比较指令进行显式设置

    • cmpq Src2,Src1

    • cmpq b,类似于计算a-b而不设置

    • 如果最高有效位进位,则CF置为1(无符号溢出)

    • 如果$ a == b $,则ZF置为1

    • 如果$ (a-b) <0 $,则SF置为1

    • 如果

      则OF置为1

  • 通过测试指令进行显式设置

    • testq Src2,Src1
      • testq b,a类似于计算$a \& b$而不设置dest
    • 根据$ \operatorname {Src} 1\& \operatorname {Src} 2 $的值设置条件码
    • 使一个操作数成为掩码很有用
    • 当$ a \& b == 0 $时设置ZF为1
    • 当$a \& b <0 $时设置SF为1

读取条件码

  • SetX指令
    • 根据条件码的组合,将dest的低位字节设置为0或1
    • 不会更改剩余的7个字节

来看一个具体例子:

1
2
3
4
int gt (long x, long y)
{
return x > y;
}

汇编代码为

1
2
3
4
cmpq %rsi, %rdi 	# Compare x:y
setg %al # Set when >
movzbl %al, %eax # Zero rest of %rax
ret

变量和寄存器的对应关系为

条件分支

跳转指令

条件分支例子

考虑如下例子:

1
2
3
4
5
6
7
8
9
long absdiff(long x, long y)
{
long result;
if (x > y)
result = x-y;
else
result = y-x;
return result;
}

为了和汇编码格风格相近,首先将上述代码改写为goto的格式:

1
2
3
4
5
6
7
8
9
10
11
12
long absdiff_j(long x, long y)
{
long result;
int ntest = x <= y;
if (ntest) goto Else;
result = x-y;
goto Done;
Else:
result = y-x;
Done:
return result;
}

汇编码为

1
2
3
4
5
6
7
8
9
10
absdiff: 
cmpq %rsi, %rdi # x:y
jle .L4
movq %rdi, %rax
subq %rsi, %rax
ret
.L4: # x <= y
movq %rsi, %rax
subq
ret

变量和寄存器的对应关系为

一般情形如下:

C语言:

1
val = Test ? Then_Expr : Else_Expr;

汇编码:

1
2
3
4
5
6
7
8
    ntest = !Test; 
if (ntest) goto Else;
val = Then_Expr;
goto Done;
Else:
val = Else_Expr;
Done:
. . .

使用条件移动

  • 条件移动指令
    • 指令支持:
      • $\text{if (Test) Dest}\leftarrow \text{Src}$
    • 在1995年后的x86处理器中受支持
    • GCC尝试使用它们
      • 但是,只有在已知安全的情况下为
  • 为什么?
    • 分支对流水线中的指令流造成很大破坏
    • 条件移动不需要控制转移

C代码

1
val = Test ? Then_Expr : Else_Expr;

汇编代码

1
2
3
4
5
result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if (nt) result = eval;
return result;

一个具体例子如下:

1
2
3
4
5
6
7
8
9
long absdiff(long x, long y)
{
long result;
if (x > y)
result = x-y;
else
result = y-x;
return result;
}

汇编码如下:

1
2
3
4
5
6
7
8
absdiff:
movq %rdi, %rax # x
subq %rsi, %rax # result = x-y
movq %rsi, %rdx
subq %rdi, %rdx # eval = y-x
cmpq %rsi, %rdi # x:y
cmovle %rdx, %rax # if <=, result = eval
ret

寄存器和变量的对应关系如下:

条件移动的坏案例

  • 昂贵的计算

    1
    val = Test(x) ? Hard1(x) : Hard2(x);
    • 计算两个值
    • 仅在计算非常简单时才有意义
  • 风险计算

    1
    val = p ? *p : 0;
  • 计算两个值
  • 可能会有不良影响
  • 计算有副作用

    1
    val = x > 0 ? x*=7 : x+=3;
    • 计算两个值
    • 必须无副作用

循环

“Do-While”循环例子

C代码

1
2
3
4
5
6
7
8
9
long pcount_do(unsigned long x) 
{
long result = 0;
do {
result += x & 0x1;
x >>= 1;
} while (x);
return result;
}

goto版本

1
2
3
4
5
6
7
8
9
long pcount_goto(unsigned long x) 
{
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if(x) goto loop;
return result;
}

汇编代码

1
2
3
4
5
6
7
8
	movl $0, %eax 		# result = 0
.L2: # loop:
movq %rdi, %rdx
andl $1, %edx # t = x & 0x1
addq %rdx, %rax # result += t
shrq %rdi # x >>= 1
jne .L2 # if (x) goto loop
rep; ret

寄存器和变量的对应关系如下:

一般的”Do-While”翻译

Do-While代码

1
2
3
do
Body
while (Test);

Goto版本

1
2
3
4
loop:
Body
if (Test)
goto loop

其中Body的形式如下

1
{ Statement1; Statement2; … Statementn; }

一般的”While”翻译

While代码

1
2
while (Test)
Body

Goto版本

1
2
3
4
5
6
7
	goto test;
loop:
Body
test:
if (Test)
goto loop;
done:

另一种方法是将While修改为Do-While

1
2
3
4
5
6
if (!Test)
goto done;
do
Body
while(Test);
done:

Goto版本

1
2
3
4
5
6
7
if (!Test)
goto done;
loop:
Body
if (Test)
goto loop;
done:

一般的”For”循环翻译

For循环形式

1
2
for (Init; Test; Update )
Body

修改为While循环

1
2
3
4
5
Init;
while (Test) {
Body
Update;
}

Switch语句

跳转表结构

Switch分支使用了跳转表结构:

跳转表将分支的条件转换为0到n,然后补齐中间缺失的部分。

例子

C代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long switch_eg (long x, long y, long z)
{ long w = 1;
switch(x) {
case 1: //.L3
w = y*z;
break;
case 2: //.L5
w = y/z;
/* Fall Through */
case 3: //.L9
w += z;
break;
case 5:
case 6: //.L7
w -= z;
break;
default: //.L8
w = 2;
}
return w;
}

跳转表

1
2
3
4
5
6
7
8
9
10
.section .rodata
.align 8
.L4:
.quad .L8 # x = 0
.quad .L3 # x = 1
.quad .L5 # x = 2
.quad .L9 # x = 3
.quad .L8 # x = 4
.quad .L7 # x = 5
.quad .L7 # x = 6

总结

  • C控制
    • if-then-else
    • do-while
    • while, for
    • switch
  • 汇编程序控制
    • 条件跳跃
    • 条件移动
    • 间接跳转(通过跳转表)
    • 编译器生成代码序列以实现更复杂的控制
  • 标准技术
    • 循环转换为do-­‐while或jump-­to-middle的形式
    • 大型switch语句使用跳转表
    • 稀疏的switch语句可能使用决策树(if-elseif-elseif-else)

本文标题:CMU 15-213 Intro to Computer Systems Lecture 6

文章作者:Doraemonzzz

发布时间:2020年05月19日 - 10:00:00

最后更新:2020年05月21日 - 15:43:28

原始链接:http://doraemonzzz.com/2020/05/19/CMU 15-213 Intro to Computer Systems Lecture 6/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。